Recursión en Java

La recursión es cuando un método se llama a sí mismo. Es una forma natural de expresar problemas cuya estructura se repite a menor escala — contar hacia atrás, recorrer un árbol, calcular un factorial, invertir una cadena.

Todo método recursivo tiene dos partes: un caso base que retorna directamente sin recurrir, y un caso recursivo que llama al método con una parte más pequeña del problema. Si alguna de las dos partes está mal, el programa producirá un resultado incorrecto o se ejecutará indefinidamente (hasta que la JVM desborde la pila).

Un primer ejemplo: factorial

El factorial de n es n × (n-1) × (n-2) × … × 1. Por definición, 0! = 1. Esa definición es en sí misma recursiva: n! = n × (n-1)!.

La traducción a Java es directa:

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

Llamar a factorial(4) produce:

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 llamada queda en la pila esperando que la siguiente retorne. Cuando factorial(0) finalmente retorna 1, las respuestas se propagan de vuelta en la cadena.

El caso base no es negociable

Sin un caso base, el método no tiene nada que detenga la recursión. El error clásico:

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

Esto recurre indefinidamente — hasta que la pila de llamadas se agota y la JVM lanza StackOverflowError. El caso base es lo que termina la cadena; el caso recursivo es lo que avanza hacia ella.

El otro error clásico es un caso base al que la recursión nunca llega:

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

factorial(4) aquí intentaría factorial(5), factorial(6), … y colapsaría. La llamada recursiva debe mover el argumento más cerca del caso base.

Recursión sobre enteros: cuenta regresiva

Un segundo ejemplo trivial para mayor claridad — imprimir los números desde n hasta 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. Intercambia el orden 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);
}

Misma recursión, diferente orden de impresión — porque la llamada recursiva ocurre antes de la impresión. La lección: lo que haces antes de la llamada recursiva se ejecuta en el camino de bajada; lo que haces después se ejecuta en el camino de vuelta.

Recursión sobre cadenas: invertir

Puedes pensar en invertir una cadena como "toma el primer carácter, invierte el resto y coloca el primer carácter al 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".

Esto es elegante pero ineficiente — cada llamada recursiva asigna una nueva subcadena. Un bucle con StringBuilder sería más rápido. La recursión suele ser la expresión más clara de una idea; no siempre es la implementación más rápida.

Fibonacci y el costo de la recursión

La secuencia de Fibonacci es 0, 1, 1, 2, 3, 5, 8, 13, …, definida como fib(n) = fib(n-1) + fib(n-2). La traducción directa:

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

Esto es correcto pero exponencialmente lento — fib(40) ya se nota, fib(50) es doloroso. El árbol de recursión recalcula los mismos subproblemas miles de millones de veces (fib(5) solo llama a fib(2) tres veces). La solución en código real es memoización o un bucle simple.

La memoización conserva la forma recursiva pero almacena en caché cada resultado la primera vez que se calcula, de modo que cada subproblema se ejecuta una sola 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])

Un bucle simple elimina la recursión por completo y usa memoria 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 cuándo la recursión es la herramienta incorrecta es tan importante como saber cuándo es la correcta.

Recursión vs iteración

Cualquier método recursivo puede reescribirse como un bucle, y cualquier bucle puede reescribirse como recursión — son igualmente poderosos. La elección tiene que ver con la claridad y el costo:

• Usa recursión cuando los propios datos son recursivos (árboles, carpetas anidadas, JSON) o cuando la definición recursiva se lee más claramente que el bucle, como con factorial o reverse.
• Usa un bucle cuando la recursión sería tan profunda que podría provocar un StackOverflowError, o cuando una versión iterativa es igual de legible y evita el costo por llamada, como con fib.

Cuando ambas opciones son igual de claras, prefiere el bucle en Java: no tiene límite de profundidad de pila ni costo de marco de llamada.

StackOverflowError

Cada llamada pendiente usa un fragmento de la pila de la JVM. Con el tamaño de pila predeterminado, normalmente puedes anidar unos pocos miles de llamadas antes de que todo falle:

factorial(100000);    // StackOverflowError

Java no realiza optimización de llamada de cola — incluso una llamada recursiva que es lo último que hace el método sigue consumiendo un marco de pila. Si el problema puede requerir una recursión muy profunda, cambia a un bucle o usa un Deque explícito como tu propia pila.

Un ejemplo completo

Qué sigue

Has definido métodos, pasado parámetros, sobrecargado nombres y usado recursión. El siguiente concepto es el ámbito — qué partes de un método pueden ver qué variables, y qué sucede cuando un nombre aparece en más de un lugar. Continúa en el capítulo de ámbito de variables.

Práctica