¿Alguna vez te has visto atrapado en un ciclo aparentemente interminable en el que un problema sigue ramificándose en fragmentos más pequeños?
Si es así, es posible que haya llegado al apasionante mundo de la recursividad. Si bien puede parecer difícil de entender, ¡no se preocupe! En esta publicación, emprenderemos un viaje interesante para aprender sobre los tipos de recursiones.
Así que abróchese el cinturón mientras exploramos numerosos enfoques recursivos. Prepárese para ingresar al fascinante reino de la recursividad y observe su notable habilidad para resolver problemas complicados.
¿Qué son exactamente las recurrencias?
En palabras básicas, la recursividad es una poderosa técnica de programación que incluye una función que se llama a sí misma durante la ejecución. Es como mirarse en un espejo y ver una imagen dentro de una imagen, lo que da como resultado un ciclo autorreferencial.
Podemos abordar grandes problemas utilizando la recursividad dividiéndolos en subproblemas más pequeños y manejables.
Es similar a armar un rompecabezas, donde una pieza se une a otras partes para producir una imagen completa. La recursividad nos permite resolver problemas de una manera elegante y eficiente al repetir el mismo conjunto de instrucciones con varias entradas.
1-Recursión directa
La recursión directa es el tipo más básico de recursión, en el que una función se llama a sí misma directamente. Implica dividir un problema problemático en subproblemas más pequeños hasta lograr un caso base, lo que conduce a la terminación.
La función recursiva se llama a sí misma con varias entradas, lo que permite repetir la ejecución del mismo conjunto de instrucciones. Cada invocación se basa en la anterior, acercándose progresivamente al caso base que hace que finalice la recursividad.
Veamos este ejemplo.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Salida:
5
4
3
2
1
2-Recursión indirecta
La recursividad indirecta agrega un giro intrigante a la ruta recursiva. A diferencia de la recursividad directa, que involucra una función que se llama a sí misma explícitamente, la recursividad indirecta incluye una cadena de llamadas a funciones.
Una función llama a otra, que luego puede llamar a la función original o a cualquier otra función que finalmente vuelva a la original. Esta red interconectada de llamadas a funciones produce una fascinante danza en la que varias funciones colaboran para solucionar un problema.
Ejemplo:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Salida:
A: 3
B: 2
A: 1
Recursión 3-Lineal
Considere un viaje por una ruta recta, un paso a la vez, hasta llegar a su objetivo. Esta técnica secuencial está representada por la recursividad lineal, en la que una función realiza una sola llamada recursiva en cada iteración de la función.
Con cada llamada recursiva, el proceso recursivo se acerca a un caso base al reducir el tamaño del problema. Procede de manera clara y lineal, resolviendo los subproblemas de uno en uno hasta llegar a la respuesta final.
Ejemplo:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Salida:
120
Recursión de 4 árboles
Cuando una función se bifurca en varias llamadas recursivas, entramos en el mundo de la recursión de árboles. Una función en la recursividad del árbol genera muchas llamadas recursivas, cada una de las cuales resuelve un subproblema separado, tal como lo hacen las ramas de un árbol.
Esta estructura ramificada permite la investigación simultánea de varias rutas, desglosando problemas complicados en componentes interrelacionados más pequeños.
Ejemplo:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Salida:
8
Recursividad de 5 anidados
La recursividad anidada agrega un emocionante grado de complejidad al universo recursivo. En esta forma de recursividad, una función incorpora una llamada recursiva como argumento dentro de otra llamada recursiva.
La llamada recursiva interna actúa sobre un valor que depende de la llamada recursiva externa. La complejidad crece con cada invocación anidada, culminando en un patrón intrigante de llamadas recursivas anidadas.
Ejemplo:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Resultado:
91
Recursión de 6 colas
La recursión de cola es una técnica de optimización para algoritmos recursivos que puede mejorar su rendimiento. La llamada recursiva aparece como la acción final de una función con cola recursiva, haciendo.
Debido a que no hay operaciones pendientes después de la llamada recursiva, el compilador o el intérprete pueden simplificar la recursividad reemplazándola con un simple salto.
Este enfoque de optimización, conocido como optimización de llamada final, reduce el requisito de que cada llamada recursiva retenga un marco de pila, lo que da como resultado una mayor velocidad y un menor uso de memoria.
Ejemplo:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Fuera fuera:
120
7-Recursividad sin cola
A diferencia de la recursividad de cola, la recursividad sin cola implica actividades adicionales realizadas después de la llamada recursiva dentro de una función. Antes de que se puedan realizar más acciones, cada llamada recursiva debe completarse y regresar.
Como consecuencia, hasta que se alcanza el caso base y finaliza la recursión, se mantiene una pila de operaciones pendientes. La recursión sin cola con frecuencia usa más memoria y es menos eficiente que la recursión de cola, pero sigue siendo una herramienta útil para abordar una variedad de problemas.
Ejemplo:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Salida:
15
Envolver
La recursividad es un concepto intrigante en la programación. Nos permite abordar problemas complicados de manera recursiva y autorreferencial.
Ofrece un método distinto para pensar y resolver problemas, dividiéndolos en partes más pequeñas y manejables. Sin embargo, cuando se trabaja con recursividad, es fundamental prestar atención a algunos puntos.
Debe identificar casos base adecuados que permitan que finalice la recursividad. Si no están presentes, la función puede continuar llamándose a sí misma para siempre.
En segundo lugar, en función del escenario en cuestión, la selección del tipo de recursividad adecuado puede conducir a soluciones más eficientes y elegantes. Trate de encontrar lo que funciona mejor para el problema en la mano. Cuando trabaje con grandes profundidades de recursión, tenga en cuenta los peligros potenciales, como el desbordamiento de pila.
Deje un comentario