Teste de Mesa - Série Fibonacci Recursiva

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.