Execução do Algoritmo de Fibonacci Recursivo
Last updated
Was this helpful?
Last updated
Was this helpful?
Vamos considerar como exemplo a implementação do algoritmo de Fibonacci de maneira recursiva:
A memória no computador possui um endereço e um valor. Para fins didáticos, vamos supor que esta memória seja sequencial, iniciando no endereço 0x01 e que possui uma etiqueta, referente ao nome da variável:
O programa irá executar a última linha do código, reservando um espaço na memória para a variável e definido o retorno da função como sendo seu valor:
Na memória fica:
Para saber qual valor de fibonacci(5), a função fibonacci é executada:
A função fibonacci é chamada com parâmetro n = 5;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(4) + fibonacci(3);
Ou seja, o valor de fibonacci(5) será fibonacci(4) + fibonacci(3). Então na memória, ficaria:
Então, o programa irá tentar primeiro calcular o valor de fibonacci(4), pois a expressão é analisada da esquerda para a direita:
A função fibonacci é chamada com parâmetro n = 4;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(3) + fibonacci(2);
Ou seja, o valor de fibonacci(4) será fibonacci(3) + fibonacci(2). Então na memória, ficaria:
Então, para saber o valor de fibonacci(4), o programa precisa saber o valor de fibonacci(3) e fibonacci(2). Analisando da esquerda para a direita, primeiro é calculado fibonacci(3):
A função fibonacci é chamada com parâmetro n = 3;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(2) + fibonacci(1);
Ou seja, o valor de fibonacci(3) será fibonacci(2) + fibonacci(1). Então na memória, ficaria:
A mesma lógica: para saber o valor de fibonacci(3), antes é necessário saber o valor de fibonacci(2) e fibonacci(1). Da esquerda para a direita, calcula-se o valor de fibonacci(2):
A função fibonacci é chamada com parâmetro n = 2;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(1) + fibonacci(0);
Ou seja, o valor de fibonacci(2) será fibonacci(1) + fibonacci(0). Então na memória, ficaria:
Para calcular o valor de fibonacci(2) então é preciso de fibonacci(1) e fibonacci(0). Da esquerda para a direita, calcula-se primeiro fibonacci(1):
A função fibonacci é chamada com parâmetro n = 1;
Verifica-se se n é menor ou igual a 1. Verdadeiro;
Retorne o valor de n (1);
Neste ponto, a recursividade é interrompida brevemente, pois o valor não depende mais de uma outra chamada da função. Assim, na memória fica:
Assim, tendo o valor de fibonacci(1), este é substituído em fibonacci(2):
Mas ainda é necessário calcular o valor de fibonacci(0):
A função fibonacci é chamada com parâmetro n = 0;
Verifica-se se n é menor ou igual a 1. Verdadeiro;
Retorne o valor de n (0);
Então na memória fica:
Este valor é prontamente substituído no valor de fibonacci(2):
O valor de fibonacci(2) é obtido somando 1+0 = 1 e é substituído em fibonacci(3):
Para calcular o valor final de fibonacci(3) é preciso o valor de fibonacci(1) novamente, então é feito novamente a chamada:
A função fibonacci é chamada com parâmetro n = 1;
Verifica-se se n é menor ou igual a 1. Verdadeiro;
Retorne o valor de n (1);
Ficando na memória:
Este valor é prontamente substituído em fibonacci(3), ficando:
O valor de fibonacci(3) então valerá 1+1 = 2, sendo substituído em fibonacci(4):
Mas novamente é preciso o valor de fibonacci(2), então:
A função fibonacci é chamada com parâmetro n = 2;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(1) + fibonacci(0);
Ficando na memória:
Já sabemos que fibonacci(1) retornará 1 e fibonacci(0) retornará 0, então para simplificar, colocarei direto seus valores em fibonacci(2):
Ficando o valor de fibonacci(2) igual a 1+0 = 1, sendo prontamente substituído em fibonacci(4):
Assim, o valor de fibonacci(4) ficará igual à 2+1 = 3, sendo prontamente substituído em fibonacci(5):
Para calcular ainda o valor final de fibonacci(5) é necessário o valor de fibonacci(3):
A função fibonacci é chamada com parâmetro n = 3;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(2) + fibonacci(1);
Ou seja, o valor de fibonacci(3) será fibonacci(2) + fibonacci(1):
Analisando da esquerda para a direita, novamente calcula-se o valor de fibonacci(2):
A função fibonacci é chamada com parâmetro n = 2;
Verifica-se se n é menor ou igual a 1. Falso, executa o else;
Retorne o valor de fibonacci(1) + fibonacci(0);
Ficando na memória:
Como já sabemos, fibonacci(1) vale 1 e fibonacci(0) vale 0, então substituindo os valores:
Resultando em fibonacci(2) igual a 1+0 = 1, sendo prontamente substituído em fibonacci(3):
Falta ainda calcular o valor de fibonacci(1), que já sabemos que vale 1:
Assim, o valor de fibonacci(3) será 1+1 = 2, sendo prontamente substituído em fibonacci(5):
Finalmente, o valor de fibonacci(5) valerá 3+2 = 5, sendo substituído prontamente em resultado:
Portanto, quando for executado:
O valor de resultado será 5. Valor este que pode ser comprovado executando o código.
