Recursión en Python: cómo funciona, cuándo usarla y ejemplos

Q: ¿Qué sigue?

A continuación vienen map(), filter() y reduce(), las potentes herramientas de programación funcional de Python. Aprenderás a transformar, filtrar y combinar colecciones de datos en una sola línea.

Intermedio25 min6 ejercicios85 XP

Esta lección es una traducción del original en inglés.Read in English Avisar de un error de traducción

Antes de empezar

Funciones en Python: definir, llamar y devolver valores

0/6 ejercicios

Imagina un juego de muñecas rusas. Abres la más grande y encuentras una más pequeña dentro. Abres esa y hay otra todavía más pequeña. Sigues abriendo hasta llegar a la muñeca diminuta que ya no se abre: ese es el final.

La recursión funciona igual. Una función recursiva se llama a sí misma con una versión más pequeña del problema, una y otra vez, hasta llegar a un punto de parada. Es una de las técnicas más elegantes de la programación y, cuando por fin la entiendes, empiezas a verla por todas partes.

En este tutorial aprenderás qué es la recursión, cómo la pila de llamadas lleva la cuenta de cada paso, cuándo la recursión es la herramienta adecuada y cómo evitar los errores más comunes. Iremos de ejemplos sencillos a algoritmos clásicos como el factorial y Fibonacci.

¿Qué es la recursión?

Hay recursión cuando una función se llama a sí misma. Esa es toda la definición. Pero ¿por qué querrías que una función se llamara a sí misma?

Piensa en contar hacia atrás desde 5. Podrías describir el proceso así: "Para contar hacia atrás desde N, di N y después cuenta hacia atrás desde N menos 1. Detente al llegar a 0". Esa es una descripción recursiva: la instrucción se refiere a sí misma.

Una cuenta regresiva recursiva sencilla

def countdown(n):

if n == 0:

print("Go!")

return

print(n)

countdown(n - 1)

countdown(5)

Salida

5
4
3
2
1
Go!

La función countdown(5) imprime 5 y luego llama a countdown(4). Esa imprime 4 y llama a countdown(3). Así continúa hasta que countdown(0) imprime "Go!" y se detiene. No hay más llamadas.

Toda función recursiva tiene dos partes esenciales. Si falta alguna, la función se ejecutará para siempre (o hasta que Python la detenga).

El caso base: cuándo parar

El caso base es la condición que detiene la recursión. Es la muñeca más diminuta, la que no se abre. Sin un caso base, la función se llama a sí misma para siempre.

El caso recursivo es la parte en la que la función se llama a sí misma con una entrada más sencilla. Cada llamada debería acercarte al caso base.

Caso base frente a caso recursivo

def countdown(n):

# BASE CASE - the stopping condition

if n == 0:

print("Go!")

return

# RECURSIVE CASE - do work, then call with smaller input

print(n)

countdown(n - 1)

countdown(3)

Salida

3
2
1
Go!

Una buena regla práctica: escribe siempre el caso base primero. Después escribe el caso recursivo que avanza hacia él. Este orden evita que olvides por accidente la condición de salida.

Cómo funciona la pila de llamadas

Cuando una función se llama a sí misma, Python no olvida dónde estaba. Usa una pila de llamadas (call stack): una pila de "marcos" en la que cada marco recuerda las variables locales de la función y el punto donde debe continuar.

Piensa en ella como en un montón de notas adhesivas. Cada vez que llamas a una función, Python escribe una nota nueva con los datos de esa llamada y la coloca encima. Cuando una función termina, Python despega la nota de arriba y vuelve a la que estaba debajo.

La pila de llamadas en acción

def factorial(n):

print(f" Calling factorial({n})")

if n <= 1:

print(f" Base case! factorial({n}) = 1")

return 1

result = n * factorial(n - 1)

print(f" factorial({n}) = {n} * factorial({n-1}) = {result}")

return result

print("Result:", factorial(5))

Salida

  Calling factorial(5)
  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Base case! factorial(1) = 1
  factorial(2) = 2 * factorial(1) = 2
  factorial(3) = 3 * factorial(2) = 6
  factorial(4) = 4 * factorial(3) = 24
  factorial(5) = 5 * factorial(4) = 120
Result: 120

Fíjate en cómo los mensajes "Calling" bajan cada vez más hondo y luego los resultados suben de vuelta. La pila de llamadas crece a medida que entran las llamadas y se encoge a medida que salen los resultados. Este ir y volver es el latido de la recursión.

Ejemplos clásicos de recursión

Factorial

El factorial de un número N (que se escribe N!) es N multiplicado por cada entero positivo menor que él. Por ejemplo, 5! = 5 x 4 x 3 x 2 x 1 = 120.

El factorial es recursivo por naturaleza: 5! = 5 x 4!, y 4! = 4 x 3!, y así sucesivamente. El caso base es 1! = 1.

Factorial con recursión

def factorial(n):

if n <= 1: # Base case

return 1

return n * factorial(n - 1) # Recursive case

print(factorial(1)) # 1

print(factorial(5)) # 120

print(factorial(10)) # 3628800

Salida

1
120
3628800

Suma de una lista

Aquí tienes otro patrón: para sumar una lista de forma recursiva, suma el primer elemento a la suma del resto.

Suma recursiva de una lista

def sum_list(numbers):

if len(numbers) == 0: # Base case: empty list

return 0

return numbers[0] + sum_list(numbers[1:]) # First + sum of rest

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

print(sum_list([10])) # 10

print(sum_list([])) # 0

Salida

15
10
0

El patrón es: resolver el caso base (una lista vacía devuelve 0) y luego dividir el problema en "primer elemento" más "llamada recursiva sobre el resto". Este patrón sirve para muchas operaciones con listas.

Recursión frente a bucles: cuándo usar cada uno

Todo lo que puedes hacer con recursión también lo puedes hacer con un bucle. Entonces, ¿cuándo conviene elegir uno u otro?

Factorial recursivo

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

print(factorial(5))  # 120

Factorial iterativo (con un bucle)

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

print(factorial(5))  # 120

Para problemas sencillos como el factorial, los bucles suelen ser más rápidos y usan menos memoria. Cada llamada recursiva agrega un marco a la pila de llamadas, mientras que un bucle reutiliza las mismas variables.

La recursión brilla cuando el problema tiene forma de árbol o se repite a sí mismo a menor escala. Por ejemplo: explorar estructuras de carpetas, analizar datos anidados (como JSON o HTML) y recorrer árboles o grafos. En estos casos, la recursión produce un código más limpio y más corto.

Cuándo la recursión es la herramienta adecuada

La recursión destaca en problemas en los que hay que explorar todas las ramas de una estructura con forma de árbol. Aquí tienes un ejemplo práctico: aplanar una lista anidada.

Aplanar una lista anidada con recursión

def flatten(lst):

result = []

for item in lst:

if isinstance(item, list):

result.extend(flatten(item)) # Recursion for nested lists

else:

result.append(item)

return result

nested = [1, [2, 3], [4, [5, 6]], 7]

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

Salida

[1, 2, 3, 4, 5, 6, 7]

Intenta escribir esto sin recursión. Necesitarías una pila manual y llevar a mano la cuenta de muchas cosas. La versión recursiva casi se lee como lenguaje natural: "Para cada elemento, si es una lista, aplánala. Si no, guárdalo".

Errores comunes con la recursión

Error 1: no tener caso base

Incluye siempre un caso base

# DON'T run this - it would crash!

# def bad_countdown(n):

# print(n)

# bad_countdown(n - 1) # Never stops!

# The fix: add a base case

def good_countdown(n):

if n <= 0:

return

print(n)

good_countdown(n - 1)

good_countdown(5)

Salida

Error 2: no avanzar hacia el caso base

Cada llamada debe acercarse al caso base

# DON'T run this - n never decreases!

# def bad_factorial(n):

# if n <= 1:

# return 1

# return n * bad_factorial(n) # Oops! Should be n - 1

# The fix: make sure the argument changes

def good_factorial(n):

if n <= 1:

return 1

return n * good_factorial(n - 1) # n - 1 moves toward base case

print(good_factorial(5))

Salida

Ejercicios de práctica

Empieza por los más fáciles y ve subiendo. Cada ejercicio se apoya en lo que ya sabes. Recuerda: ¡escribe siempre primero el caso base!

Ejercicio 1: predice la salida recursiva

Predice la salida

Lee este código y predice la salida. Después escribe instrucciones print() que produzcan exactamente la misma salida.

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

mystery(3)

Fíjate en que el print(n) está después de la llamada recursiva. Piensa bien en el orden.

# Print the exact output of the code above

Ejercicio 2: suma recursiva de 1 a N

Escribe el código

Escribe una función recursiva llamada sum_to que reciba un entero positivo n y devuelva la suma de todos los números del 1 al n.

Por ejemplo: sum_to(5) debe devolver 1 + 2 + 3 + 4 + 5 = 15.

Caso base: sum_to(1) devuelve 1.

Imprime los resultados de sum_to(5) y sum_to(10) en líneas separadas.

def sum_to(n):

# Your code here

pass

print(sum_to(5))

print(sum_to(10))

Ejercicio 3: corrige la función de potencia

Corrige el error

Esta función recursiva debería calcular base elevado a la potencia exp (como base ** exp). Pero tiene dos errores.

Corrige los dos errores para que la salida sea:

8
1
81

def power(base, exp):

if exp == 0:

return 0

return base + power(base, exp - 1)

print(power(2, 3))

print(power(5, 0))

print(power(3, 4))

Ejercicio 4: Fibonacci recursivo

Escribe el código

Escribe una función recursiva llamada fibonacci que devuelva el n-ésimo número de Fibonacci.

La sucesión de Fibonacci empieza así: 0, 1, 1, 2, 3, 5, 8, 13, ...

Reglas:

fibonacci(0) devuelve 0

fibonacci(1) devuelve 1

Para n >= 2: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Imprime los resultados para n = 0, 1, 5 y 10 en líneas separadas.

def fibonacci(n):

# Your code here

pass

print(fibonacci(0))

print(fibonacci(1))

print(fibonacci(5))

print(fibonacci(10))

Ejercicio 5: invierte una cadena de forma recursiva

Escribe el código

Escribe una función recursiva llamada reverse que reciba una cadena y la devuelva invertida.

Por ejemplo: reverse("hello") debe devolver "olleh".

Pista: el último carácter más la inversión de todo lo demás, sin el último carácter.

Imprime los resultados de reverse("hello") y reverse("Python") en líneas separadas.

def reverse(s):

# Your code here

pass

print(reverse("hello"))

print(reverse("Python"))

Ejercicio 6: cuenta los dígitos de forma recursiva

Escribe el código

Escribe una función recursiva llamada count_digits que reciba un entero no negativo y devuelva cuántos dígitos tiene.

Por ejemplo:

count_digits(0) devuelve 1

count_digits(5) devuelve 1

count_digits(123) devuelve 3

count_digits(99999) devuelve 5

Pista: dividir entre 10 con // elimina el último dígito.

Imprime los resultados para 0, 5, 123 y 99999 en líneas separadas.

def count_digits(n):

# Your code here

pass

print(count_digits(0))

print(count_digits(5))

print(count_digits(123))

print(count_digits(99999))

Resumen

Lo que ya sabes sobre la recursión:

Concepto	Qué significa
Recursión	Una función que se llama a sí misma
Caso base	La condición que detiene la recursión
Caso recursivo	La parte que se llama a sí misma con una entrada más sencilla
Pila de llamadas	El sistema de Python para seguir las llamadas a funciones anidadas
Desbordamiento de pila	Lo que pasa cuando la recursión llega demasiado hondo (sin caso base)
Recursión frente a bucles	Bucles para repeticiones sencillas, recursión para problemas con forma de árbol

La regla de oro de la recursión: escribe siempre primero el caso base y asegúrate de que cada llamada recursiva avance hacia él. Si haces eso, puedes escribir cualquier función recursiva.

¿Qué sigue?

A continuación vienen [map(), filter() y reduce()](/python/python-map-filter-reduce), las potentes herramientas de programación funcional de Python. Aprenderás a transformar, filtrar y combinar colecciones de datos en una sola línea.

¿Qué es la recursión?

El caso base: cuándo parar

Cómo funciona la pila de llamadas

Ejemplos clásicos de recursión

Factorial

Suma de una lista

Recursión frente a bucles: cuándo usar cada uno

Cuándo la recursión es la herramienta adecuada

Errores comunes con la recursión

Error 1: no tener caso base

Error 2: no avanzar hacia el caso base

Ejercicios de práctica

Resumen

¿Qué sigue?

Tutoriales relacionados