Las muñecas rusas
La recursión es una función que se llama a sí misma para resolver un problema más pequeño. Es como una muñeca rusa: abres una y dentro hay otra igual, más pequeña.
Sirve para problemas que se repiten dentro de sí mismos, como las carpetas dentro de carpetas, y deja el código muy corto.
Al final de esta lección
Nota
Puedo escribir una función recursiva con su caso base.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Recursión | una función que se llama a sí misma |
| Caso base | el caso más pequeño, que se resuelve sin llamarse |
| Caso recursivo | el caso que se resuelve con una llamada a un problema menor |
| Llamada | el momento en que una función empieza a ejecutarse |
| Pila de llamadas | la lista de funciones que esperan una respuesta |
| RecursionError | el error de Python cuando hay demasiadas llamadas |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un problema grande se parte en otro menor
Para sumar una lista, puedes sumar el primer número y el resto de la lista. Pero "sumar el resto" es el mismo problema, con una lista más corta.
La función se llama a sí misma con la lista más corta. Así sigue, hasta llegar a una lista vacía, cuya suma ya sabes: 0.
Suma una lista de dos maneras
docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(sum(h[:5]), h[0] + sum(h[1:5]))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
El primero más el resto
El Run imprime 1053 1053. Es la suma de los cinco primeros alquileres, calculada dos veces.
La segunda suma es "el primero más la suma de los otros cuatro". Es justo la idea de la recursión.
La suma con recursión
def total(numbers):
# Caso base: una lista vacía suma 0.
if len(numbers) == 0:
return 0
# Caso recursivo: el primero más la suma del resto.
return numbers[0] + total(numbers[1:])
print(total([4, 7, 2]))
La pila de llamadas guarda lo que espera
Cuando total se llama a sí misma, la llamada anterior se queda esperando. Python las apila una encima de otra.
Al llegar al caso base, la última llamada devuelve su valor. Entonces las demás se van terminando, de arriba hacia abajo. Es la pila de la lección anterior.
Ejemplo resuelto: las respuestas de [4, 7, 2]
| Llamada | Espera | Devuelve |
|---|---|---|
| total([]) | Nada: es el caso base | 0 |
| total([2]) | 2 + total([]) | 2 |
| total([7, 2]) | 7 + total([2]) | 9 |
| total([4, 7, 2]) | 4 + total([7, 2]) | 13 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una cuenta atrás recursiva
def countdown(n):
if n == 0:
print("Despegue")
else:
print(n)
countdown(n - 1)
countdown(3)
# Cambia el 3 por otro número y mira qué pasa.
Un error frecuente
Advertencia
Mucha gente se olvida del caso base. Sin él, la función se llama para siempre y nunca llega al final. Python corta la pila de llamadas y da un RecursionError. Todo caso recursivo tiene que acercarse al caso base.
Una función sin caso base
def endless(n):
return n + endless(n - 1)
try:
endless(5)
except RecursionError:
print("Sin caso base, la pila de llamadas se llena")
Mira cuántas llamadas aguanta Python
docker exec jupyter python3 -c "import sys; print(sys.getrecursionlimit())"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un factorial es un producto recursivo
docker exec jupyter python3 -c "import math; print(math.factorial(5), 5 * math.factorial(4))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Qué dicen los dos Run
El primer Run imprime 1000: Python aguanta unas mil llamadas una dentro de otra, y después da un RecursionError.
El segundo imprime 120 120. El factorial de 5 es 5 por el factorial de 4. Cada factorial se apoya en uno menor: recursión pura.
Para ir más lejos: la mezcla recursiva
La ordenación por mezcla de la lección 2 se escribe mejor con recursión. Para ordenar una lista, ordenas su mitad izquierda, ordenas su mitad derecha y las mezclas.
El caso base es una lista de 0 o 1 elementos, que ya está ordenada. Prueba a escribirla en el cuaderno con tu función merge.