Passei um bom tempo tentando entender o exercício do cálculo do número de Fibonacci na aula 4 do curso C III, mas, mesmo olhando a resolução do instrutor , não consegui compreender como resolvê-lo.
Você está vendo a versão anterior da nova experiência da Alura que estamos preparando para você. Em breve, ela ganha uma identidade visual novinha totalmente pensada em potencializar seus estudos!
Passei um bom tempo tentando entender o exercício do cálculo do número de Fibonacci na aula 4 do curso C III, mas, mesmo olhando a resolução do instrutor , não consegui compreender como resolvê-lo.
Olá gab, tudo bem com você?
Fique tranquilo, pois recursão é um assunto bem complexo e difícil de perceber nas primeiras vezes, com o passar do tempo vai ficando um pouco mais fácil :)
Vou te auxiliar, simulando a execução de um programa ok?
Temos dois pontos principais em uma recursão que temos sempre que pensar:
Em relação a função de fibonacci temos:
Condição de Parada:
if(n == 0) return 0;
if(n == 1) return 1;Sabemos que o fibonacci de 1 e de 0, e não existe fibonacci negativo, então quando chegarmos nesse valor podemos apenas retornar o valor e não chamar novamente
Diminuir o tamanho do problema
return fib(n-1) + fib(n-2);Então aqui a gente está pegando um problema de tamanho n e diminuindo ele para um problema de tamanho n-1 e n-2
Agora vamos a execução do Fibonacci de 4
Então eu chamo a passando n = 4, teremos o seguinte fluxo:
>> fib(4)
n == 0 ? Falso
n == 1? Falso
Retorna o fib(3) + fib(2)Então vamos calcular o fibonacci(3), veja que ainda não tocamos no fib(2)
>> fib(3)
n == 0 ? Falso
n == 1? Falso
Retorna o fib(2) + fib(1)Novamente, vamos calcular o fibonacci(2):
>> fib(2)
n == 0 ? Falso
n == 1? Falso
Retorna o fib(1) + fib(0)E finalmente chegamos na condição de parada, vamos chamar fib(1)
>> fib(1)
n == 0 ? Falso
n == 1? Verdadeiro --> Retorna 1 Mas iremos retornar 1 para quem? para a execução anterior, então voltando para o fib(2) teremos:
Retorna o 1 + fib(0)Vamos calcular o fib(0):
n == 0 ? Verdadeiro --> Retorna 0 Retornamos para o fib(2) novamente:
Retorna 1 + 0 = 1, que é o resultado `fib(2)`E agora voltamos para o fib(3)que foi quem chamou fib(2):
>> fib(3)
n == 0 ? Falso
n == 1? Falso
Retorna o 1 + fib(1)Vamos calcular o fib(1), eu sei que já calculamos, mas o nosso programa não sabe disso:
>> fib(1)
n == 0 ? Falso
n == 1? Verdadeiro --> Retorna 1 Retorna para o fib(3)
>> fib(3)
n == 0 ? Falso
n == 1? Falso
Retorna o 1 + 1 --> 2Então temos fib(3) = 2, voltamos para quem chamou o fib(3) que foi o fib(4):
>> fib(4)
n == 0 ? Falso
n == 1? Falso
Retorna o 2 + fib(2)Teríamos que calcular da mesma forma o fib(2), vou pular isso para não ficar mais enorme, entretanto no final teríamos:
>> fib(4)
n == 0 ? Falso
n == 1? Falso
Retorna o 2 + 1 ---> 3O retorno final do nosso programa de fib(4) é 3
Ou seja uma função recursiva vai chamando a si mesmo quebrando o problema em etapas menores, até chegar no tamanho mínimo, quando chega nisso ela começa a trazer o valor para quem chamou :)
Compreendeu? Qualquer coisa estou a disposição :)
Abraços e Bons Estudos!