Recursión explicada: cómo funciona, con ejemplos en Python

Qué problema resuelve la recursión

Algunos problemas se definen en términos de sí mismos. Una carpeta contiene archivos y otras carpetas. Un nodo de un árbol tiene subárboles. El factorial de n es n por el factorial de n − 1. Escribirlos con bucles simples suele requerir una pila explícita de trabajo pendiente; con la recursión, el lenguaje mantiene esa pila por ti.

Una función recursiva tiene dos partes:

• Caso base: la entrada más pequeña, que se responde directamente. En el factorial, 0! = 1.
• Caso recursivo: reducir el problema, llamar a la función con la parte más pequeña y combinar el resultado. En el factorial, n! = n × (n − 1)!.

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

La pila de llamadas, paso a paso

Cada llamada obtiene su propio marco en la pila de llamadas, con su propia copia de n. Las llamadas descienden hasta el caso base y luego los resultados vuelven hacia arriba en orden inverso.

La profundidad de la pila aquí es de n + 1 marcos, así que el espacio extra es O(n) aunque no se cree ninguna lista.

Recursión sobre datos anidados

La recursión es más útil cuando la forma de los datos es en sí misma recursiva. Esta función suma todos los números de una lista que puede contener otras listas, a cualquier profundidad.

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

El mismo patrón recorre un árbol de directorios, un documento JSON, un DOM de HTML o un árbol binario: procesa el nodo actual y luego recursa en cada hijo.

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Complejidad de las funciones recursivas

Estima el coste como (número de llamadas) × (trabajo por llamada). El espacio es como mínimo la profundidad máxima de la pila.

Las recurrencias de divide y vencerás como T(n) = 2T(n/2) + O(n) para merge sort se resuelven en O(n log n). Una función que hace dos llamadas con n − 1 crece de forma exponencial.

Memoización: evitar repetir trabajo

La función de Fibonacci ingenua recalcula los mismos valores muchas veces: fib(5) llama a fib(3) dos veces y a fib(2) tres veces. Guardar en caché cada resultado la primera vez que se calcula convierte el tiempo exponencial en lineal. functools.lru_cache de Python (o functools.cache, a partir de Python 3.9) lo hace con un solo decorador.

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

La recursión con memoización es la forma descendente (top-down) de la programación dinámica. La forma ascendente (bottom-up) rellena una tabla con un bucle.

Límites de la recursión y conversión a un bucle

Puedes subir el límite con sys.setrecursionlimit(), pero una recursión muy profunda aún puede bloquear el intérprete. Para entradas que pueden ser profundas, como una lista enlazada de un millón de nodos o un árbol degenerado, reescribe la función con un bucle y una pila explícita.

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

Errores comunes

• Caso base ausente o inalcanzable; por ejemplo, factorial(-1) con el código anterior nunca llega a 0 y termina en RecursionError.
• Un caso recursivo que no reduce la entrada, como llamar a f(n) desde f(n).
• Olvidar el return del resultado recursivo: factorial(n - 1) sin return devuelve None.
• Copiar datos en cada llamada. items[1:] copia la lista, así que recursar sobre rebanadas de una lista larga cuesta O(n²) de tiempo; pasa un índice en su lugar.
• Usar un argumento por defecto mutable como def f(x, seen=[]) para llevar estado entre llamadas; la misma lista se comparte en todas las llamadas a la función.

Cuándo usar recursión

Usa recursión cuando los datos o el problema sean recursivos por naturaleza: árboles, grafos (búsqueda en profundidad), estructuras anidadas, análisis de expresiones, backtracking (permutaciones, N reinas, sudoku) y divide y vencerás (merge sort, quicksort, búsqueda binaria). Usa un bucle cuando el problema sea una secuencia simple, o cuando en Python la profundidad pueda crecer con el tamaño de la entrada.

En las entrevistas técnicas, las preguntas sobre recursión suelen comprobar que sabes indicar el caso base, el caso recursivo, el coste en tiempo y espacio incluyendo la pila, y cuándo ayuda la memoización.