Imagina una caja de espejos donde cada espejo refleja lo que ve en el siguiente, creando una serie infinita de reflejos. La recursión en programación es algo similar. Es una técnica donde una función se llama a sí misma directa o indirectamente[^1^]. Esto crea un ciclo en el cual la función resuelve un problema dividiéndolo en instancias más pequeñas del mismo problema, hasta llegar a un caso base sencillo de resolver.
Por ejemplo, imaginemos una función que imprime un contador regresivo:
def cuenta_regresiva(numero):
if numero > 0:
print(numero)
cuenta_regresiva(numero - 1)
else:
print("¡Despegue!")
cuenta_regresiva(5)
Esta función se llama recursivamente reduciendo el número cada vez hasta llegar a 0, y luego imprime el mensaje de despegue.
La recursión es un enfoque declarativo donde se enfoca en dividir un problema en casos recursivos sin necesidad de controlar explícitamente el bucle usando iteradores o contadores como en la programación imperativa.
El poder de la recursión radica en su simplicidad. Sin embargo, es esencial entender su estructura para evitar caer en trampas comunes. Una función recursiva típica tiene dos partes principales1:
El factorial de un entero positivo \(n\) es el producto de todos los enteros positivos menores o iguales a \(n\). Por ejemplo:
Aquí está el código en Python para calcular el factorial usando recursión:
def factorial(n):
if n == 1:
return 1 # Caso base
return n * factorial(n-1) # Caso recursivo
Digamos que quieres calcular el factorial de \(5\), así que llamas a factorial(5)
.
Esto es lo que sucede:
factorial(4)
, luego multiplica el resultado por \(5\).factorial(4)
, \(n = 4\), entonces la función llama a factorial(3)
, luego multiplica el resultado por \(4\).factorial(3)
, \(n = 3\), así que llama a factorial(2)
, luego multiplica el resultado por \(3\).factorial(2)
, \(n = 2\), así que llama a factorial(1)
, luego multiplica el resultado por \(2\).factorial(1)
alcanza el caso base, donde \(n = 1\), así que retorna \(1\).Ahora los resultados se desenrollan:
factorial(2)
retorna \(2 * 1 = 2\)factorial(3)
retorna \(3 * 2 = 6\)factorial(4)
retorna \(4 * 6 = 24\)factorial(5)
retorna \(5 * 24 = 120\)El resultado final es \(120\), que es el valor de \(5!\).
Aquí hay una representación visual de la pila de llamadas:
factorial(5)
-> factorial(4)
-> factorial(3)
-> factorial(2)
-> factorial(1)
return 1
return 2
return 6
return 24
return 120
La serie de Fibonacci es una secuencia de números donde cada número es la suma de los dos anteriores. Comienza con \(0\) y \(1\), y cada número posterior es la suma de los dos números anteriores. Los primeros números de la secuencia son: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …\)
Aquí está el código en Python para calcular el \(n^th\) número de Fibonacci usando recursión de cola:
def fibonacci(n, a=0, b=1):
if n == 0:
return a
return fibonacci(n-1, b, a+b)
La función toma tres parámetros:
Aquí hay un desglose de cómo funciona la función:
Caso Base: Si \(n\) es \(0\), la función devuelve \(a\). Este es el valor del \(n^th\) número en la secuencia.
Caso Recursivo: Si \(n\) no es \(0\), la función se llama a sí misma con \(n-1\), \(b\), y \(a+b\). Estos parámetros cambian la posición en la secuencia y preparan los siguientes números para la suma.
Supongamos que queremos encontrar el \(5^th\) número en la secuencia de Fibonacci llamando a fibonacci(5)
.
Esto es lo que sucede:
fibonacci(4, 1, 1)
(porque \(a = 0\), \(b = 1\), \(a + b = 1\)).fibonacci(3, 1, 2)
(porque \(a = 1\), \(b = 1\), \(a + b = 2\)).fibonacci(2, 2, 3)
(porque \(a = 1\), \(b = 2\), \(a + b = 3\)).fibonacci(1, 3, 5)
(porque \(a = 2\), \(b = 3\), \(a + b = 5\)).fibonacci(0, 5, 8)
(porque \(a = 3\), \(b = 5\), \(a + b = 8\)).El resultado es \(5\), que es el \(5^th\) número en la secuencia de Fibonacci.
Aquí hay una representación visual de la pila de llamadas:
fibonacci(5, 0, 1)
-> fibonacci(4, 1, 1)
-> fibonacci(3, 1, 2)
-> fibonacci(2, 2, 3)
-> fibonacci(1, 3, 5)
-> fibonacci(0, 5, 8)
return 5
La recursión tiene ciertas ventajas2:
Las desventajas incluyen:
Por lo tanto, la recursión es una herramienta poderosa que debe usarse con discreción en los casos apropiados.
La recursión y la iteración (usando ciclos) son paralelos y podemos usar cualquiera para resolver muchos problemas. Ambas técnicas tienen el potencial de resolver los mismos problemas, pero su implementación y eficiencia pueden variar. Tomemos el ejemplo del factorial:
Iterativo
def factorial_iterativo(n):
resultado = 1
for i in range(1, n+1):
resultado *= i
return resultado
Recursivo
def factorial_recursivo(n):
if n == 1:
return 1
return n * factorial(n-1)
La versión iterativa es más eficiente en términos de espacio, pero la recursiva es más limpia y fácil de entender. La elección entre recursión e iteración a menudo depende del problema específico, las restricciones de memoria y las preferencias del programador.
La recursión es una técnica clave que permite escribir algoritmos elegante, naturales y eficientes si se utiliza adecuadamente. Entender cómo dividir un problema en casos recursivos es esencial para dominar esta habilidad. La recursión ofrece una alternativa declarativa única para resolver problemas complejos sin necesidad de administrar bucles explícitos. Sin embargo, es crucial recordar siempre definir un caso base adecuado y ser consciente de las limitaciones de la recursión en términos de eficiencia y uso de memoria. Saber combinar recursión e iteración nos da flexibilidad al crear soluciones óptimas.
Como siempre, la clave está en encontrar el equilibrio adecuado y utilizar la herramienta correcta para el trabajo adecuado.
¡Felicitaciones por llegar hasta acá! Espero que este recorrido por el universo de la programación te haya resultado tan interesante como lo fue para mí al escribirlo.
Queremos conocer tu opinión, así que no dudes en compartir tus comentarios, sugerencias y esas ideas brillantes que seguro tenés.
Además, para explorar más allá de estas líneas, date una vuelta por los ejemplos prácticos que armamos para vos. Todo el código y los proyectos los encontrarás en nuestro repositorio de GitHub learn-software-engineering/examples.
Gracias por ser parte de esta comunidad de aprendizaje. ¡Seguí programando y explorando nuevas areas en este fascinante mundo del software!
¿Fue útil esta página?
¡Nos alegra mucho! Por favor dinos como podemos mejorar.
Nos apena que no te haya gustado. Por favor dinos como podemos mejorar.