Recursión en Python

La recursión es una técnica en la que una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños e idénticos. Cada llamada trabaja sobre una versión más simple del problema original hasta llegar a un caso trivial — el caso base — que puede responderse directamente.

Este capítulo cubre:

• Cómo funciona la recursión y cómo se ve la pila de llamadas
• Caso base y caso recursivo
• Problemas recursivos clásicos: factorial, Fibonacci, potencia, aplanamiento
• Recursión vs iteración — cuándo elegir cada una
• El límite de recursión de Python y cómo trabajar con él
• Memoización con functools.lru_cache

Cómo Funciona la Recursión

Cuando una función se llama a sí misma, Python coloca un nuevo marco de pila en la pila de llamadas por cada llamada. Cada marco mantiene sus propias variables locales. Cuando se alcanza el caso base, los marcos comienzan a retornar en orden inverso — el último en entrar, el primero en salir — hasta que la llamada original recibe su respuesta final.

Una función recursiva válida siempre tiene dos partes:

Sin un caso base (o con uno que nunca se alcanza), la función se llama a sí misma indefinidamente y Python lanza un RecursionError.

Un Ejemplo Simple: Cuenta Regresiva

La siguiente función hace una cuenta regresiva desde n hasta cero y luego imprime "Go!". Es fácil de seguir porque cada llamada reduce n en uno hasta que n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Salida:

5
4
3
2
1
Go!

Traza de la pila de llamadas:

1. countdown(5) imprime 5, llama a countdown(4)
2. countdown(4) imprime 4, llama a countdown(3)
3. … y así sucesivamente …
4. countdown(0) imprime "Go!" y retorna — comienza el desenrollado

Factorial

El factorial de n (escrito n!) es el producto de todos los enteros positivos hasta n. Se define recursivamente como:

• 0! = 1 (caso base)
• n! = n × (n − 1)! (caso recursivo)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) se expande así antes de que se retorne cualquier valor:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Luego las multiplicaciones ocurren en el camino de vuelta: 1 → 2 → 6 → 24 → 120.

Secuencia de Fibonacci

La secuencia de Fibonacci se define así: cada número es la suma de los dos anteriores — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Esto es correcto pero lento para valores grandes de n — fibonacci(40) realiza millones de llamadas redundantes. Consulta Memoización más abajo para la solución.

Suma de una Lista

La recursión funciona de manera natural con listas: procesa el primer elemento y luego recurre sobre el resto.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] crea una nueva lista sin el primer elemento, haciendo el problema un elemento más pequeño cada vez.

Elevar un Número a una Potencia

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Aplanar una Lista Anidada

Algunos problemas son intrínsecamente recursivos — tienen la misma estructura en cada nivel. Aplanar una lista anidada de profundidad arbitraria es uno de ellos.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

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

Esto es difícil de escribir de forma limpia solo con iteración porque la profundidad del anidamiento es desconocida.

Recursión vs Iteración

La mayoría de los algoritmos recursivos pueden reescribirse como bucles iterativos, y viceversa.

Factorial iterativo

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

Guía: elige recursión cuando el problema se descompone naturalmente en subproblemas idénticos más pequeños y la profundidad es moderada. Elige iteración cuando necesitas alto rendimiento o la profundidad podría ser grande.

El Límite de Recursión de Python

Python limita la pila de llamadas a 1 000 marcos por defecto para evitar que un desbordamiento de pila bloquee el proceso.

import sys
print(sys.getrecursionlimit())   # 1000

Si tu función supera este límite, verás:

RecursionError: maximum recursion depth exceeded

Puedes aumentar el límite con sys.setrecursionlimit(n), pero hazlo con precaución — una pila muy profunda puede agotar la memoria del sistema. Para recursión genuinamente profunda, reescribe el algoritmo de forma iterativa o usa generadores de Python para simular una pila manualmente.

Memoización

La recursión naive de Fibonacci es exponencialmente lenta porque resuelve los mismos subproblemas una y otra vez. La memoización almacena en caché el resultado de cada llamada única para que se calcule solo una vez.

Caché manual con un diccionario

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Usando functools.lru_cache

La biblioteca estándar proporciona un decorador que gestiona el caché automáticamente:

from functools import lru_cache

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

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache convierte un algoritmo que de otro modo sería exponencial en tiempo lineal sin ningún código adicional dentro del cuerpo de la función. Es el enfoque idiomático de Python para memoizar funciones recursivas puras.

Búsqueda Binaria (Recursiva)

La búsqueda binaria es un algoritmo clásico de divide y vencerás: compara el objetivo con el elemento central y luego recurre en la mitad izquierda o derecha.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Errores Comunes

Caso base faltante

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Siempre pregúntate: "¿Cuál es la entrada más simple que esta función debe manejar sin llamarse a sí misma?"

Recursión infinita por un caso base incorrecto

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Argumento predeterminado mutable como memo

Usar memo={} como parámetro predeterminado es conveniente pero comparte estado entre todas las llamadas de nivel superior. Para código en producción, pasa el caché explícitamente o usa @lru_cache.

Cuándo Usar la Recursión

La recursión es una opción natural para:

• Recorrido de árboles y grafos — listados de directorios, recorrido del DOM, árboles de decisión
• Algoritmos de divide y vencerás — merge sort, quicksort, búsqueda binaria
• Definiciones matemáticas — factorial, Fibonacci, combinatoria
• Backtracking — resolución de laberintos, Sudoku, generación de permutaciones
• Estructuras de datos anidadas — análisis de JSON/XML, aplanamiento de listas anidadas

Para bucles secuenciales simples o grandes profundidades, prefiere los bucles for o los bucles while.

Capítulos Relacionados

• Funciones en Python — los bloques de construcción sobre los que se basa la recursión
• Alcance en Python — entender cómo funcionan las variables locales en cada marco
• Bucles While en Python — la alternativa iterativa
• Generadores en Python — alternativas eficientes en memoria para secuencias
• Iteradores en Python — el protocolo de iteración subyacente al modelo de bucles de Python
• Try Except en Python — manejar RecursionError de forma elegante

Práctica