Por favor, alguém poderia me orientar com o teste de mesa da série de fibonacci recursiva? Ou ainda indicar um link pontual sobre o assunto? Já fiz vários esboços do teste, porém não está dando certo.
O algoritmo abaixo funciona perfeitamente, estou estudando FJ11, porém preciso entender o conceito.
int calculaFibonacci(int i){
if(i <= 1){
return i;
}
return calculaFibonacci(i-2) + calculaFibonacci(i-1);
}
Impressão: 0,1,1,2,3,5,8,13,21,34,55,89,144…
vamos la
int calculaFibonacci(int i){
if(i <= 1){
return i;
}
return calculaFibonacci(i-2) + calculaFibonacci(i-1);
}
faz com papel e caneta o que acontece quando vc chama assim
calculaFibonacci(0);
calculaFibonacci(1);
calculaFibonacci(2);
calculaFibonacci(3);
calculaFibonacci(4);
os dois primeiros sao faceis né? vamos ver pro numero 2?
int calculaFibonacci(2){
if(2 <= 1){
return i; // nao
}
return calculaFibonacci(2-2) + calculaFibonacci(2-1);
}
vejamos
calculaFibonacci(2-2) + calculaFibonacci(2-1);
é
calculaFibonacci(0) + calculaFibonacci(1);
que vc ja calculou antes.
Tiago Peczenyj, obrigado pela orientação!
Pelo que entendi, para cada resultado referente a um parâmetro passado para a função, o mesmo fica armazenado no cache… Por exemplo: quando a função calculaFibonacci(0) retornou zero, calculaFibonacci(1) retornou um, esses valores ficam armazenados na memória, então, quando em tempo de execução eu chamar novamente a função calculaFibonacci passando o parâmetro (1), automaticamente a aplicação recuperará o resultado já adquirido para esse parâmetro.
Está correto? Os resultados para cada parâmetro ficam mesmo no cache?
Obs.: O motivo de anteriormente não conseguir concluir o teste de mesa, não chegando na sequencia correta, embora o algoritmo está correto, é que toda vez que passava um parâmetro - no caso, calculaFibonacci(2-1=1), por exemplo - entrava na função e fazia toda a soma novamente.
Ola
não existe cache. só existe se vc implementar.
o que acontece é que vc tem uma pilha de execuções. quando vc pede calculaFibonacci(1024) isso vai empilhar diversas execuções recursivas ate que vc pare de chamar a função e retorne um valor ( como nos casos do parametro 1 e 0 ).
essa pilha é implicita e custa memoria. se vc tentar algo muito grande vc vai ter um estouro de pilha ( uma exception vinda da JVM ).
em algumas linguagens funcionais sim, vc pode admitir que existe algum cache entre as funções, mas pq são funções no sentido matematico ( stateless, só depende dos parametros, etc). em linguagens imperativas isso dificilmente acontece a menos q vc use explicitamente uma forma de faze-lo.