Recursividad en Python: la función que se llama a sí misma (y el límite en MicroPython)

Una función es recursiva cuando se llama a sí misma. Para que esto funcione sin quedarse llamando para siempre, necesita dos partes: un caso base, que da la respuesta directa sin nueva llamada, y un paso recursivo, que reduce el problema y llama a la misma función con algo menor. En cada llamada Python apila un nuevo marco con las variables locales, y cuando se alcanza el caso base los valores vuelven por la pila hasta la primera llamada.

La recursividad es una manera de pensar: "para resolver esto, resuelvo una versión menor y junto el resultado". Vale la pena conocerla porque aparece en problemas naturalmente repetitivos, como el factorial, el máximo común divisor y el recorrido de estructuras anidadas. En la ESP32 viene con una advertencia, porque la memoria para apilar llamadas es pequeña y el límite de profundidad es mucho menor que en el computador. Este artículo muestra cómo escribir una función recursiva, cómo seguirla en la pila, qué ocurre cuando no se detiene, dónde queda el límite en el simulador y cuándo un bucle es la mejor elección.

La idea: un problema menor igual al primero

Imagina una cuenta regresiva. Para contar de 3 hasta 0, dices 3 y después haces una cuenta regresiva de 2 hasta 0. Esa segunda cuenta es el mismo problema, solo que menor. En Python:

def contagem(n):
    if n == 0:
        print("¡fuego!")
        return
    print(n)
    contagem(n - 1)

contagem(3)
print("fin")

La salida es 3, 2, 1, ¡fuego! y fin. La función contagem muestra el número y llama a contagem(n - 1), que hace lo mismo con el número siguiente. Cuando n llega a 0, el if responde directo, sin nueva llamada, y la cadena termina. Ese return sin valor, que presentó el artículo sobre return, termina la función.

Caso base y paso recursivo

Toda función recursiva tiene las dos partes de la figura. El caso base es la situación más simple, para la cual la respuesta es conocida. El paso recursivo es lo que la función hace en los otros casos: se llama a sí misma con un argumento más cercano al caso base. La suma de los números de 1 hasta n lo muestra con claridad:

def soma_ate(n):
    if n == 0:
        return 0
    return n + soma_ate(n - 1)

print(soma_ate(4))
print(soma_ate(10))
total = 0
for i in range(1, 11):
    total = total + i
print(total)

La salida es 10, 55 y 55. La suma hasta 4 es 4 más la suma hasta 3, que es 3 más la suma hasta 2, y así hasta la suma hasta 0, que vale 0 (el caso base). El bucle del final, con el mismo resultado, sirve de comparación: la recursión repite por llamadas lo que el bucle repite por vueltas.

La segunda condición para que la recursión funcione es que cada llamada se acerque al caso base. En soma_ate, el n va de 4 a 3, 2, 1 y 0, y el 0 aparece. Si el argumento no se acercara, el caso base nunca se alcanzaría.

La pila de llamadas

Cuando una función se llama a sí misma, la llamada anterior no termina: queda esperando. Python guarda cada llamada pendiente en una pila, con el n y las otras variables de esa llamada. El factorial de n, el producto de 1 hasta n, muestra lo que ocurre:

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

print(fatorial(1))
print(fatorial(5))
print(fatorial(10))
print(fatorial(12))

La salida es 1, 120, 3628800 y 479001600. Para ver la pila trabajando, el mismo programa con un print a la entrada y a la salida de cada llamada:

def fatorial(n):
    print("entra", n)
    if n <= 1:
        print("base, devuelve 1")
        return 1
    r = n * fatorial(n - 1)
    print("sale", n, "devuelve", r)
    return r

print(fatorial(4))

La salida es entra 4, entra 3, entra 2, entra 1, base, devuelve 1, sale 2 devuelve 2, sale 3 devuelve 6, sale 4 devuelve 24 y 24. Todas las entradas aparecen antes de cualquier salida, y las salidas vienen en el orden inverso. La multiplicación n * fatorial(n - 1) no se hace en la ida: cada llamada queda detenida en la multiplicación, esperando el valor de la de abajo. La cuenta solo ocurre en la vuelta. La figura muestra la misma secuencia con los marcos apilados.

Esto explica un hecho práctico: cada nivel de la recursión ocupa memoria mientras espera. Una recursión con mil niveles tiene mil marcos vivos al mismo tiempo.

Más ejemplos

La potencia, la base elevada al exponente, es la base por la potencia con el exponente menor en 1:

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

print(potencia(2, 10))
print(potencia(3, 4))
print(potencia(5, 0))

La salida es 1024, 81 y 1. El caso base es el exponente 0, y cualquier base elevada a 0 vale 1.

El máximo común divisor, por el algoritmo de Euclides, es recursivo por naturaleza: el MCD de a y b es el MCD de b y del resto de a entre b, hasta que el resto sea cero.

def mdc(a, b):
    if b == 0:
        return a
    return mdc(b, a % b)

print(mdc(48, 18))
print(mdc(17, 5))
print(mdc(100, 75))

La salida es 6, 1 y 25. En un programa de ESP32, el MCD tiene un uso concreto: si un LED debe parpadear cada 500 ms y otro cada 300 ms, el menor paso de tiempo que sirve a los dos es mdc(500, 300), que es 100 ms, y un temporizador único con ese paso basta. El artículo sobre programar sin colgarse trata de temporizadores y estados.

La suma de los dígitos de un número separa el último dígito (n % 10) del resto (n // 10):

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

print(soma_digitos(7))
print(soma_digitos(1234))
print(soma_digitos(99999))

La salida es 7, 10 y 45. Y la inversión de un texto usa rebanadas, texto[1:] para todo menos el primer carácter:

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

print(inverter("python"))
print(inverter("a"))
print(inverter(""))

La salida es nohtyp, a y una línea vacía. El caso base cubre el texto vacío y el de un carácter, y la función invierte el resto y pone el primer carácter al final.

Cuando la recursión no se detiene

El error clásico es la función sin caso base. Se llama a sí misma sin detenerse nunca, y la pila crece hasta que Python se rinde:

def contagem(n):
    print(n)
    contagem(n - 1)

contagem(3)

3
2
1
0
-1
...
-48
Traceback (most recent call last):
  File "main.py", line 5, in <module>
  File "main.py", line 3, in contagem
  File "main.py", line 3, in contagem
...
RuntimeError: maximum recursion depth exceeded

Los puntos ... indican líneas repetidas que se cortaron para caber en el artículo: en la salida real, son unas 50 líneas de números y otras tantas de File "main.py", line 3, in contagem. Lo que importa es la última línea, RuntimeError: maximum recursion depth exceeded. El Python del computador usa el nombre RecursionError, que es un tipo de RuntimeError, y el mensaje completo maximum recursion depth exceeded.

Hay tres formas comunes de equivocarse con la recursión. La primera, la que se vio, es olvidar el caso base. La segunda es escribir el caso base, pero no llegar a él:

def f(n):
    if n == 0:
        return 0
    return f(n + 1)

print(f(5))

Traceback (most recent call last):
  File "main.py", line 6, in <module>
  File "main.py", line 4, in f
  File "main.py", line 4, in f
...
RuntimeError: maximum recursion depth exceeded

El n + 1 aleja el argumento del 0, en lugar de acercarlo. Lo mismo ocurre con soma_ate(2.5): la secuencia 2.5, 1.5, 0.5, -0.5 nunca es igual a 0, y el caso base no se alcanza. Cuando el caso base es una igualdad, vale preguntar si el argumento puede saltar por encima de él. Escribir n <= 0 en lugar de n == 0 protege de esta clase de error.

La tercera es olvidar el return en el paso recursivo:

def soma(n):
    if n == 0:
        return 0
    n + soma(n - 1)

print(soma(3))

Traceback (most recent call last):
  File "main.py", line 6, in <module>
  File "main.py", line 4, in soma
  File "main.py", line 4, in soma
TypeError: unsupported types for __add__: 'int', 'NoneType'

La llamada soma(n - 1) devuelve None cuando falta el return, y la suma n + None falla. Es el mismo tropiezo del artículo sobre return, ahora dentro de una recursión. El Python del computador escribe unsupported operand type(s) for +: 'int' and 'NoneType'.

El límite de recursión

Ninguna plataforma deja crecer la pila sin fin. El Python del computador tiene un límite configurado, que por defecto es de unas mil llamadas. El MicroPython de la ESP32 tiene un límite mucho menor, que depende de la memoria disponible, porque cada llamada gasta memoria del aparato. El simulador del proyecto fue calibrado con una DevKit V1 para reproducir ese límite. Se puede medir con una función que cuenta cuántas llamadas aguanta:

profundidade = 0
def descer():
    global profundidade
    profundidade += 1
    descer()

try:
    descer()
except RuntimeError as e:
    print("paró en", profundidade, "llamadas")
    print(e)

La salida es paró en 53 llamadas y maximum recursion depth exceeded. El try y el except, que la serie todavía va a detallar, capturan el error para que el programa pueda contar y continuar, en lugar de detenerse con el traceback. En el Python del computador, el mismo programa cuenta cerca de mil llamadas. En ese límite aparecen dos efectos prácticos en el simulador:

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

for n in (10, 20, 30, 40, 45, 50, 60):
    try:
        print(n, fatorial(n))
    except RuntimeError as e:
        print(n, "error", e)

La salida muestra los factoriales de 10 a 50 (con números enormes: el de 20 ya es 2432902008176640000, y el de 50 tiene 65 dígitos) y termina en 60 error maximum recursion depth exceeded. Midiendo, el fatorial aguanta hasta 52 y falla en 53, y el soma_ate aguanta hasta 51 y falla en 52. La diferencia viene del tamaño de cada marco: las funciones con más variables locales gastan más por llamada y llegan antes al límite.

Dos cuidados valen aquí. El primero es que el número exacto cambia con la función y con la versión de MicroPython, así que los valores de arriba son del simulador y sirven como orden de magnitud: unas pocas decenas de llamadas, y no cientos. Quien necesita un número firme debe medir en su propia placa, con el programa de la función descer. El segundo es que el límite afecta a quien usa recursión para repetir tareas largas: recorrer mil lecturas con una función recursiva desborda la pila en una ESP32, y un bucle lo resuelve sin problema.

Fibonacci: la recursión que repite trabajo

La secuencia de Fibonacci, en que cada número es la suma de los dos anteriores, es la recursión favorita de los libros, y también el mejor ejemplo de su costo:

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

for i in range(10):
    print(fib(i), end=" ")
print()

chamadas = 0
def fib2(n):
    global chamadas
    chamadas += 1
    if n < 2:
        return n
    return fib2(n - 1) + fib2(n - 2)

for n in (5, 10, 15):
    chamadas = 0
    r = fib2(n)
    print(n, r, chamadas)

La salida es la secuencia 0 1 1 2 3 5 8 13 21 34 y las tres líneas 5 5 15, 10 55 177 y 15 610 1973. La segunda función cuenta cuántas llamadas se hicieron, con un global como en el artículo sobre alcance. Para calcular fib(15), el programa hace 1973 llamadas, casi 2 mil, para una secuencia de apenas 15 valores. El árbol de la figura muestra por qué: fib(3) se calcula dos veces y fib(2) tres veces, cada uno desde cero, y el desperdicio se duplica en cada nivel. La profundidad de la pila es pequeña, solo n niveles, y lo que crece es el tiempo.

La versión con bucle da una vuelta por valor:

def fib_laco(n):
    a = 0
    b = 1
    for i in range(n):
        a, b = b, a + b
    return a

for i in range(10):
    print(fib_laco(i), end=" ")
print()
print(fib_laco(30))

La salida es la misma secuencia y 832040. El fib_laco(30) da 30 vueltas, y la versión recursiva haría más de 2,6 millones de llamadas y agotaría el tiempo y la memoria en una ESP32. El a, b = b, a + b es una asignación múltiple: los dos lados se calculan antes de cualquier asignación.

Recursión o bucle

Todo lo que se hace con recursión se hace con bucle, y viceversa. La cuenta regresiva y el factorial, por ejemplo, quedan así:

def contagem_laco(n):
    while n > 0:
        print(n)
        n = n - 1
    print("¡fuego!")

contagem_laco(3)

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

print(fatorial_laco(10))
print(fatorial_laco(20))

La salida es 3, 2, 1, ¡fuego!, 3628800 y 2432902008176640000. La versión con bucle no apila nada y no tiene límite de profundidad. En la ESP32, es la elección por defecto. La recursión compensa cuando el problema es naturalmente recursivo y la profundidad es pequeña y conocida, como ocurre al dividir el problema por la mitad en cada paso (la búsqueda binaria, por ejemplo, necesita poco más de diez niveles para mil elementos) o al recorrer una estructura anidada.

Un criterio práctico:

• ¿La repetición tiene un tamaño que depende de los datos, como leer lecturas de un sensor? Usa bucle.
• ¿La solución se escribe naturalmente como "resuelve la versión menor y combina"? La recursión puede ser más clara, siempre que la profundidad sea pequeña.
• ¿La misma cuenta se repite muchas veces, como en el Fibonacci? Bucle, o guardar resultados ya calculados.
• ¿Duda? Escribe el bucle. No falla por profundidad.

En el aula: dónde suele tropezar la recursión

Estos casos se repiten en los grupos.

Olvidar el caso base

La más frecuente. El alumno escribe solo el paso, la función se llama a sí misma y el programa termina en RuntimeError. La pregunta de comprobación es: ¿en qué situación responde esta función sin llamarse a sí misma?

El caso base que nunca llega

El f(n + 1) o el n == 0 con n fraccionario. El alumno tiene un caso base, y el programa también desborda. La comprobación: ¿el argumento de la llamada está más cerca del caso base que el argumento actual?

Olvidar el return en el paso

La función devuelve None y la cuenta explota lejos de ahí, en un TypeError. En la recursión, el return tiene que aparecer en los dos lugares: en el caso base y en el paso.

Esperar que la cuenta ocurra en la ida

El alumno imagina que el fatorial(4) multiplica 4 por 3 y después por 2, en secuencia, hacia adelante. El print de entrada y salida muestra que la multiplicación solo ocurre en la vuelta. Seguir la pila en el papel, dibujando los marcos, deshace el error.

Usar recursión para todo

Después de aprender, el alumno resuelve incluso la suma de una lista con recursión. Funciona con cinco elementos y desborda con cien. El bucle sería más corto y sin riesgo.

Fibonacci recursivo con números grandes

El programa corre bien con fib(10) y parece colgado con fib(35). No está colgado, solo repite una cantidad enorme de cuentas. La tabla de la figura muestra el crecimiento.

Ejercicio: decimal a binario

Escribe una función recursiva binario(n) que devuelva el número n en binario, como texto. La idea: el último dígito binario es el resto de la división entre 2, y el resto de los dígitos es el binario de n // 2. El caso base es cualquier número menor que 2, que ya es un dígito.

def binario(n):
    if n < 2:
        return str(n)
    return binario(n // 2) + str(n % 2)

print(binario(0))
print(binario(10))
print(binario(255))

La salida es 0, 1010 y 11111111. El binario(10) calcula binario(5) y junta el dígito 0, que calcula binario(2) y junta 1, que calcula binario(1), el caso base, y junta 0, lo que resulta en 1, 0, 1, 0. Para mejorarlo, rehaz la función con un bucle while y compara, y después comprueba con la función incorporada bin(10), que devuelve '0b1010'. La profundidad aquí es solo el número de dígitos binarios, como máximo 8 para el 255, lo que cabe con holgura en el límite del simulador.

Preguntas frecuentes

¿Qué es un caso base?

Es la situación más simple de una función recursiva, en que responde sin llamarse a sí misma. Sin él, la recursión no termina.

¿Por qué el límite de recursión es menor en la ESP32?

Cada llamada guarda un marco con variables locales en la memoria, y la ESP32 tiene mucha menos memoria que un computador. MicroPython limita la profundidad para no agotar la pila del aparato.

¿Puedo aumentar el límite de recursión?

En el Python del computador, con sys.setrecursionlimit. En el MicroPython de la placa, el límite depende de la memoria, y la salida es reducir la profundidad: usar un bucle, o dividir el problema por la mitad en cada paso.

¿Toda recursión puede volverse bucle?

Puede. Algunas quedan más largas, porque el bucle necesita guardar en una estructura lo que la pila guardaba sola, pero siempre es posible.

¿La recursión es más rápida que el bucle?

En general, no. Cada llamada tiene un costo, y el bucle suele ser igual o más rápido. La ventaja de la recursión es la claridad en ciertos problemas, y no la velocidad.

¿La ruta tiene un desafío de recursión?

No hay un desafío solo de recursión. Los de funciones, como Función Doble, se resuelven sin ella, y el factorial, el MCD y el binario de este artículo sirven de práctica.

Para continuar

Relee los artículos sobre return y alcance de variables, porque la recursión depende de los dos: cada llamada tiene sus propias variables locales y entrega el valor por return. La ruta Lógica con Python no tiene un desafío solo de recursión, y los ejercicios de este artículo cumplen ese papel.

El próximo artículo cierra el módulo de funciones con lambda, map, filter y sorted con key: funciones pequeñas, escritas en una línea, y las funciones incorporadas que las reciben como argumento.