Recursão em C

Recursão é uma técnica na qual uma função chama a si própria para resolver um problema.

Nesta lição, aprenderá:

• O que é recursão e como funciona.
• Como implementar funções recursivas.
• A diferença entre recursão e iteração.

O que é recursão?

Recursão ocorre quando uma função chama a si própria para resolver uma parte menor de um problema.

Sintaxe de exemplo:

void function() { function(); // Recursive call }

Toda função recursiva deve ter um caso-base para evitar a recursão infinita.

Exemplo: recursão

Este programa demonstra a recursão ao imprimir os números de 5 a 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Caso-base na recursão

Uma função recursiva deve incluir um caso-base para interromper a recursão.

Exemplo:

if (n == 0) return;

Sem um caso-base, a função chamará a si própria infinitamente, causando um estouro da pilha.

Exemplo: fatorial usando recursão

Este programa calcula o fatorial de um número usando recursão.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Recursão e iteração

A recursão e a iteração (laços) podem produzir os mesmos resultados, mas funcionam de formas diferentes.

Diferenças:

• A recursão usa chamadas de função e requer mais memória.
• A iteração usa laços e, em geral, é mais eficiente.
• A recursão torna o código mais simples em problemas como a travessia de árvores.

Exemplo: Sequência de Fibonacci (Recursiva)

Este programa calcula a sequência de Fibonacci usando recursão.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Quando Usar Recursão?

A recursão é útil para problemas que envolvem:

• Travessia de árvores.
• Retrocesso (por exemplo, para resolver labirintos).
• Problemas matemáticos, como fatoriais e Fibonacci.

Resumo

Nesta lição, você aprendeu:

• O que é recursão e como ela funciona.
• A importância de um caso-base.
• A diferença entre recursão e iteração.

Em seguida, exploraremos arrays e strings em C!