Execução do Algoritmo de Fibonacci Recursivo

Vamos considerar como exemplo a implementação do algoritmo de Fibonacci de maneira recursiva:

def fibonacci(n: int) -> int:
  if n <= 1:
    return n
  else:
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))

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:

resultado = fibonacci(5)

Na memória fica:

Passo 1

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:

Passo 2

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:

Passo 3

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:

Passo 4

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:

Passo 5

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:

Passo 6

Assim, tendo o valor de fibonacci(1), este é substituído em fibonacci(2):

Passo 7

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:

Passo 8

Este valor é prontamente substituído no valor de fibonacci(2):

Passo 9

O valor de fibonacci(2) é obtido somando 1+0 = 1 e é substituído em fibonacci(3):

Passo 10

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:

Passo 11

Este valor é prontamente substituído em fibonacci(3), ficando:

Passo 12

O valor de fibonacci(3) então valerá 1+1 = 2, sendo substituído em fibonacci(4):

Passo 13

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:

Passo 14

Já sabemos que fibonacci(1) retornará 1 e fibonacci(0) retornará 0, então para simplificar, colocarei direto seus valores em fibonacci(2):

Passo 15

Ficando o valor de fibonacci(2) igual a 1+0 = 1, sendo prontamente substituído em fibonacci(4):

Passo 16

Assim, o valor de fibonacci(4) ficará igual à 2+1 = 3, sendo prontamente substituído em fibonacci(5):

Passo 17

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):

Passo 18

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:

Passo 19

Como já sabemos, fibonacci(1) vale 1 e fibonacci(0) vale 0, então substituindo os valores:

Passo 20

Resultando em fibonacci(2) igual a 1+0 = 1, sendo prontamente substituído em fibonacci(3):

Passo 21

Falta ainda calcular o valor de fibonacci(1), que já sabemos que vale 1:

Passo 22

Assim, o valor de fibonacci(3) será 1+1 = 2, sendo prontamente substituído em fibonacci(5):

Passo 23

Finalmente, o valor de fibonacci(5) valerá 3+2 = 5, sendo substituído prontamente em resultado:

Portanto, quando for executado:

resultado = fibonacci(5)

O valor de resultado será 5. Valor este que pode ser comprovado executando o código.

PreviousExemplos Next6. Algoritmos de Busca

Last updated 5 years ago

Was this helpful?