Recursividade (Conceito para qualquer linguagem)

Sim, seu raciocínio está correto. Só vale lembrar que quando chega em Fibonacci(1) e Fibonacci(0), ele entra no se x = 1 ou x = 0.

Mas vale lembrar que Fibonacci recursivo é o pior e mais ineficiente jeito de resolver o problema. Isso porque são geradas muitas chamadas redundantes.

Por exemplo, se F for a sua função recursiva, chamar F(10) faz o seguinte:

F(10) = F(9)                           +   F(8)
F(10) = F(8)          +   F(7)         +   F(7)          +  F(6)
F(10) = F(7) + F(6)   +   F(6) + F(5)  +   F(6) + F(5)   +  F(5) + F(4)
....

Repare que F(8) é calculada duas vezes, F(7) 3 vezes, e assim por diante. Quanto maior o número inicial, mais chamadas recursivas - e neste caso, redundantes - serão feitas, e isso cresce exponencialmente conforme o valor inicial.

Recursão é um conceito importante e deve ser aprendido, mas mais importante ainda é saber quando não usar. No caso de Fibonacci, o pessoal usa pra ensinar porque a definição matemática é recursiva e parece que fica mais “didático”. Mas ao transpor isso para código, se torna uma solução ruim, e um loop resolve de maneira muito melhor e mais simples.

Pra entender recursividade, primeiro você precisa entender recursividade.

Sem dúvida a forma iterativa de se resolver esse problema é melhor. Como você falou, é didática, eu já tinha lido que a recursão muita das vezes pode deixar o código mais bonito de se ver porém pode não ser eficiente, não tinha ainda entendido, mas no exemplo de fibonacci, consigo ver que a recursão não é a melhor estratégia. Mesmo assim, achei bem interessante o fato de cada chamada da função fazer mais 2 chamadas recursivas. Obrigado novamente!

Só parece algo do outro mundo, mas não é. É a base da computação e como uma prova formal por indução funciona na matemática. A forma de se descrever uma recursão matematicamente é chamada de fórmula de recorrência, relação de recorrência ou só recorrência, que é quando na definição de uma função a própria função aparece novamente. É algo que é definido em termos de si mesmo. Fibonacci ficaria algo como:

image837×115 8.5 KB

Além disso, existem diversos tipos de recursão dependendo do contexto. Simples, composta, direta, indireta, mais à esquerda, mais à direita…

Interessante consegui entender. Eu estou no segundo ano de faculdade e minha matemática de escola foi muito fraca mas consigo visualizar nessa descrição matemática o funcionamento do algoritmo que eu deixei acima. Uma das primeiras coisas que ganhou sentido pra mim quando entrei na faculdade foi a aplicabilidade de funções, que na escola eu não via sentido. Obrigado pela resposta, não sabia dos outros tipos de recursão vou dar uma estudada depois.

Infelizmente o ensino básico no nosso país é um lixo, salvo escolas federais ou particulares. Claro que os alunos tem que querer ir atrás tbm, mas se vc não tem um professor que consegue ensinar o básico de forma minimamente decente, fica difícil ter vontade ou alguma motivação para ir aprender mais. Continue assim.