Recursão em Java

Recursão é quando um método chama a si mesmo. É uma forma natural de expressar problemas cuja estrutura se repete em uma escala menor — contagem regressiva, percurso em árvore, cálculo de fatorial, inversão de string.

Todo método recursivo tem duas partes: um caso base que retorna diretamente sem recursar, e um caso recursivo que chama o método em uma parte menor do problema. Errar qualquer uma das partes faz com que o programa produza uma resposta errada ou rode para sempre (até a JVM estourar a pilha).

Primeiro exemplo: fatorial

O fatorial de n é n × (n-1) × (n-2) × … × 1. Por definição, 0! = 1. Essa definição é em si recursiva: n! = n × (n-1)!.

A tradução para Java é direta:

public static int factorial(int n) {
  if (n == 0) return 1;            // base case
  return n * factorial(n - 1);      // recursive case
}

Chamar factorial(4) produz:

factorial(4)
  = 4 * factorial(3)
  = 4 * 3 * factorial(2)
  = 4 * 3 * 2 * factorial(1)
  = 4 * 3 * 2 * 1 * factorial(0)
  = 4 * 3 * 2 * 1 * 1
  = 24

Cada chamada fica na pilha aguardando o retorno da próxima. Quando factorial(0) finalmente retorna 1, as respostas propagam-se de volta pela cadeia.

O caso base é inegociável

Sem um caso base, o método não tem nada para interromper a recursão. O erro clássico:

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

Isso recursa para sempre — ou melhor, até a pilha de chamadas se esgotar e a JVM lançar StackOverflowError. O caso base é o que encerra a cadeia; o caso recursivo é o que avança em direção a ela.

O outro erro clássico é um caso base que a recursão nunca alcança:

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) aqui tentaria factorial(5), factorial(6), … e travaria. A chamada recursiva deve mover o argumento mais próximo do caso base.

Recursão em inteiros: contagem regressiva

Um segundo exemplo simples para clareza — imprimir os números de n até 1:

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) imprime 3, 2, 1. Inverta a ordem para imprimir 1, 2, 3:

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

A mesma recursão, ordem de impressão diferente — porque a chamada recursiva acontece antes da impressão. A lição: o que você faz antes da chamada recursiva ocorre na descida, o que você faz depois ocorre na subida.

Recursão em strings: inversão

Você pode pensar em inverter uma string como "retire o primeiro caractere, inverta o restante, coloque o primeiro caractere no final":

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

Isso é elegante, mas ineficiente — cada chamada recursiva aloca uma nova substring. Um loop com StringBuilder seria mais rápido. A recursão muitas vezes é a expressão mais clara de uma ideia; nem sempre é a implementação mais rápida.

Fibonacci e o custo da recursão

A sequência de Fibonacci é 0, 1, 1, 2, 3, 5, 8, 13, …, definida como fib(n) = fib(n-1) + fib(n-2). A tradução direta:

public static long fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

Isso está correto, mas é exponencialmente lento — fib(40) já roda de forma perceptível, fib(50) é doloroso. A árvore de recursão recalcula os mesmos subproblemas bilhões de vezes (fib(5) sozinho chama fib(2) três vezes). A solução no código real é memoização ou um loop simples.

Memoização mantém a forma recursiva, mas armazena em cache cada resultado na primeira vez em que é calculado, para que cada subproblema seja executado apenas uma vez:

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

Um loop simples elimina completamente a recursão e usa memória constante:

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Saber quando a recursão é a ferramenta errada é tão importante quanto saber quando é a certa.

Recursão vs iteração

Qualquer método recursivo pode ser reescrito como um loop, e qualquer loop pode ser reescrito como recursão — eles são igualmente poderosos. A escolha é sobre clareza e custo:

• Opte pela recursão quando os dados em si são recursivos (árvores, pastas aninhadas, JSON) ou quando a definição recursiva é mais clara do que o loop, como com factorial ou reverse.
• Opte por um loop quando a recursão puder ser profunda o suficiente para arriscar um StackOverflowError, ou quando uma versão iterativa for igualmente legível e evitar o overhead por chamada, como com fib.

Quando os dois são igualmente claros, prefira o loop em Java: ele não tem limite de profundidade de pilha nem custo de frame de chamada.

StackOverflowError

Cada chamada pendente usa um pedaço da pilha da JVM. Com o tamanho de pilha padrão, você geralmente pode aninhar alguns milhares de chamadas antes de as coisas quebrarem:

factorial(100000);    // StackOverflowError

Java não faz otimização de chamada de cauda — mesmo uma chamada recursiva que é a última coisa que o método faz ainda consome um frame de pilha. Se o problema pode exigir recursão muito profunda, mude para um loop ou use um Deque explícito como sua própria pilha.

Um exemplo completo

O que vem a seguir

Você definiu métodos, passou parâmetros, sobrecarregou nomes e usou recursão. O próximo conceito é escopo — quais partes de um método podem ver quais variáveis e o que acontece quando um nome aparece em mais de um lugar. Continue no capítulo de escopo de variáveis.

Prática