Desafio C

Sequência de Fibonacci com recursão e passagem por valor

Enunciado

Escreva uma função recursiva fibonacci que retorna o n-ésimo número de Fibonacci (considerando fib(0) = 0 e fib(1) = 1). No main, leia um inteiro n (0 ≤ n ≤ 20), chame a função e imprima Fibonacci(n) = valor. Além disso, crie uma função imprime_sequencia que recebe um inteiro n e imprime todos os termos de fib(0) até fib(n) separados por espaço, usando a função fibonacci.

Requisitos

  • fibonacci deve ser recursiva e tratar os casos base 0 e 1.
  • imprime_sequencia deve usar fibonacci para gerar os termos.
  • O main deve ler n e imprimir a linha Fibonacci(n) = valor seguida da sequência.

Código inicial

#include <stdio.h>

/* Protótipos */
int fibonacci(int n);
void imprime_sequencia(int n);

int main(void) {
    int n;
    scanf("%d", &n);
    /* Chame as funções e imprima */
    return 0;
}

/* Defina fibonacci recursiva aqui */

/* Defina imprime_sequencia aqui */

Saída esperada

Fibonacci(6) = 8
0 1 1 2 3 5 8
Ver dica

A sequência de Fibonacci é definida por F(0)=0, F(1)=1 e F(n)=F(n-1)+F(n-2). Use um laço para imprimir os termos.

Mostrar solução 
#include <stdio.h>

/* Protótipos */
int fibonacci(int n);
void imprime_sequencia(int n);

int main(void) {
    int n;
    scanf("%d", &n);
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    imprime_sequencia(n);
    return 0;
}

/* Função recursiva que retorna o n-ésimo número de Fibonacci */
int fibonacci(int n) {
    if (n == 0) return 0;      /* caso base 0 */
    if (n == 1) return 1;      /* caso base 1 */
    return fibonacci(n - 1) + fibonacci(n - 2); /* chamadas recursivas */
}

/* Imprime a sequência de Fibonacci de 0 até n */
void imprime_sequencia(int n) {
    for (int i = 0; i <= n; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
}

Passo a passo

  1. Declaramos os protótipos de fibonacci e imprime_sequencia antes do main.
  2. No main, lemos n com scanf.
  3. Imprimimos Fibonacci(n) = valor chamando fibonacci(n).
  4. Chamamos imprime_sequencia(n) para imprimir todos os termos de 0 a n.
  5. A função fibonacci trata os casos base: se n == 0 retorna 0; se n == 1 retorna 1.
  6. Para os demais, retorna a soma das duas chamadas recursivas anteriores.
  7. A função imprime_sequencia usa um laço for de 0 a n e chama fibonacci(i) para cada termo, imprimindo com espaço.
  8. Ao final, imprime uma quebra de linha.

Por que funciona

A recursão em fibonacci segue exatamente a definição matemática: F(0)=0, F(1)=1 e F(n)=F(n-1)+F(n-2). Cada chamada se divide em duas outras até atingir os casos base. A passagem por valor garante que cada chamada tenha sua própria cópia de n. A função imprime_sequencia reutiliza fibonacci para gerar cada termo, demonstrando a composição de funções.

Erros comuns

  • Esquecer um dos casos base: se apenas n == 0 for tratado, fibonacci(1) chamará fibonacci(0) e fibonacci(-1), causando recursão infinita. Sempre trate n == 0 e n == 1.
  • Trocar a ordem das chamadas: fibonacci(n - 2) + fibonacci(n - 1) também funciona, mas a ordem natural é n-1 e n-2.
  • Não imprimir o espaço após cada termo: o enunciado pede termos separados por espaço, então use "%d " dentro do laço.
  • Esquecer a quebra de linha final: printf("\n"); ao final da sequência.

Outra forma de resolver

Versão iterativa de fibonacci (mais eficiente, sem recursão):

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

É preferível para valores grandes de n, pois evita a explosão exponencial de chamadas.

Saída esperada

Fibonacci(6) = 8
0 1 1 2 3 5 8