Recursión
Al aprender programación, a menudo abordamos tareas de manera lineal y directa. Pero, ¿qué sucede si nos encontramos con un problema que requiere descomponerlo en problemas más pequeños y similares? Ahí es donde se utiliza la recursión.
En términos sencillos, la recursión ocurre cuando una función se llama a sí misma durante su ejecución. Esto podría sonar como si creara un bucle infinito, pero si diseñamos nuestra función correctamente, eventualmente llegará a un punto en el que ya no se llame a sí misma.
Imagina una muñeca Matrioska. Cada vez que abres una muñeca, hay una más pequeña dentro, y continúas hasta que llegas a la muñeca más pequeña que no se puede abrir. Este proceso de abrir muñecas es un poco como la recursión. Para llegar a la muñeca más pequeña, que es como resolver el problema más difícil, lo solucionas resolviendo repetidamente versiones más simples del mismo problema (abriendo las muñecas más grandes) hasta que llegas a un punto en el que el problema no puede reducirse más (la última muñeca).
El proceso de resolver un gran problema dividiéndolo recursivamente en problemas más pequeños hasta alcanzar el más pequeño/fácil posible se entiende mejor con el concepto del “salto de fe recursivo”.
El Salto de Fe Recursivo
Al implementar una solución recursiva a un problema, generalmente se crea una función que funciona llamándose a sí misma en algún punto. La parte donde se llama a sí misma se denomina usualmente llamada recursiva.
La gran ventaja de las soluciones recursivas es que uno puede asumir que la función funciona correctamente cuando se llama con algunos argumentos simples, y luego implementar el comportamiento correcto para los más complejos. Similar a llamar a otras funciones como
sqrt, max, abs y otras que hemos estado usando antes, puedes asumir que la función funciona para algunos argumentos más pequeños/simples y llamarlos para construir el resultado actual sobre esos.💡
¡El único requisito es asegurarse de que la función llegará al caso base (el caso más simple). De lo contrario, tendríamos una función recursiva que se ejecuta infinitamente y podríamos obtener un StackOverflow!
Como una demostración de cómo se podría realizar un cálculo dentro de una función recursiva, podemos intentar calcular la suma de todos los números desde
0, 1, 2, …, n dado un número n.Vamos a implementar la función
sum paso a paso. El primer paso es asegurarse de que la función funciona correctamente para el caso más simple (contar correctamente la suma cuando n es 0 o 1):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # Si n es 0 => la suma es 0
return 0 # Detener aquí la ejecución de la función
if n == 1: # Si n es 1 => la suma es 1
return 1 # Detener aquí la ejecución de la función
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (ya que no hemos implementado esta parte)Con esta parte de la función, ya podemos usar el hecho de que
sum(0) siempre devolverá correctamente 0, mientras que sum(1) siempre devolverá 1. La función funcionará correctamente incluso si llamamos a la función sum con argumentos 0 o 1 desde la propia función sum.Entonces, podemos ir un paso más allá e implementar la función
sum para n = 2 y n = 3 utilizando los resultados de sum(1) y sum(0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # Si n es 2, podemos sumar 2 al resultado de sum(1) implementado arriba
return n + sum(1) # o n + sum(n - 1)
if n == 3: # Si n es 3, podemos sumar 3 al resultado de sum(2) implementado arriba
return n + sum(2) # o n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (ya que no hemos implementado esta parte)De esta manera, es obvio que la función
sum funciona correctamente para casos pequeños como cuando n es igual a 0, 1, 2 o 3.Con esto, podemos implementar la función para otros valores de
n mayores que 3. El único requisito es llegar a esos valores más pequeños de n (0, 1, 2 o 3) cuando llamamos a la función sum desde sí misma. Entonces, para valores mayores de n, como 4, 5 o 6, etc., podemos implementar la función sum utilizando el hecho de que para calcular sum(4), podemos sumar 4 al resultado de sum(3), mientras que calcular sum(5) se puede hacer sumando 5 al resultado de sum(4):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# Para todos los otros casos (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...Las partes clave de una función recursiva son:
- Caso base: Una condición que detiene la recursión. Sin esto, la función se llamaría a sí misma indefinidamente, causando un bucle infinito.
Aquí, es
n == 0yn == 1.
- Paso recursivo: Donde la función se llama a sí misma, generalmente con un argumento diferente.
Aquí, es
sum(n - 1).
Dado que las llamadas para
n == 1, n == 2 y n == 3 son exactamente iguales que para n == 4, n == 5, etc., podemos incluso simplificar la función sum teniendo solo 1 caso base (para n == 0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...De esta manera, teniendo el salto de fe recursivo, asumimos/sabemos que la función funciona correctamente para casos más pequeños/simples, y construimos el resto de la función basándonos en esos casos más simples. Eso ayuda a entender cómo funcionan las funciones recursivas y cómo pueden implementarse.
💡
Llamar a la función recursivamente es como llamar a una función completamente diferente que sabes con certeza que funcionará con los argumentos pasados.