1

Estou estudando recursividade, e queria encontrar uma maneira de fazer um algoritmo recursivo para sequencia de fibonacci eficiente, onde o algoritmo não seja exponencial. Como vou guardar o valor dos subproblemas?? Tava pensando em usar o vetor e e tentar guardar os subproblemas ou sei lá

unsigned long long fibonacci (unsigned long long n){
    int cont = n, unsigned long long fib[cont];

    if(n < 2)
        return n;
    else if(n == cont)
            return fib[cont];
    else
        fib[cont] = return fibonacci(n-1) + fibonacci(n-2);   
}
2
  • 2
    Recursividade para obter eficiência parece-me um pouco incoerente. Se precisar de eficiência, por que não usa um laço de repetição simples?
    – Woss
    16/09/2019 às 10:33
  • é porque o exercicio pede pra ser resolvido com recursão
    – user66436
    17/09/2019 às 0:10

1 Resposta 1

1

A solução é justamente isso que você propôs: salvar os valores já calculados em um vetor. Essa técnica é conhecida como memoização (ou memoization).

Armazene o vetor de valores antigos em uma variável estática, aí você poderá salvar os dados entre uma chamada da função e outra:

#include <stdio.h>
#define MAX_DEPTH 512

unsigned long long fibonacci (unsigned long long n){
    static unsigned long long max_n = 1;
    static unsigned long long memo[MAX_DEPTH];

    memo[0] = 0;
    memo[1] = 1;

    if (n <= max_n)
        return memo[n];

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    max_n = n;

    return memo[n];
}

int main() {
    int i;
    for (i = 0; i < 10; i++)
        printf("%llu\n", fibonacci(i));
    return 0;
}

Você pode ver que a função é recursiva (fibonacci chama a si mesma), mas agora você só calcula o que ainda não foi calculado. Com isso a complexidade fica a mesma se você executar com um laço de repetição.

2
  • 1
    Cara então eu apliquei essa solução só que o tempo é mesmo de uma recursão normal, eu comparei com uma solução iterativa que ja tinha feito e ela foi instantânea, ao contrário dessa solução, tem alguma sugestão??
    – user66436
    17/09/2019 às 0:33
  • 1
    Eu rodei um puramente recursivo e outro com memoização na minha máquina e vi uma diferença gritante. Tenta mudar o limite superior do loop de 10 para 100 comparando as duas versões e me diz o que você acha. 17/09/2019 às 13:07

Você deve fazer log-in para responder a esta pergunta.