Qué es la recursividad y cómo dejar de temerle

A la recursividad se le suele poner una etiqueta injusta: "o lo pillas o no lo pillas". No es verdad. Lo que ocurre es que casi siempre se explica con el ejemplo equivocado (el factorial, sin más contexto) y sin mostrar qué está pasando realmente detrás, en la memoria del programa. Una vez ves eso, deja de parecer magia.

En esencia, una función recursiva es simplemente una función que se llama a sí misma para resolver una versión más pequeña del mismo problema, hasta llegar a un caso tan simple que puede resolverse directamente.

Los dos ingredientes de toda función recursiva

Toda función recursiva correcta necesita exactamente dos piezas:

• Caso base: la condición más simple, donde la función devuelve un resultado directo sin volver a llamarse. Es lo que detiene la recursión.
• Caso recursivo: la función se llama a sí misma con una versión más pequeña o más simple del problema original, acercándose en cada llamada al caso base.

Si falta el caso base, o si el caso recursivo no se acerca nunca a él, la función se llama a sí misma indefinidamente hasta que el programa se queda sin memoria para seguir. Eso es justo lo que veremos con la pila de llamadas.

Qué es la pila de llamadas

Cada vez que una función llama a otra (o a sí misma), el ordenador guarda en la pila de llamadas (call stack) el punto exacto donde debe volver y con qué valores, y "apila" esa nueva llamada encima. Cuando esa llamada termina, se "desapila" y el control vuelve al punto guardado.

En una función recursiva, cada llamada a sí misma añade un nuevo nivel a la pila. Si el caso base nunca llega, la pila crece sin parar hasta agotar la memoria reservada para ella, lo que produce el clásico error RecursionError en Python o Maximum call stack size exceeded en JavaScript.

def factorial(n):
    if n <= 1:          # caso base: detiene la recursión
        return 1
    return n * factorial(n - 1)  # caso recursivo: problema más pequeño

print(factorial(5))  # 5 * 4 * 3 * 2 * 1 = 120

# Pila de llamadas al calcular factorial(5):
# factorial(5) -> factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)
# factorial(1) devuelve 1, y cada nivel multiplica y "desapila" hacia arriba

Fibonacci: cuando la recursión se repite de más

La sucesión de Fibonacci (cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8...) es el ejemplo perfecto para entender un problema real de la recursividad ingenua: la repetición de trabajo.

def fibonacci(n):
    if n <= 1:
        return n  # caso base
    return fibonacci(n - 1) + fibonacci(n - 2)  # dos llamadas recursivas

print(fibonacci(6))  # 8

El problema: fibonacci(6) vuelve a calcular fibonacci(4) dos veces, fibonacci(3) tres veces, y así sucesivamente. Esta versión tiene una complejidad exponencial, muy lejos de ser eficiente. La solución habitual es "memoizar" (guardar en caché los resultados ya calculados) o pasarse a una versión iterativa, algo a tener en cuenta si te interesa cómo se comparan distintos algoritmos según su eficiencia.

Recorrer un árbol: donde la recursividad brilla de verdad

Hay problemas donde la recursividad no es solo una opción elegante, sino la forma más natural de resolverlos: recorrer estructuras jerárquicas como árboles (el DOM de una web, un sistema de archivos, un árbol genealógico). Cada nodo puede tener hijos que son, a su vez, árboles más pequeños con la misma forma.

def contar_nodos(arbol):
    if arbol is None:
        return 0  # caso base: un árbol vacío no tiene nodos
    total = 1  # cuenta el nodo actual
    for hijo in arbol.get("hijos", []):
        total += contar_nodos(hijo)  # recursión sobre cada subárbol
    return total

carpeta = {
    "nombre": "proyecto",
    "hijos": [
        {"nombre": "src", "hijos": [{"nombre": "main.py"}]},
        {"nombre": "README.md"},
    ],
}
print(contar_nodos(carpeta))  # 4

Escribir este mismo recorrido de forma iterativa es posible, pero requiere gestionar tú mismo una pila o cola manual: la recursividad, en este caso, aprovecha directamente la pila de llamadas que ya te da el lenguaje. Este mismo patrón aparece cuando se explica cómo funciona un array frente a una lista enlazada, donde recorrer los nodos también puede plantearse de forma recursiva.

¿Recursividad o bucle? Cómo decidir

Como regla práctica: si el problema tiene una estructura naturalmente jerárquica o "problema grande hecho de problemas más pequeños idénticos" (árboles, backtracking, divide y vencerás), la recursividad suele dar un código más claro. Si el problema es simplemente "repite esto N veces", un bucle normal es casi siempre más legible y más eficiente en memoria, porque no acumula llamadas en la pila. La recursividad no es "más avanzada" que un bucle; es una herramienta distinta para un tipo de problema distinto.

Ponte a prueba