Recursion · Recursión
A function that calls itself
- Recursion is when a function calls itself.
- Each call should work on a smaller version of the problem.
- Done right, the problem shrinks until it is trivial to solve.
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.
Base case and recursive case
- The base case is the simplest case — it stops the recursion.
- The recursive case calls the function again on a smaller input.
- Without a base case the function never stops (an error).
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)
A worked example: factorial
- The factorial
n!meansn × (n-1) × ... × 1. - In recursive form:
n! = n × (n-1)!, and the base case is0! = 1. - Each call multiplies
nby the factorial of one less.
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))
How the computer runs it
- Each call is paused on a call stack while it waits for the inner call.
- When the base case returns, the paused calls finish one by one.
- Too many calls overflow the stack — Python raises a
RecursionError.
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.
In Cambridge pseudocode
- A recursive function names its base case and recursive case clearly.
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
Common mistakes
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
Errores comunes
- Toda recursividad necesita un caso base, o desbordará la pila de llamadas.
- Cada llamada debe acercarse al caso base.
Now you try
- Give each function a base case and a recursive case.
- Press Check answer to test your code.
Ahora tú prueba
- Asigna a cada función un caso base y un caso recursivo.
- Pulsa Comprobar respuesta para probar tu código.
Recursion returns from the leaves · La recursión regresa desde las hojas
Each call splits into smaller calls; answers return up from the base cases. · Cada llamada se divide en llamadas más pequeñas; las respuestas regresan hacia arriba desde los casos base.
Write a recursive sum_to(n) that returns 1 + 2 + ... + n. The base case is sum_to(0) which is 0. · Escribe una función sum_to(n) recursiva que devuelva 1 + 2 + ... + n. El caso base es sum_to(0) que es 0.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write a recursive power(base, exp) that returns base raised to exp. The base case is exp == 0, which gives 1. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write a recursive count_up(n) that returns the list [1, 2, ..., n]. The base case is count_up(0) which is the empty list []. · 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 [].
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.