Una carpeta dentro de otra carpeta
La recursividad es una técnica en la que una función se llama a sí misma para resolver un problema más pequeño. Sirve cuando el problema contiene una versión más pequeña de sí mismo.
Una carpeta contiene archivos y otras carpetas, que a su vez contienen más. Para sumar su tamaño, sumas sus archivos y repites lo mismo con cada subcarpeta.
Al final de esta lección
Nota
Puedo escribir una función recursiva con su caso base.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Recursividad | una función que se llama a sí misma | |
| Caso base | el caso tan pequeño que se responde sin llamarse | |
| Caso recursivo | el caso que se reduce a uno más pequeño | |
| Pila de llamadas | la lista de llamadas que esperan su resultado | |
| Factorial | el producto de 1 hasta n | 4! = 24 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Toda función recursiva tiene dos casos
El caso base es tan pequeño que la función lo responde sin llamarse. Es lo que detiene la cadena.
El caso recursivo reduce el problema a uno más pequeño y llama a la función con él. El factorial de 4 es 4 por el factorial de 3, y así hasta llegar al factorial de 1.
Un factorial recursivo
# Factorial: 4! es 4 * 3 * 2 * 1.
def factorial(n):
# Caso base: el factorial de 0 o de 1 es 1.
if n <= 1:
return 1
# Caso recursivo: n por el factorial del número anterior.
return n * factorial(n - 1)
print(factorial(4))
print(factorial(10))
# Prueba con factorial(5).
La pila de llamadas guarda lo que espera
Cada llamada espera el resultado de la siguiente. Python guarda las llamadas pendientes en la pila de llamadas.
Al llegar al caso base, la última llamada responde. Entonces las demás terminan una a una, en orden inverso. Python limita la pila: una cadena demasiado larga da un error.
Las llamadas de factorial(4)
| Llamada | Espera | Devuelve |
|---|---|---|
| factorial(4) | 4 * factorial(3) | 24 |
| factorial(3) | 3 * factorial(2) | 6 |
| factorial(2) | 2 * factorial(1) | 2 |
| factorial(1) | Nada: es el caso base | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El límite de llamadas pendientes en Python
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 error frecuente
Advertencia
Mucha gente escribe solo el caso recursivo y cree que la función terminará sola. No termina: cada llamada pide otra. Escribe siempre el caso base primero, y comprueba que cada llamada se acerca a él.
Una carpeta se recorre recursivamente
Recorrer carpetas es recursivo: cada carpeta contiene el mismo problema, más pequeño. El caso base es un archivo, que se cuenta sin entrar en nada.
La orden find hace justo eso. Los dos Runs cuentan los archivos y las carpetas de projects, en la copia recién arrancada del laboratorio.
Cuenta los archivos de projects
find ~/projects -type f | wc -lSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Cuenta las carpetas de projects
find ~/projects -type d | wc -lSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Fibonacci repite trabajo
En los números de Fibonacci, cada uno es la suma de los dos anteriores. Escrito con recursividad es muy corto. Pero cada llamada lanza otras dos.
Con n igual a 5 hay 15 llamadas. Con 10 hay 177. Con 20 hay 21.891. El trabajo crece muy deprisa, y la próxima lección explica por qué.
Fibonacci recursivo y sus llamadas
# Fibonacci recursivo, contando las llamadas.
calls = 0
def fib(n):
global calls
calls = calls + 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(5), "con", end=" ")
print(calls, "llamadas")
# Cambia fib(5) por fib(10) y mira las llamadas.