Question

Seja a seqüência de Fibonacci: {0,1,1,2,3,5,...}. Por que a implementação
recursiva da série é considerada uma solução ruim ? Prove.

Answer 1

Resposta:

O fibonacci recursivo calcula os mesmos valores várias vezes, e é por isso que é tão ineficiente.

Explicação:

Por exemplo,

F(5)=F(4)+F(3) = F(3)+F(2)+F(3) = F(2)+F(1)+F(2) + F(3) = F(2)+F(1)+F(2)+F(2)+F(1)

Calculamos o mesmo valor várias vezes para chegar a F(5). Fica pior quando calculamos o último número da série.