Hoje, mais um post sobre recursão, abordando a sequência de Fibonacci.
Se você perdeu o meu post sobre recursão, você pode acessá-lo aqui. E também há um sobre a função recursiva que faz a potência de números inteiros, que você pode ver por aqui.
A sequência de Fibonacci é uma sequência matemática definida da seguinte forma:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Como podemos observar, a sequência tem uma característica: Ela começa com 0, 1 e os próximos números são definidos pela soma dos dois anteriores.
Você observa pelas contas:
Dois primeiros: 0, 1
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
...
Tendo isso em mente, podemos definir a seguinte relação matemática:
F(n) =
| 0, se n = 0
| 1, se n = 1
| F(n - 1) + F(n - 2), em outros casos
Utilizando essa definição, facilmente podemos construir uma função recursiva que calcule a sequência de fibonacci, certo?
Pensando em um caso base para nossa recursão, o que temos? Sabemos que quando n = 0 ou n = 1, não precisamos retornar nossa função de novo, e a resposta é o próprio n.
Agora, vamos definir o passo da recursão. Caso n não seja 0 ou 1, qual o valor da resposta? É a soma dos dois anteriores à n, certo? Ou seja:
Pronto! Construimos nosso algoritmo que calcula o número de fibonacci:
E para visualizar a sequência de Fibonacci como demonstrada no começo? Como fazer? Calma, pequeno padawan. Vamos utilizar um laço de repetição para poder calcular os números de fibonacci e imprimi-los na tela.
Agora, pra brincar, é preciso apenas chamar a função fibonacci com o número de elementos da sequência desejado!
fibonacci(5) Irá nos retornar a seguinte sequência:
0, 1, 1, 2, 3
Nessa hora muitas pessoas não compreendem o que exatamente está acontecendo pra que a sequência esteja certa. De onde estão vindo os números?
Tentei ilustrar como ocorrem as chamadas recursivas:
Veja, para cada iteração do laço for, um número fibonacci é calculado, e a função fibo realiza a recursão para este cálculo. Perceba que todas chegam até f(0) ou f(1), e vão retornando seus valores. Como em fibo(2), que precisa da resposta de f(1) + f(0), trazendo a soma 1 + 0, fazendo com que fibo(2) retorne 1.
Esse é um clássico da recursão. Sua solução recursiva é muito elegante, mas como se verifica na imagem, nem tanto eficiente. A solução iterativa é bem menos elegante, mas muito mais eficiente.
Postarei a solução iterativa em breve!
Até a próxima!
