Continuando nosso estudo sobre recursividade, vamos nesta aula aprender como calcular o enésimo termo da sequência de FIBONACCI com recursão. O interessante do problema da sequência de FIBONACCI é que sua versão recursiva é mais fácil que a versão iterativa já que a própria definição da sequência de fibonacci diz que n = (n – 1) + (n – 2).

Caso você não conheça ou não se recorde, vamos relembrar aqui o que é esta tal sequência de Fibonaccci.

Imagine uma sequência de números que inicia com os algarismos 0 e 1, assim: 0, 1

O primeiro termo é o zero. O segundo termo é o 1. A partir do terceiro termo, cada novo termo é a soma dos dois termos anteriores, assim:

1º – 0
2º – 1
3º – 2º + 1º = 1
4º – 3º + 2º = 2
5º – 4º + 3º = 3
6º – 5º + 4º = 5
7º – 6º + 5º = 8
…
nº – (n-1)º + (n-2)º

Agora que está claro como é gerada a sequência de Fibonacci, podemos então pensar uma função recursiva para calcular um termo n.

Como nos exemplos anteriores, precisamos pensar em nossos pontos de parada, aquele valor ou valores de n para os quais já sabemos a resposta sem a necessidade de nenhum cálculo ou processamento. Para este caso temos dois possíveis pontos de parada, n = 1 (primeiro termo) ou n = 2 (segundo termo).

Porém, se n for maior que 2, significa que precisamos calcular este termo. Isso pode ser feito aplicando exatamente a definição do problema onde n = (n-1) + (n-2).

Código C para o Fibonacci recursivo

#include <stdio.h>
#include <stdlib.h>

int fibonacci(int n){
    if(n == 1) // primeiro termo
        return 0;
    else{
        if(n == 2) // segundo termo
            return 1;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main () {

    int n;

    printf("Digite um valor maior que zero: ");
    scanf("%d", &n);

    printf("O termo %d eh: %d\n", n, fibonacci(n));

    return 0;
}