Funciones recursivas: funciones que se llaman a sí mismas

Al finalizar este tema

Podrás explicar el funcionamiento de las funciones recursivas, comprender la importancia del caso base (condición de parada) y resolver problemas sencillos de recursión.

¿Qué es la recursión?

La recursión es cuando una función se llama a sí misma.

def countdown(n):
    if n <= 0:
        print("Launch!")
        return
    print(n)
    countdown(n - 1)  # se llama a sí mismo

countdown(5)
# 5
# 4
# 3
# 2
# 1
# Launch!

countdown(5) llama a countdown(4), countdown(4) llama a countdown(3)... Cuando se alcanza countdown(0), imprime "Launch!" y se detiene.

Esto es todo lo que es la recursión. Tiene dos elementos:

1. Caso base (Base Case): if n <= 0 — la condición para dejar de realizar llamadas.
2. Caso recursivo (Recursive Case): countdown(n - 1) — se llama a sí mismo, pero reduciendo el problema.

Por qué es esencial el caso base

Sin un caso base, la función se llamaría a sí misma infinitamente.

def infinite():
    print("Help!")
    infinite()  # llamada infinita

infinite()
# Help!
# Help!
# Help!
# ...
# RecursionError: maximum recursion depth exceeded

Python permite la recursión hasta un máximo de 1,000 veces de forma predeterminada. Si se supera este límite, se produce un cierre forzado mediante RecursionError. Este es un mecanismo de seguridad para evitar que la memoria se agote debido a una recursión infinita.

Factorial: ejemplo clásico de recursión

5! = 5 × 4 × 3 × 2 × 1 = 120

Si pensamos en el factorial de forma recursiva: 5! = 5 × 4!

def factorial(n):
    # Base case
    if n <= 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(factorial(5))  # 120

Siguiendo el proceso de llamada:

factorial(5)
  → 5 * factorial(4)
       → 4 * factorial(3)
            → 3 * factorial(2)
                 → 2 * factorial(1)
                      → 1  (base case!)
                 ← 2 * 1 = 2
            ← 3 * 2 = 6
       ← 4 * 6 = 24
  ← 5 * 24 = 120

La función tiene una estructura en la que "se adentra" y luego "regresa" con los resultados.

La pila de llamadas: el principio de funcionamiento de la recursión

Cada vez que se llama a una función, el ordenador guarda el estado actual en un espacio de memoria llamado pila (stack).

factorial(5) llamado → pila: [factorial(5)]
factorial(4) llamado → pila: [factorial(5), factorial(4)]
factorial(3) llamado → pila: [factorial(5), factorial(4), factorial(3)]
factorial(2) llamado → pila: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(1) llamado → pila: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
factorial(1) devuelto → pila: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(2) devuelto → pila: [factorial(5), factorial(4), factorial(3)]
...

A medida que aumenta la profundidad de la recursión, la pila se acumula. La razón por la que el límite predeterminado de Python es 1000 es que cada elemento de la pila ocupa memoria; si la profundidad es excesiva, se producirá un error por falta de memoria.

Fibonacci: la trampa de la recursión

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

print(fib(10))  # 55
print(fib(30))  # 832040 — but slow!
# print(fib(50))  # Never finishes...

El código es conciso, pero fib(50) nunca termina, ya que recalcula el mismo valor repetidamente.

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← repeated
│   │   └── fib(1)
│   └── fib(2) ← repeated
└── fib(3) ← repeated
    ├── fib(2) ← repeated
    └── fib(1)

fib(2) se calcula repetidamente. En fib(30) se producen millones de cálculos redundantes y en fib(50) miles de millones.

Solución mediante memoización

from functools import lru_cache

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

print(fib_fast(50))   # 12586269025 — instant!
print(fib_fast(100))  # 354224848179261915075

@lru_cache almacena los resultados ya calculados y, cuando se llama con los mismos argumentos, devuelve el valor almacenado. Al eliminar los cálculos redundantes, la complejidad se reduce de O(2^n) a O(n).

Recursión vs. bucles

El mismo problema también se puede resolver mediante bucles.

# Recursion
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

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

Regla: Si la estructura del problema es naturalmente recursiva (árboles, grafos, divide y vencerás), usa recursión; si es una iteración simple, usa un bucle for.

Ejemplo práctico — Exploración de directorios

import os

def list_all_files(directory, indent=0):
    """Recursively list all files in a directory tree."""
    items = sorted(os.listdir(directory))
    for item in items:
        path = os.path.join(directory, item)
        print("  " * indent + item)
        if os.path.isdir(path):
            list_all_files(path, indent + 1)  # subdirectory → recurse

list_all_files("project")
# project
#   app.js
#   routes
#     users.js
#     posts.js
#   public
#     css
#       style.css
#     index.html

Una carpeta dentro de otra, y dentro de esa otra hay más carpetas: esta es la estructura típica de un problema recursivo. Si "no se sabe cuántos niveles hay, pero el mismo patrón se repite", la recursión es la solución natural.

Resumen clave

Al ver la recursión por primera vez, puede surgir la duda: "¿Si una función se llama a sí misma, no creará un bucle infinito?". La clave es que cada vez el problema se vuelve más pequeño hasta alcanzar finalmente la condición de parada. Comprender este patrón permite entender de forma natural muchos algoritmos, como la búsqueda en árboles, la ordenación (merge sort), combinaciones/permutaciones y la búsqueda en grafos (DFS).

Patrón práctico — Exploración de diccionarios anidados

Al encontrarse con estructuras anidadas de profundidad desconocida, como en JSON o archivos de configuración, la recursión es la solución natural.

def flatten_dict(d, prefix=""):
    result = {}
    for key, value in d.items():
        full_key = f"{prefix}.{key}" if prefix else key
        if isinstance(value, dict):
            result.update(flatten_dict(value, full_key))
        else:
            result[full_key] = value
    return result

config = {
    "database": {
        "host": "localhost",
        "port": 5432,
        "credentials": {
            "user": "admin",
            "password": "secret"
        }
    },
    "debug": True
}

print(flatten_dict(config))
# {
#   'database.host': 'localhost',
#   'database.port': 5432,
#   'database.credentials.user': 'admin',
#   'database.credentials.password': 'secret',
#   'debug': True
# }

Este patrón se utiliza con frecuencia en sistemas de registro, gestión de configuración e indexación de Elasticsearch.