Recursión de cola: la optimización que evita el stack overflow

En el artículo anterior vimos que cada llamada recursiva abre un nuevo stack frame y que eso limita la profundidad práctica de la recursión. Hay una variante especial —la recursión de cola, o tail call recursion— que, en algunos lenguajes, evita ese crecimiento del stack. El compilador reconoce el patrón y convierte la llamada recursiva en algo casi idéntico a un bucle, reutilizando el mismo frame en lugar de apilar uno nuevo.

Es una idea elegante, pero con una trampa: Java y PHP no la optimizan. Saber que existe y reconocer cuándo aplica sigue siendo útil, pero la conclusión práctica para los lenguajes que probablemente usas todos los días es distinta a lo que dice el folklore.

Qué es una llamada de cola

Una llamada es "de cola" (tail call) cuando es la última operación que ejecuta la función antes de retornar. No "casi la última", ni "la que aparece al final del código": realmente la última, sin ninguna operación pendiente después.

Compara estas dos versiones de factorial:

// Recursión NO de cola
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);   // Hay una multiplicación pendiente
}

Aunque la llamada a factorial(n - 1) aparece al final del código, no es una llamada de cola: cuando esa llamada retorna, todavía hay que multiplicarla por n. El frame actual tiene que permanecer vivo en el stack para guardar n y hacer la multiplicación después.

Para convertirla en tail-recursive, hay que pasar el acumulador como parámetro:

// Recursión de cola (versión equivalente)
int factorial(int n) {
    return factorialHelper(n, 1);
}
int factorialHelper(int n, int acumulado) {
    if (n == 0) return acumulado;
    return factorialHelper(n - 1, acumulado * n);  // Última operación: no hay nada pendiente
}

Ahora, cuando factorialHelper llama a factorialHelper, no hay ningún trabajo pendiente después. El frame actual podría literalmente ser reemplazado por el de la nueva llamada sin perder información.

Cómo se vería en memoria (con y sin TCO)

La optimización se llama Tail Call Optimization (TCO) o tail call elimination. Cuando el compilador la aplica, transforma el código de esto:

frame(n=5, acc=1)    ← ocupa stack
  frame(n=4, acc=5)
    frame(n=3, acc=20)
      frame(n=2, acc=60)
        frame(n=1, acc=120)
          frame(n=0, acc=120) ← retorna

A algo equivalente a esto:

frame(n=5, acc=1)    ← se reescribe en el lugar
frame(n=4, acc=5)
frame(n=3, acc=20)
frame(n=2, acc=60)
frame(n=1, acc=120)
frame(n=0, acc=120)  ← retorna

Un solo frame, reutilizado. Memoria de stack: O(1) en lugar de O(n). El resultado es esencialmente un bucle disfrazado de recursión.

Qué lenguajes sí optimizan TCO

• Scheme: el estándar del lenguaje exige TCO. Es la patria de la recursión.

• Haskell, OCaml, Scala: TCO garantizado por el compilador (en Scala lo marcas con @tailrec).

• Kotlin: con la palabra reservada tailrec delante de fun.

• Lua, Erlang, Elixir: TCO por diseño.

• C y C++: compiladores modernos (GCC, Clang) aplican TCO con -O2, pero no es un estándar garantizado.

• JavaScript: fue prometido en ES6 con "proper tail calls" pero solo Safari lo implementó. Chrome, Firefox y Node lo descartaron.

Qué lenguajes NO optimizan TCO

• Java: la JVM no elimina tail calls. Hay razones históricas relacionadas con la inspección del stack para seguridad, y aunque existen propuestas desde hace años, ninguna llegó a producción.

• PHP: tampoco aplica TCO. Una recursión profunda tirará igual sea de cola o no.

• Python: Guido van Rossum decidió explícitamente no implementar TCO. El razonamiento: los stack traces se vuelven engañosos y la recursión profunda suele ocultar código mal estructurado.

Esto tiene implicaciones muy concretas: escribir tu factorial en versión tail-recursive en Java no te salva del StackOverflowError. Si n es 50,000, el código va a explotar igual que la versión no-tail-recursive.

// Esto NO se salva del stack overflow en Java, por más "tail-recursive" que se vea
int factorial(int n, int acc) {
    if (n == 0) return acc;
    return factorial(n - 1, acc * n);
}

factorial(100000, 1); // StackOverflowError garantizado

Entonces, ¿para qué te sirve conocerla?

Tres razones, incluso si programas en Java y PHP:

1. Reconocerla en código de otros lenguajes

Vas a encontrar recursión de cola en artículos, cursos de CS y código de Scala, Kotlin, Elixir. Saber identificar el patrón te permite leer ese código sin tropezar.

2. Reescribir tu código a iterativo con la misma estructura

Toda recursión de cola se puede convertir mecánicamente en un while. Es tan directo que muchos compiladores lo hacen automáticamente. Puedes hacerlo tú a mano en Java o PHP:

// Versión tail-recursive (rompe con n grande)
int factorial(int n, int acc) {
    if (n == 0) return acc;
    return factorial(n - 1, acc * n);
}

// Versión iterativa equivalente (segura)
int factorial(int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n--;
    }
    return acc;
}

La traducción es mecánica: los parámetros se vuelven variables locales, y el paso recursivo se vuelve el cuerpo del bucle. Si ves que tu lenguaje no optimiza TCO, aplica esta conversión directamente.

3. Kotlin/Scala/Clojure están cada vez más presentes en el ecosistema JVM

Si tu stack incluye microservicios en Kotlin o pipelines en Scala, escribir tailrec correctamente te da lo mejor de los dos mundos: código que se lee como recursión pero corre como bucle.

// Kotlin: el compilador verifica que realmente sea tail-recursive
tailrec fun factorial(n: Int, acc: Long = 1): Long =
    if (n == 0) acc else factorial(n - 1, acc * n)

Si pones tailrec y el código no está en forma de cola, el compilador de Kotlin te lo marca como error. Es la forma más segura de usar la optimización.

Cómo reconocer si tu recursión es de cola

Pregúntate: cuando la función retorna el resultado de la llamada recursiva, ¿hay alguna operación pendiente?

// NO de cola: hay una suma pendiente
return n + recursiva(n - 1);

// NO de cola: hay una multiplicación pendiente
return n * recursiva(n - 1);

// NO de cola: hay una construcción de lista pendiente
return prepend(n, recursiva(n - 1));

// Sí de cola: el return es la llamada misma
return recursiva(n - 1, acumulado * n);

La pista visual: si lo único que hay en el return es la llamada recursiva —sin operadores, sin envoltura, sin new—, es de cola.

Recursión de cola con múltiples caminos

Una función puede tener varias ramas, y basta con que cada una termine en una llamada de cola (o en un valor) para ser tail-recursive.

tailrec fun buscar(lista: List<Int>, valor: Int): Int {
    if (lista.isEmpty()) return -1
    if (lista.first() == valor) return 0  // valor inmediato: ok
    return 1 + buscar(lista.drop(1), valor)  // ¡cuidado! el "1 +" la descalifica
}

Este ejemplo no es tail-recursive por el 1 +. Para arreglarlo, mueve el acumulador al parámetro:

tailrec fun buscar(lista: List<Int>, valor: Int, idx: Int = 0): Int {
    if (lista.isEmpty()) return -1
    if (lista.first() == valor) return idx
    return buscar(lista.drop(1), valor, idx + 1)
}

Ahora sí: cada retorno es o un valor inmediato o una llamada recursiva pura.

Errores comunes

1. Asumir que tu lenguaje optimiza TCO cuando no lo hace

Ya lo vimos: Java, PHP y Python van a romper igual. No te fíes del folklore de "si está en forma de cola, es seguro". Verifica con la documentación del lenguaje.

2. Código "en apariencia" de cola pero con operación pendiente

El clásico return n * rec(n - 1). Se ve limpio, se ve como cola, pero no lo es. Revisa: ¿qué operadores hay alrededor de la llamada recursiva en el return?

3. Confundir TCO con "elimina todo el overhead de la recursión"

Incluso con TCO, el compilador sigue teniendo que evaluar la llamada. Lo que se ahorra es el crecimiento del stack, no las operaciones de la función. El código es igual de lento que el bucle equivalente, solo que no desborda.

4. Confundir recursión mutua de cola con recursión simple

Si f llama a g en posición de cola y g llama a f en posición de cola, algunos lenguajes sí lo manejan (Scheme sí; Kotlin con tailrec no, porque solo optimiza auto-llamadas). Verifica con la documentación del compilador.

Cuándo usarla en la práctica

Si programas en Java o PHP: escribe iterativo directamente. La ganancia de claridad por usar recursión de cola no compensa el riesgo de stack overflow.

Si programas en Kotlin, Scala, Elixir, Scheme o similares: úsala libremente para recursión lineal donde quieras preservar el look declarativo. Marca tailrec/@tailrec para que el compilador te avise si la rompes.

Si escribes código educativo o pseudocódigo: menciona que el patrón existe y que la conversión mecánica a iterativo es siempre posible. Es parte del arsenal que un programador debe reconocer.

Resumen

Una llamada recursiva es de cola cuando es la última operación antes de retornar, sin trabajo pendiente. Los lenguajes que optimizan TCO reemplazan el stack frame actual en lugar de apilar uno nuevo, reduciendo la memoria de O(n) a O(1). Java y PHP no aplican esta optimización; Kotlin, Scala, Scheme y Elixir sí.

Incluso si tu lenguaje no la optimiza, reconocer el patrón es útil: toda recursión de cola se traduce mecánicamente a un bucle while, y esa es la versión que debes usar cuando la profundidad pueda desbordar el stack.

En el siguiente artículo pasamos a la herramienta que te permite hablar con rigor sobre "cuánto tarda" un algoritmo: la notación Big-O.