26.Recursividad

La recursividad es cuando una función se llama a sí misma para resolver una versión más pequeña del mismo problema, hasta llegar a un caso tan sencillo que se resuelve sin más llamadas.

Piensa en las muñecas rusas (matrioskas): para saber cuántas hay, abres una; adentro hay otra igual pero más pequeña, y repites… hasta llegar a la última, que ya no se abre.

Las dos partes obligatorias

Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120.

PSeInt

Funcion r <- Factorial(n)
	Si n = 0 Entonces
		r <- 1
	SiNo
		r <- n * Factorial(n - 1)
	FinSi
FinFuncion

Algoritmo Principal
	Escribir "5! = ", Factorial(5)
FinAlgoritmo

Python

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

print("5! =", factorial(5))

Cómo se resuelve (pila de llamadas)

factorial(5) = 5 * factorial(4)
                   factorial(4) = 4 * factorial(3)
                                      factorial(3) = 3 * factorial(2)
                                                         factorial(2) = 2 * factorial(1)
                                                                            factorial(1) = 1 * factorial(0)
                                                                                               factorial(0) = 1   ← caso base
             = 5 * 4 * 3 * 2 * 1 * 1 = 120

Cada llamada espera a que termine la siguiente; al llegar al caso base, los resultados regresan multiplicándose.

Problema: sumar los dígitos de un número (por ejemplo, 4 + 7 + 2 = 13 para 472).

1. Caso base: un número de un solo dígito (menor que 10) es su propia suma.

2. Caso recursivo: el último dígito (n % 10) más la suma de los dígitos del resto (n // 10).

def suma_digitos(n):
    if n < 10:
        return n
    return n % 10 + suma_digitos(n // 10)

print(suma_digitos(472))     # 13
print(suma_digitos(2026))    # 10

Salida esperada:

13
10

Recursivo y con ciclo

Todo lo recursivo se puede hacer también con un ciclo:

def suma_digitos_ciclo(n):
    suma = 0
    while n > 0:
        suma += n % 10
        n //= 10
    return suma

print(suma_digitos_ciclo(472))   # 13

# ✗ Incorrecto: no hay caso base
def cuenta(n):
    print(n)
    cuenta(n - 1)

cuenta(3)

RecursionError: maximum recursion depth exceeded

• Escribe primero el caso base.
• Usa recursividad cuando el problema es naturalmente recursivo: carpetas dentro de carpetas, árboles, divide y vencerás.
• Para repeticiones simples, prefiere un ciclo: es más eficiente en Python.
• Python limita la profundidad (alrededor de 1000 llamadas por defecto); no lo subas sin necesidad.
• Haz la pila de llamadas a mano con un número pequeño para entenderla.

• Downey, A. Think Python, capítulo «Conditionals and Recursion». https://allendowney.github.io/ThinkPython/
• Python Software Foundation. sys.getrecursionlimit(). https://docs.python.org/es/3/library/sys.html#sys.getrecursionlimit
• Python Software Foundation. functools.lru_cache. https://docs.python.org/es/3/library/functools.html#functools.lru_cache
• Python Tutor (visualizador de ejecución). https://pythontutor.com/