Recursión
Una función que se llama a sí misma
- La recursividad es cuando una función se llama a sí misma.
- Cada llamada debe trabajar con una versión más pequeña del problema.
- Si se hace correctamente, el problema se reduce hasta ser trivial de resolver.
Caso base y caso recursivo
- El caso base es el caso más simple: detiene la recursividad.
- El caso recursivo vuelve a llamar a la función con una entrada más pequeña.
- Sin un caso base, la función nunca se detiene (error).
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
Ejemplo resuelto: factorial
- El factorial
n!significan × (n-1) × ... × 1. - En forma recursiva:
n! = n × (n-1)!, y el caso base es0! = 1. - Cada llamada multiplica
npor el factorial de uno menos.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
Cómo lo ejecuta el ordenador
- Cada llamada se pausa en una pila de llamadas mientras espera la llamada interna.
- Cuando el caso base devuelve un valor, las llamadas pausadas terminan una tras otra.
- Demasiadas llamadas desbordan la pila — Python lanza un
RecursionError.
En pseudocódigo de Cambridge
- Una función recursiva nombra claramente su caso base y su caso recursivo.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
Errores comunes
- Toda recursividad necesita un caso base, o desbordará la pila de llamadas.
- Cada llamada debe acercarse al caso base.
Ahora tú prueban
- Asigna a cada función un caso base y un caso recursivo.
- Pulsa Check answer para probar tu código.
La recursión regresa desde las hojas
Cada llamada se divide en llamadas más pequeñas; las respuestas regresan hacia arriba desde los casos base.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe una función sum_to(n) recursiva que devuelva 1 + 2 + ... + n. El caso base es sum_to(0) que es 0.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe una función power(base, exp) recursiva que devuelva base elevado a la potencia de exp. El caso base es exp == 0, lo cual da como resultado 1.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 4/5 · 280 monedas + un pequeño bono en el primer intento de hoy
Escribe una función count_up(n) recursiva que devuelva la lista [1, 2, ..., n]. El caso base es count_up(0) que es la lista vacía [].
Haz clic en Ejecutar para ver la salida aquí.