int fib (int n, int* a) { /* devolve fibonacci de n e coloca fibonacci de n-1 na variável a */
if (n == 0) return 1;
else if (n == 1) {
*a = 1;
return 1;
}
else {
int n1, n2;
n1 = fib(n-1, &n2);
*a = n1;
return n1 + n2;
}
}
int fibonacci (int n) {
int a;
return fib(n, &a);
}
Como eu prometi pro pessoal no plantão da noite, a versão recursiva O( n ) do cálculo do n-ésimo elemento da sequência de Fibonacci:
bom se ele converte em linear ou não, não sei mas que realmente o tempo de execuçao é identicado ao do linear é.
Para ambos calcularem o fibonacci de 46 levam 0.008s enquanto o recursivo tradicional demora 20s.
Para ambos calcularem o fibonacci de 46 levam 0.008s enquanto o recursivo tradicional demora 20s.