Recursividad en Python

Una función recursiva es una función que se llama a sí misma. Suena raro, pero es una forma muy natural de resolver problemas que se pueden dividir en versiones más pequeñas del mismo problema: recorrer carpetas dentro de carpetas, menús con submenús o comentarios con respuestas. En esta lección verás cómo se construye una función recursiva, qué pasa por dentro con la pila de llamadas, los ejemplos clásicos (factorial, Fibonacci, sumas) y cuándo conviene usar un bucle en su lugar.

La idea: un problema dentro de otro

Imagina que quieres contar cuántas personas hay delante de ti en una cola, pero solo puedes hablar con quien tienes justo delante. Le preguntas: “¿Cuántas personas tienes delante?”. Esa persona hace la misma pregunta a la suya, y así sucesivamente, hasta llegar a la primera de la cola, que responde “ninguna”. Entonces cada una devuelve la respuesta de la anterior más uno.

Esa es la receta de cualquier función recursiva:

• Caso base: la situación tan simple que se responde directamente, sin volver a llamar a la función (“soy la primera, no tengo a nadie delante”).
• Caso recursivo: la función se llama a sí misma con un problema más pequeño y usa su resultado (“lo que diga quien tengo delante, más uno”).

Si falta el caso base, o si el problema no se hace más pequeño en cada llamada, la función se llamaría a sí misma para siempre.

Tu primera función recursiva: una cuenta atrás

def cuenta_atras(n):
    if n == 0:                 # caso base
        print("¡Despegue!")
        return
    print(n)
    cuenta_atras(n - 1)        # caso recursivo, con un problema más pequeño

cuenta_atras(3)
# 3
# 2
# 1
# ¡Despegue!

Cada llamada imprime su número y delega el resto de la cuenta en una llamada con n - 1. Cuando n llega a 0, se cumple el caso base y las llamadas dejan de encadenarse.

Factorial: devolver un resultado

El factorial de un número n (se escribe n!) es el producto de todos los enteros desde 1 hasta n: 5! = 5 · 4 · 3 · 2 · 1 = 120. Fíjate en que 5! = 5 · 4!, y 4! = 4 · 3!… El problema contiene una versión más pequeña de sí mismo. Por definición, 0! = 1 y 1! = 1.

def factorial(n):
    if n <= 1:                     # caso base
        return 1
    return n * factorial(n - 1)    # caso recursivo

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

Qué pasa por dentro: la pila de llamadas

Cada vez que llamas a una función, Python guarda sus variables y el punto donde debe continuar en una estructura llamada pila de llamadas (call stack). Funciona como una pila de platos: la última llamada que entra es la primera que termina.

Con factorial(4) ocurre esto:

factorial(4)  espera a  4 * factorial(3)
  factorial(3)  espera a  3 * factorial(2)
    factorial(2)  espera a  2 * factorial(1)
      factorial(1)  -> caso base, devuelve 1
    factorial(2)  devuelve 2 * 1 = 2
  factorial(3)  devuelve 3 * 2 = 6
factorial(4)  devuelve 4 * 6 = 24

Primero las llamadas bajan hasta el caso base, y ninguna puede terminar todavía. Después, el resultado sube: cada llamada recibe la respuesta de la de abajo, hace su multiplicación y devuelve el resultado a la de arriba.

Puedes verlo tú mismo añadiendo un parámetro que indique la profundidad y usándolo para sangrar los mensajes:

def factorial_traza(n, nivel=0):
    sangria = "  " * nivel
    print(f"{sangria}factorial({n})")
    if n <= 1:
        print(f"{sangria}-> 1")
        return 1
    resultado = n * factorial_traza(n - 1, nivel + 1)
    print(f"{sangria}-> {resultado}")
    return resultado

factorial_traza(3)
# factorial(3)
#   factorial(2)
#     factorial(1)
#     -> 1
#   -> 2
# -> 6

Cada llamada tiene sus propias variables: el n de factorial(3) sigue valiendo 3 mientras factorial(2) trabaja con su n igual a 2. No se pisan.

Sumar una lista de forma recursiva

Una lista también se puede ver como un problema recursivo: su suma es “el primer elemento más la suma del resto”.

def suma(numeros):
    if not numeros:                       # caso base: lista vacía
        return 0
    return numeros[0] + suma(numeros[1:])

print(suma([4, 8, 15, 16, 23, 42]))   # 108
print(suma([]))                       # 0

Con la misma idea puedes encontrar el máximo, contar elementos o darle la vuelta a un texto:

def invertir(texto):
    if len(texto) <= 1:
        return texto
    return invertir(texto[1:]) + texto[0]

print(invertir("Santander"))   # rednatnaS

Nota: estos ejemplos son buenos para entender la técnica, pero en la práctica usarías sum(numeros) y texto[::-1]. Además, numeros[1:] crea una lista nueva en cada llamada, lo que gasta memoria. La recursión brilla de verdad con los datos anidados que verás más abajo.

Fibonacci y el problema de repetir trabajo

La sucesión de Fibonacci empieza por 0 y 1, y cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21… Su definición ya es recursiva, con dos llamadas en cada paso:

def fib(n):
    if n < 2:                          # caso base: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])   # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Funciona, pero es muy lenta con números grandes. El problema es que repite el mismo cálculo una y otra vez: fib(5) calcula fib(4) y fib(3), pero fib(4) vuelve a calcular fib(3), y así en cascada. Cuenta las llamadas:

llamadas = 0

def fib_contando(n):
    global llamadas
    llamadas += 1
    if n < 2:
        return n
    return fib_contando(n - 1) + fib_contando(n - 2)

print(fib_contando(20), "en", llamadas, "llamadas")
# 6765 en 21891 llamadas

¡Casi 22.000 llamadas para obtener un número! Y cada vez que n sube en uno, las llamadas se multiplican por 1,6 aproximadamente. fib(40) tardaría varios segundos.

La solución: recordar resultados con functools.cache

Si guardamos cada resultado la primera vez que lo calculamos, las siguientes veces basta con consultarlo. Esa técnica se llama memoización (de memo, nota), y Python la trae hecha con el decorador @cache del módulo functools:

from functools import cache

@cache
def fib_rapido(n):
    if n < 2:
        return n
    return fib_rapido(n - 1) + fib_rapido(n - 2)

print(fib_rapido(20))    # 6765
print(fib_rapido(100))   # 354224848179261915075

El código de la función es el mismo; solo cambia la línea @cache. Ahora cada valor se calcula una única vez y fib_rapido(100) responde al instante. Aprenderás cómo funcionan los decoradores por dentro en la lección de decoradores.

Consejo: @cache solo sirve para funciones puras: las que, con los mismos argumentos, devuelven siempre el mismo resultado y no tienen efectos secundarios (no imprimen ni modifican nada). Además, los argumentos deben ser inmutables: números, textos o tuplas, no listas.

Recorrer estructuras anidadas

Aquí es donde la recursión resulta imprescindible. Imagina un menú de restaurante con secciones y subsecciones, o un sistema de carpetas. No sabes cuántos niveles de profundidad tiene, así que un número fijo de bucles anidados no sirve. Una función recursiva, en cambio, se adapta a cualquier profundidad.

Carpetas dentro de carpetas

Representamos un disco con diccionarios: si el valor es un número, es un archivo con su tamaño en KB; si es otro diccionario, es una carpeta.

disco = {
    "notas.txt": 4,
    "fotos": {
        "playa.jpg": 2300,
        "monte.jpg": 1800,
        "2025": {"boda.jpg": 3100},
    },
    "clase": {
        "python": {"recursividad.py": 2, "apuntes.pdf": 950},
        "horario.pdf": 120,
    },
}

def tamano_total(carpeta):
    total = 0
    for contenido in carpeta.values():
        if isinstance(contenido, dict):    # es una subcarpeta
            total += tamano_total(contenido)
        else:                              # es un archivo
            total += contenido
    return total

print(tamano_total(disco), "KB")           # 8276 KB
print(tamano_total(disco["fotos"]), "KB")  # 7200 KB

isinstance(valor, dict) comprueba si el valor es un diccionario. El caso base aquí no es un if al principio: es el archivo, que se suma sin volver a llamar a la función. Una carpeta vacía también es un caso base, porque el bucle no se ejecuta y devuelve 0.

Mostrar el árbol

Con un parámetro de nivel, como hiciste en la traza del factorial, puedes dibujar la estructura:

def mostrar(carpeta, nivel=0):
    for nombre, contenido in carpeta.items():
        if isinstance(contenido, dict):
            print("    " * nivel + f"[{nombre}]")
            mostrar(contenido, nivel + 1)
        else:
            print("    " * nivel + f"{nombre} ({contenido} KB)")

mostrar(disco)
# notas.txt (4 KB)
# [fotos]
#     playa.jpg (2300 KB)
#     monte.jpg (1800 KB)
#     [2025]
#         boda.jpg (3100 KB)
# [clase]
#     [python]
#         recursividad.py (2 KB)
#         apuntes.pdf (950 KB)
#     horario.pdf (120 KB)

Para recorrer carpetas reales del ordenador usarías pathlib (lo verás en Ficheros), pero la estructura de la función sería exactamente la misma.

Buscar en listas anidadas

Otro caso típico es aplanar una lista que contiene listas a cualquier profundidad:

def aplanar(datos):
    resultado = []
    for elemento in datos:
        if isinstance(elemento, list):
            resultado.extend(aplanar(elemento))
        else:
            resultado.append(elemento)
    return resultado

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

El límite de recursión

Cada llamada ocupa un hueco en la pila, y la pila no es infinita. Para protegerse, Python corta la recursión cuando supera un número de llamadas encadenadas. Puedes consultar ese límite con el módulo sys:

import sys

print(sys.getrecursionlimit())   # 1000

Si lo superas, Python lanza RecursionError. Ocurre sobre todo cuando olvidas el caso base o cuando el problema no se reduce:

def sin_fin(n):
    return sin_fin(n + 1)      # no hay caso base y n crece

try:
    sin_fin(1)
except RecursionError as error:
    print("Error:", error)
# Error: maximum recursion depth exceeded

Existe sys.setrecursionlimit() para subir el límite, pero casi nunca es la solución: si tu función necesita más de mil niveles, probablemente debería ser un bucle.

Cuidado: a diferencia de otros lenguajes, Python no optimiza la recursión de cola (cuando la llamada recursiva es lo último que hace la función). Cada llamada ocupa su hueco en la pila, siempre. Por eso, en Python, recorrer una lista de 10.000 elementos de forma recursiva falla, mientras que con un bucle no hay ningún problema.

Recursión frente a bucle

Todo lo que se hace con recursión se puede hacer con bucles, y al revés. Compara las dos versiones del factorial:

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

print(factorial_bucle(5), factorial(5))   # 120 120

¿Cuál elegir? Depende del problema:

	Recursión	Bucle
Datos lineales (listas, rangos, contadores)	Funciona, pero es más lenta y tiene límite	La opción natural en Python
Datos anidados (árboles, carpetas, JSON, menús)	Código corto y claro	Necesita gestionar una pila a mano
Memoria	Una entrada en la pila por llamada	Constante
Límite de profundidad	Unas 1000 llamadas	Ninguno
Problemas definidos de forma recursiva (Fibonacci, divide y vencerás)	Se parece a la definición	A veces cuesta más de leer

Regla práctica: usa recursión cuando los datos tienen forma de árbol o cuando el algoritmo se divide en subproblemas del mismo tipo (como algunos algoritmos de ordenación). Para todo lo demás, un bucle for o while es más sencillo y más rápido.

Cómo pensar una función recursiva

Cuando te enfrentes a un problema nuevo, sigue estos pasos:

1. Busca el caso más simple: lista vacía, número 0 o 1, texto de una letra, archivo (no carpeta). Ese es tu caso base.
2. Confía en la llamada recursiva: supón que la función ya funciona para un problema un poco más pequeño. ¿Cómo usarías ese resultado para resolver el problema actual?
3. Comprueba que avanzas: cada llamada debe acercarse al caso base (n - 1, lista[1:], una subcarpeta).

Por ejemplo, para calcular una potencia base ** exp con exponente entero positivo: el caso más simple es exp == 0 (el resultado es 1), y si sabes calcular base ** (exp - 1), solo tienes que multiplicarlo por base:

def potencia(base, exp):
    if exp == 0:
        return 1
    return base * potencia(base, exp - 1)

print(potencia(2, 10))   # 1024
print(potencia(5, 3))    # 125

Errores frecuentes

• Olvidar el caso base: la función se llama sin parar y termina en RecursionError: maximum recursion depth exceeded.
• No reducir el problema: llamar a factorial(n) dentro de factorial(n) en lugar de factorial(n - 1). El caso base nunca llega.
• Olvidar el return en el caso recursivo: si escribes n * factorial(n - 1) sin return, la función devuelve None y la multiplicación de la llamada anterior falla con TypeError.
• Usar recursión para recorrer listas largas: con más de unos mil elementos chocas con el límite. Usa un bucle.
• Recalcular lo mismo una y otra vez: con dos o más llamadas recursivas (como en Fibonacci), añade @cache si la función es pura.
• Valores por defecto mutables en funciones recursivas: def recorrer(datos, vistos=[]) comparte la lista entre llamadas distintas. Usa None y créala dentro, como viste en funciones avanzadas.

Resumen

Concepto	Qué significa	Ejemplo
Función recursiva	Se llama a sí misma	return n * factorial(n - 1)
Caso base	Se resuelve sin recursión y detiene las llamadas	if n <= 1: return 1
Caso recursivo	Llamada con un problema más pequeño	suma(numeros[1:])
Pila de llamadas	Guarda cada llamada pendiente hasta que termina	Bajan hasta el caso base y luego suben
@cache	Recuerda resultados ya calculados	fib_rapido(100) al instante
Datos anidados	El uso estrella de la recursión	Carpetas, menús, listas dentro de listas
sys.getrecursionlimit()	Profundidad máxima permitida	1000
RecursionError	Se ha superado el límite	Falta caso base o el problema no se reduce

En la siguiente lección aprenderás cómo funcionan por dentro los bucles for con los iteradores y generadores.

def mostrar(n):
    if n == 0:
        return
    mostrar(n - 1)
    print(n)

mostrar(3)

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

def total(carpeta):
    t = 0
    for valor in carpeta.values():
        if isinstance(valor, dict):
            t += total(valor)
        else:
            t += valor
    return t