Arquivo Discussoes de Programacao e Tecnologia 
Bom galera o exercicio que não entendi foi esse ai de cima mas na verdade eu não achei o metodo recursivo tão lento, e nem faço ideia de como montar isso ai em cima se alguem puder dar aquela luz!
desde ja grato
Você não achou o método recursivo lenta ainda. Tenta usar:
calculaFibo(10000);
E veja o desastre…
Quanto à ajuda propriamente dita, vou deixar para alguém mais qualificado (minha lógica não está funcionando hoje…).
a recursividade nesse caso particular, se torna extremamente lenta, pq a calculos duplicados ocorrendo por todo o código…
por exemplo…
calcularFibonacci(5);
isso vai invocar o seguinte
1 - calcularFibonacci(4)
2 - calcularFibonacci(3)
para somar esses dois valores
o numero 1 vai invocar
3 - calcularFibonacci(3)
4 - calcularFibonacci(2)
o numero 2 vai invocar
5 - calcularFibonacci(2)
6 - calcularFibonacci(1)
o numero 3 vai invocar
7 - calcularFibonacci(2)
8 - calcularFibonacci(1)
o numero 4 vai invocar
9 - calcularFibonacci(1)
10 - calcularFibonacci(0)
o numero 5 vai invocar
11 - calcularFibonacci(1)
12 - calcularFibonacci(0)
o numero 6 vai dar a resposta direto = 1
o numero 7 vai calcular
13 - calcularFibonacci(1)
14 - calcularFibonacci(0)
o numero 8 vai dar a resposta direto = 1
o numero 9 vai dar a resposta direto = 1
o numero 10 vai dar a resposta direto = 0
o numero 11 vai dar a resposta direto = 1
o numero 12 vai dar a resposta direto = 0
o numero 13 vai dar a resposta direto = 1
o numero 14 vai dar a resposta direto = 0
…
como vc pode ver… para o numero 5, há 14 chamadas do proprio método…
calcularFibonacci(4) é invocado 1 vez
calcularFibonacci(3) é invocado 2 vezes
calcularFibonacci(2) é invocado 3 vezes
calcularFibonacci(1) é invocado 5 vezes
calcularFibonacci(0) é invocado 3 vezes
fica claro assim, que usando a recursividade o método é muito lento, devido as varias chamadas
Bom blz laviere, mas como aplico array neste caso vou te dizer que isso é uma coisa que usei muito pouco ate hj na minha vida de programador defeito meu na verdade.
1) No capítulo anterior, você deve ter reparado que a versão recursiva para o problema de Fibonacci é lenta
porque toda hora estamos recalculando valores. Faça com que a versão recursiva seja tão boa quanto a
versão iterativa. (Dica: use arrays para isso)
Crie um array suficientemente grande para conter os números de Fibonacci já calculados. Por exemplo, digamos que você queira calcular até N = 100000. Então você tem de criar um array com 100000 + 1 posições.
bom vou te falar como eu penso que é, porem sem escreve o código
1° passo é o que o thiago falou, criar a array, pra guardar os dados…
2° passo é fazer array[0] = 0 e array[1] = 1, pois para esses 2 index na sequencia de fibonacci não há calculos, eles são constantes…
3° passo é modificar o método antigo, que so aplicava a recursividade, no lugar de “return fib(n-1) + fib(n-2);” vc deve verificar se já existe o número na array (basta verificar se a posição do número na array é nula), e se não estiver na array, vc deve guardalo lá
4° passo é retornar o número a partir da array, visto que anteriormente vc já checou se o número estava na array, e não estando vc gravou, agora é so retornar da array…
a diferença vai ser que sempre que vc precisar puxar um número da seqencia de fibonacci todos os números ate ele serão guardados na array, e assim, em caso de chamada dupla, havera apenas uma consulta na array, e um retorno do número, otimizando as chamadas…
ao calcular por exemplo, fib(5), ele deve verificar array[5] igual a null ? se for ele deve fazer esse index ser igual a fib(4) + fib(3) …
note que fib(4) e fib(3) vão fazer os mesmos testes, assim, vão preencher tb os index 4 e 3 da array…
desta forma, apos a chamada de fib(5) vc tera array[5,4,3,2,1,0] já preenchidos…
caso não consiga montar sozinho o código, da uma olhada nesse link, que eu deixei o código la