La Recursividad Explicada: Cuándo Usarla y Cuándo No

Una función que se llama a sí misma tiene una profundidad máxima, y es más pequeña de lo que la mayoría espera: 1.000 llamadas en CPython por defecto, entre 10.000 y 15.000 en Node y en los motores de los navegadores, según cuánto pese cada frame. Pasarse de ese límite no hace que el programa vaya más lento: lo hace fallar. Python lanza RecursionError: maximum recursion depth exceeded; JavaScript lanza RangeError: Maximum call stack size exceeded.

Ambos errores tienen la misma causa, y en cuanto la ves sabes cuándo la recursividad es la herramienta correcta y cuándo se convierte en un riesgo.

Qué le hace realmente una función recursiva a la pila de llamadas

Cada llamada a una función pone un frame en la pila: los argumentos, las variables locales, la dirección a la que volver. Una llamada normal retorna y su frame se elimina. Una llamada recursiva todavía no puede retornar, porque está esperando la llamada que acaba de hacer, así que cada frame permanece en la pila hasta que el de abajo termina.

1
2
3
4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4) construye cuatro frames en la pila antes de que ninguno produzca un valor:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # caso base, la pila deja de crecer

Solo cuando factorial(1) retorna 1 la pila se deshace: 2 * 1, luego 3 * 2, luego 4 * 6, resultado 24.

Dos piezas hacen que esto funcione. El caso base (n <= 1) detiene la recursividad. El caso recursivo vuelve a llamar a la función con una entrada que se acerca al caso base. Quita cualquiera de las dos y la función nunca deja de llamarse a sí misma: en Python llegas a RecursionError en menos de mil llamadas; en un lenguaje sin límite, el proceso muere por desbordamiento de pila.

Cuándo la recursividad es la herramienta correcta: datos anidados

La recursividad se gana su sitio cuando los datos están anidados a una profundidad que no conoces de antemano: un árbol, un sistema de archivos, un JSON anidado sin límite. Un bucle sobre ese tipo de datos necesita una pila que gestiones a mano. La recursividad te da una gratis, porque la pila de llamadas es la pila que necesitabas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Cada llamada a flatten gestiona un nivel. Cuando encuentra una lista anidada, se la pasa a una nueva llamada, y la pila recuerda dónde reanudar en la lista exterior una vez que la interior termina. La versión iterativa tendría que rastrear esa posición por su cuenta.

Recorrer un árbol de directorios tiene la misma forma:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

A total_size le da igual que un directorio tenga un nivel o diez. Cada llamada gestiona su propio path.

Cuándo la recursividad es la herramienta equivocada: entrada plana y larga

Sumar una lista plana es el caso contrario. No hay anidamiento, así que la recursividad no aporta nada excepto riesgo de pila.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Funciona con entradas pequeñas y falla con entradas reales:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Dos mil elementos, un frame por elemento, el doble del límite por defecto. La versión con bucle usa un único frame sin importar la longitud de la lista:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) retorna al instante. En términos de notación Big O ambas versiones son O(n) en tiempo, pero la recursiva además cuesta O(n) en espacio de pila, y ese espacio está limitado a unos mil frames.

¿La tail-call optimization resuelve la recursividad profunda en Python o JavaScript?

No. En sum_recursive, lo último que ocurre es la suma, no la llamada recursiva, así que cada frame tiene que seguir vivo para recibir un resultado y sumarlo. Puedes reescribirla para que la llamada recursiva sea la última operación, llevando el total acumulado como argumento:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

En un lenguaje con tail-call optimization, el compilador ve que no se necesita nada del frame de quien llama después de la llamada, y reutiliza ese frame en lugar de apilar uno nuevo. La recursividad se convierte en un bucle por debajo.

CPython no lo hace, por decisión de diseño: sus desarrolladores principales la han rechazado porque haría los tracebacks más difíciles de leer. sum_tail sigue chocando con el límite en una lista de 2.000 elementos. La especificación ES2015 de JavaScript incluye las proper tail calls, pero V8 (Chrome, Node.js) y SpiderMonkey (Firefox) nunca las implementaron; solo JavaScriptCore, el motor de Safari, lo hace.

Así que la regla es la misma en los dos lenguajes. Si el tamaño de la entrada decide hasta dónde llega la recursividad, no confíes en que el motor te salve. Convierte la función en un bucle, o limita la profundidad.

Cómo la memoization arregla la recursividad lenta

Algunas funciones recursivas nunca se acercan al límite de profundidad. Su problema es que calculan lo mismo una y otra vez. El Fibonacci recursivo ingenuo es el caso de manual:

1
2
3
4

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) llama a fib(4) y a fib(3), y fib(4) vuelve a llamar a fib(3). Esa duplicación se acumula en cada nivel, así que el número de llamadas crece de forma exponencial con n (por un factor de alrededor de 1,6 en cada paso, que suele escribirse como el límite superior O(2^n)). En CPython, fib(30) ya tarda alrededor de una décima de segundo y fib(40) más de diez segundos.

La solución deja la recursividad tal cual y pone en caché los resultados, de modo que cada entrada distinta se calcula una sola vez:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache es un decorador. Envuelve a fib_memo, y cuando un argumento se repite, devuelve el resultado guardado en lugar de ejecutar otra vez el cuerpo. fib_memo(40) retorna al instante.

La profundidad no cambia: fib_memo(40) sigue necesitando unos 40 frames de pila. Lo que cambia es el número de llamadas, que pasa de exponencial a lineal. Pagas O(n) de memoria por la caché y obtienes O(n) de tiempo en lugar de exponencial.

Recursividad o iteración: cuál usar

Un caso merece más que una fila de tabla. Si la profundidad de la recursividad está controlada por una entrada en la que no confías, es un vector de denegación de servicio. Un parser recursivo que baja un nivel por cada corchete anidado en un texto que escribe el usuario puede hacerse fallar con solo enviar unos miles de caracteres [. Limita la profundidad de forma explícita, o no recurras.

Cómo convertir una función recursiva en un bucle

El sustituto directo de la recursividad sobre un árbol es una pila explícita: una list en la que haces push y pop a mano, controlada por un bucle while. Así queda flatten reescrita de esa forma:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Produce el mismo resultado con un único frame de pila, sin importar cuán profunda sea la entrada. El coste es la gestión que se ve a simple vista: la pila de iteradores es exactamente lo que la pila de llamadas rastreaba por ti.

La próxima vez que escribas una función recursiva, pregúntate hasta dónde puede llegar su profundidad. Si la respuesta es pequeña y conocida (un archivo de configuración, un árbol de componentes de interfaz, un árbol de parseo de tu propia gramática), conserva la recursividad. Si la respuesta es “lo que diga la entrada”, escribe el bucle.

Artículos relacionados

• Notación Big O Explicada con Ejemplos de Código
• Git Bisect: Cómo Encontrar el Commit que Rompió tu Código