Métodos Recursivos em Java

A recursão é uma poderosa técnica de programação onde um método, para resolver um problema complexo, chama a si mesmo com uma versão um pouco mais simples do mesmo problema.

Imagine que você tem uma boneca russa (matryoshka). Para abri-la completamente, você abre a primeira, encontra uma boneca menor dentro, e para abrir essa boneca, você repete exatamente o mesmo processo. Você continua até encontrar a última boneca, a menor de todas, que não pode ser aberta.

Os Dois Pilares da Recursão

Para que um método recursivo não se execute infinitamente, ele precisa, obrigatoriamente, ser construído sobre dois pilares:

1. O Caso Base (ou Condição de Parada): É a versão mais simples do problema, que pode ser resolvida imediatamente, sem mais chamadas recursivas. É a menor boneca que não abre. Esta é a condição que para a recursão.
2. A Chamada Recursiva: É o passo onde o método chama a si mesmo, mas alterando o argumento para se aproximar um pouco mais do Caso Base. É o ato de abrir uma boneca para encontrar a próxima, menor.

Exemplo: O Fatorial de um Número

O fatorial de n (n!) é a multiplicação de todos os números de 1 até n. Por exemplo, 3! = 3 * 2 * 1.

A lógica recursiva é: o fatorial de n é n multiplicado pelo fatorial de n-1.

static int factorial(int x) {
    // PILAR 1: O CASO BASE
    // O problema mais simples que sabemos resolver diretamente é o fatorial de 1, que é 1.
    if (x == 1) {
        return 1;
    }

    // PILAR 2: A CHAMADA RECURSIVA
    // Reduzimos o problema: o fatorial de x é x multiplicado pelo fatorial de (x - 1).
    return x * factorial(x - 1);
}

Como o Computador "Pensa" Nisso?

Quando factorial(3) é chamado, o computador empilha as tarefas:

1. factorial(3) é chamado. Ele não pode retornar 3 * ??? ainda, pois precisa do resultado de factorial(2). Ele pausa e espera.
2. factorial(2) é chamado. Ele também precisa do resultado de factorial(1). Ele pausa e espera.
3. factorial(1) é chamado. Ele atinge o caso base! Ele não faz novas chamadas e retorna o valor 1 diretamente.
4. A chamada de factorial(2) que estava em espera agora recebe o 1. Ela calcula 2 * 1 e retorna 2.
5. A chamada original de factorial(3) que estava em espera agora recebe o 2. Ela calcula 3 * 2 e retorna 6.

O resultado final é 6.

Quando Usar Recursão?

Embora poderosa, a recursão não é sempre a melhor escolha.

• Para tarefas lineares simples (como calcular um fatorial ou uma soma), um laço for ou while é frequentemente mais eficiente, usando menos memória e sendo mais rápido.
• O verdadeiro poder da recursão brilha em problemas que são inerentemente hierárquicos ou que se dividem em subproblemas idênticos. Nesses cenários, a solução recursiva pode ser muito mais limpa e legível do que uma solução com múltiplos laços.

📝 Exercícios

Tarefa 1: O Erro Infinito

O método abaixo foi criado para imprimir uma contagem regressiva, mas contém um erro crítico que viola uma das regras da recursão.

public class Countdown {
    public static void main(String[] args) {
        // Cuidado: executar este código causará um erro!
        countDownFrom(5);
    }

    static void countDownFrom(int number) {
        System.out.println(number);
        // O método sempre se chama com um número menor, sem parar.
        countDownFrom(number - 1);
    }
}

Pergunta: O que acontecerá quando este método for chamado? Qual pilar essencial da recursão foi quebrado?

if (number <= 0) {
    return; // Para a recursão
}

Tarefa 2: Soma Recursiva

Complete o método recursivo sumUpTo para que ele calcule a soma de todos os números inteiros de 1 até o número fornecido. Por exemplo, sumUpTo(4) deve retornar 10 (que é 4 + 3 + 2 + 1).

public class RecursiveSum {
    public static void main(String[] args) {
        int result = sumUpTo(4);
        System.out.println("A soma de 1 até 4 é: " + result); // Saída esperada: 10
    }

    static int sumUpTo(int n) {
        // 1. Defina o Caso Base (a versão mais simples do problema).


        // 2. Defina a Chamada Recursiva (o passo que se aproxima do caso base).

    }
}

public class RecursiveSum {
    public static void main(String[] args) {
        int result = sumUpTo(4);
        System.out.println("A soma de 1 até 4 é: " + result); // Saída esperada: 10
    }

    static int sumUpTo(int n) {
        // 1. Caso Base: Se n for 1, a soma até ele é o próprio 1.
        if (n <= 1) {
            return 1;
        }

        // 2. Chamada Recursiva: Retorna n + a soma de todos os números abaixo dele.
        return n + sumUpTo(n - 1);
    }
}