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!
Olá Guilherme,
ResponderExcluirVale a pena comentar que há uma possibilidade para fazer o fibonacci recursivo "eficiente". Só precisa memorizar o resultado resultante de um f(x) quando ele é calculado pela primeira vez. Quando for calcular um f(y) primeiro verifica se este valor já foi calculado anteriormente.
Obrigado pelo comentário!
ResponderExcluirRealmente há outras formas de se fazer esse algoritmo. Essa que você citou leva à programação dinâmica, que é bem mais eficiente que a que coloquei no post. É que nesse caso minha intenção não era focar na eficiência. Mas vou anotar como sugestão para um próximo post. :)
Abraço!
Guilherme meus parabens. topico muito bem escrito e de facil entendimento.
ResponderExcluirja tinha feito essa sequencia em javascript, li seu esse post e lembrei muito rapido pela eficiencia na explicação..
parabens msmo;
sou professor particular de programação e ja estou usando seu blog como referencia
parabens...
Guilherme parabéns pelo post, eu estudo sistemas de informação e tive que fazer esse exercício ontem, mais não sabia como fazer, e fui procurar no google uma forma de fazer que eu entendesse e achei seu blog, me ajudo muito. Vlw.
ResponderExcluir