En el post de hoy trataremos un tema muy importante dentro de la programación, como es, la recursividad. Es cierto que es un término que cuando lo estudias por primera vez cuesta, pero es muy sencillito. La recursividad es una técnica de programación en la que una función se llama a sí misma para resolver un problema.
¿Qué es la Recursividad?
La recursividad es un concepto fundamental en programación donde una función se llama a sí misma para resolver un problema más pequeño dentro del mismo problema. Este concepto se indica cuando un método se llama a sí mismo. Una función es recursiva cuando se invoca a sí misma. Consiste en dividir un problema complejo en subproblemas más pequeños. Esta técnica es especialmente útil para resolver problemas que pueden dividirse en subproblemas idénticos o similares. En la recursividad, cada llamada recursiva trabaja en un subconjunto más pequeño del problema original hasta que se alcanza un caso base que no requiere más subdivisión, lo que permite que la recursión termine.
La recursividad se considera una herramienta poderosa para resolver problemas complejos porque permite descomponer problemas grandes e intrincados en subproblemas más pequeños y manejables. Al resolver estos subproblemas de forma recursiva y combinar sus soluciones, se puede resolver el problema original. Las soluciones recursivas suelen ser elegantes y concisas, ya que aprovechan la estructura recursiva inherente al problema. Esto convierte a la recursividad en una técnica valiosa para abordar problemas de naturaleza recursiva o de divide y vencerás.
Componentes Clave de la Recursividad: El Caso Base y el Caso Recursivo
En general, una función recursiva tiene al menos dos partes: una condición base y al menos un caso recursivo.
- Caso Base: Un caso base es la condición que permite que el algoritmo detenga la recursividad. Es un problema que es lo suficientemente pequeño como para resolverlo directamente. Una función recursiva es llamada para resolver un problema; la función de hecho, sabe sólo cómo resolver el caso más simple, es decir, el llamado caso base. Uno o más casos base son casos para los que existe una solución directa. Siempre ha de existir uno o más casos base para los que la función devuelve un valor directo, es decir, sin hacer uso de recursión. El caso base proporciona una condición que, cuando se cumple, permite que la recursión termine y que la función comience a desenrollarse.
- Caso Recursivo: Si la función es llamada con un problema más complejo, la función divide dicho problema en dos partes conceptuales: una parte que la función ya sabe cómo ejecutar y una parte que la función no sabe cómo ejecutar. En el caso recursivo se llama recursivamente a la función y ha de hacerse de forma que el argumento de la llamada tienda a alcanzar el valor de un caso base. La última ley es que el algoritmo debe llamarse a sí mismo. Esta es la definición misma de la recursividad.
Para obedecer a este principio, debemos organizar un cambio de estado que mueva el algoritmo hacia el caso base. Un cambio de estado significa que se modifican algunos datos que el algoritmo está usando. Por lo general, los datos que representan nuestro problema se hacen más pequeños de alguna manera.
Lea también: IVA 21% Excel
Manejar cuidadosamente la validación de la entrada y las condiciones de terminación en las funciones recursivas es vital para asegurar la corrección y terminación de la recursión. Una correcta validación de la entrada garantiza que la función opera con una entrada válida, evitando comportamientos inesperados o errores. Además, la definición de condiciones de terminación precisas, a menudo en forma de casos base, garantiza que la recursividad finalmente se detiene. Sin estas precauciones, las funciones recursivas pueden mostrar un comportamiento incorrecto, bucles infinitos o errores de desbordamiento de pila.
Funcionamiento Interno: La Pila de Llamadas
Cuando llamamos a una función, un contexto de ejecución se coloca en la pila de ejecución. Una pila (stack) es una estructura de datos que opera sobre la base de "último en entrar, primero en salir". Un elemento es “apilado” (push) sobre una pila para añadirlo a esta, y un elemento es “retirado” (pop) de la pila para quitarlo. Usar una pila es un método para ordenar ciertas operaciones para su ejecución.
Un contexto de ejecución se forma una vez que una función se invoca. Este contexto se coloca a sí mismo en una pila de ejecución, un orden de operaciones. El elemento que siempre está primero en esta pila es el contexto de ejecución global. Seguido de este están los contextos creados por una función. Estos contextos de ejecución tienen propiedades, un Objeto de Activación y un enlace “this”. El enlace “this” es una referencia a este contexto de ejecución. El objeto de activación incluye: parámetros pasados, variables declaradas, y declaraciones de funciones. Así que cada vez que colocamos un nuevo contexto en la pila, usualmente tenemos todo lo que necesitamos para ejecutar código.
Con recursión, nosotros estamos esperando valores de retorno que vienen de otros contextos de ejecución. Estos otros contextos están más arriba en la pila. Cuando el último elemento en la pila termina la ejecución, ese contexto genera un valor de retorno. Este valor de retorno se pasa como un valor devuelto del caso recursivo al siguiente elemento. Ese contexto de ejecución luego es sacado de la pila. Donde vuelve a crear en la pila los nuevos parámetros y variables locales.
La pila de llamadas es una estructura de datos utilizada por los programas para gestionar las llamadas a funciones. En las funciones recursivas, cada llamada recursiva introduce un nuevo marco en la pila de llamadas, que almacena información sobre las variables de la función y el contexto de ejecución. Mientras la condición base sea falsa, seguiremos colocando contextos de ejecución encima de la pila. Es esencial gestionar correctamente la pila de llamadas para evitar errores de desbordamiento de pila, que se producen cuando el tamaño de la pila supera la memoria disponible.
Lea también: Guía IVA reducido
Ventajas y Desventajas de la Recursividad
Ventajas de la Recursividad
- Claridad y simplicidad: La recursividad puede conducir a una implementación más clara y concisa de algoritmos, especialmente para problemas que tienen una estructura recursiva natural. El uso de la recursividad produce una solución elegante que es más legible.
- Facilita la solución de problemas dividiendo: Al dividir un problema en subproblemas más pequeños y similares, la recursividad puede simplificar la solución de problemas complejos, ya que cada subproblema se puede resolver de manera independiente. Subproblemas son más fáciles de resolver que el problema original. Soluciones a subproblemas son combinadas para resolver el problema original.
- Promueve la reutilización del código: Una función recursiva bien diseñada puede ser reutilizada en diferentes contextos, lo que puede mejorar la modularidad y la mantenibilidad del código.
- Facilita la implementación de estructuras de datos recursivas: La recursividad es esencial para la implementación de estructuras de datos como árboles y grafos, que tienen una naturaleza recursiva intrínseca.
- Capacidad para resolver problemas con estructura recursiva natural: Las ventajas de la recursividad incluyen la concisión y la elegancia del código, así como la capacidad de resolver problemas que tienen una estructura recursiva de forma natural.
Desventajas de la Recursividad
- Consumo de memoria: En algunos casos, la recursividad puede consumir más memoria que un enfoque iterativo equivalente debido a la pila de llamadas, lo que puede resultar en desbordamientos de pila (stack overflow) si se utiliza en problemas con profundidad recursiva significativa. La aplicación tiene una cantidad limitada de espacio para las variables locales. Cada vez que un procedimiento se llama a sí mismo, usa más espacio para copias adicionales de sus variables locales.
- Eficiencia: En comparación con los enfoques iterativos, la recursividad puede ser menos eficiente en términos de tiempo de ejecución y consumo de recursos, especialmente para problemas que se pueden resolver de manera más eficiente con bucles. Un bucle no tiene la sobrecarga de pasar argumentos, inicializar almacenamiento adicional y devolver valores. La recursividad es más ineficiente en términos de tiempo y uso de memoria, ya que para cada llamada al método hay que efectuar una serie de operaciones en la pila.
- Dificultad para depurar: Las funciones recursivas pueden ser más difíciles de depurar y entender, especialmente cuando se utilizan incorrectamente o en casos donde la recursión no termina adecuadamente.
- Posibilidad de entrar en bucles infinitos: Si no se gestiona correctamente, la recursividad puede llevar a bucles infinitos si no se alcanza un caso base, lo que puede resultar en un bloqueo del programa.
A pesar de ello, en el mundo laboral no se utiliza demasiado la recursividad, debido a que un error puede ser trágico en la memoria, así como tener una lista con millones de datos, puede hacer que se utilice mucha memoria. Es importante considerar cuidadosamente los requisitos y características del problema antes de decidir si se utiliza la recursividad o enfoques alternativos.
Ejemplos Prácticos de Recursividad
Factorial de un Número
Un ejemplo clásico para entender la recursividad es calcular el factorial de un número. En matemáticas se expresa con n! donde n es el último número a comprobar. El factorial de n es n multiplicado por el factorial de n-1. Por ejemplo, la función factorial se define como el producto de todos los enteros positivos menores o iguales a sus argumentos.
Consideremos el siguiente código para calcular el factorial de un número:
const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}factorial(5)La primera condición dice: “si el parámetro pasado es igual a 0 o 1, vamos a salir y regresar 1”. Si llamamos factorial(0), la función regresa 1 y nunca toca el caso recursivo. Lo mismo aplica para factorial(1). Siguiente, el caso recursivo establece: “Si el parámetro no es 0 o 1, entonces pasaremos el valor de num multiplicado por el valor de retorno de llamar esta función otra vez con num-1 como su argumento”.
Podemos ver lo que está pasando si insertamos un enunciado de depuración en el código y usamos las herramientas de desarrollador para pasar a través de él y mirar la pila de llamadas:
Lea también: ¿Cómo localizar tus XML del SAT?
- La pila de ejecución coloca factorial() con 5 como argumento pasado. El caso base es falso, entra en la condición recursiva.
- La pila de ejecución coloca factorial() por segunda vez con num-1 = 4 como argumento. El caso base es falso, entra en la condición recursiva.
- La pila de ejecución coloca factorial() por tercera ocasión con num-1 (4-1) = 3 como argumento. El caso base es falso, entra en la condición recursiva.
- La pila de ejecución coloca factorial() por cuarta ocasión con num-1 (3-1) = 2 como argumento. El caso base es falso, entra en la condición recursiva.
- La pila de ejecución coloca factorial() por quinta ocasión con num-1 (2-1) = 1 como argumento. Ahora el caso base es verdad, entonces regresa 1.
- A partir de aquí se completa el último contexto de ejecución, num === 1, entonces esa función regresa 1.
- Siguiente num === 2, entonces el valor de retorno es 2. (1×2).
- Siguiente num === 3, entonces el valor de retorno es 6, (2×3). Hasta ahora tenemos 1×2×3.
- Siguiente, num === 4, (4×6). 24 es el valor de retorno al siguiente contexto.
- Finalmente, num === 5, (5×24) y tenemos 120 como el valor final.
La figura muestra cómo la sucesión de llamadas recursivas continúa hasta que 1! se evalúa al valor 1, lo que termina la recursión. La función recursiva factorial primero prueba para ver si una condición de terminación es verdadera, es decir, si el número es menor o igual a 1.
A continuación, una implementación en Java para el factorial:
public class Recursividad { public static int factorialRecursive(int n) { if (n == 0) { return 1; } return n * factorialRecursive(n - 1); }}Secuencia de Fibonacci
El cálculo del término n de la secuencia de Fibonacci también puede abordarse recursivamente:
const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);Y su implementación recursiva en Java:
public class Recursividad { public static int fibonacciRecursive(int n) { if (n <= 1) { return n; } return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); }}Otros Ejemplos de Recursividad
La recursividad es una técnica poderosa en programación que nos permite resolver una variedad de problemas de manera elegante y eficiente. Hemos explorado varios ejemplos prácticos de cómo usar la recursividad para realizar una cuenta regresiva, calcular factoriales y generar la secuencia de Fibonacci.
Cuenta Regresiva
Un ejemplo sencillo es la cuenta regresiva:
public class Recursividad { public static void countDownRecursive(int n) { if (n < 0) { System.out.println("Terminó la cuenta regresiva"); return; } System.out.println("Cuenta " + n); countDownRecursive(--n); }}En este ejemplo, countDownRecursive logra la cuenta regresiva utilizando recursividad.
Operaciones con Arrays
Se pueden implementar funciones para manipular arrays recursivamente, como "aplanar" un array anidado:
function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}flatten([1, [2], [3, [[4]]]]);Invertir una Cadena
La recursividad puede ser utilizada para invertir el orden de los caracteres en una cadena:
function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}reverse('abcdefg');Ordenamiento Rápido (Quicksort)
Los algoritmos recursivos pueden emplearse para tareas de ordenación y búsqueda. Por ejemplo, el algoritmo quicksort utiliza la recursividad para dividir una matriz en submatrices más pequeñas y ordenarlas de forma independiente. “Divide y vencerás” se utiliza con mayor frecuencia para recorrer o buscar estructuras de datos como árboles de búsqueda binaria, gráficos, y montículos. También funciona para muchos algoritmos de clasificación, como ordenamiento rápido y ordenamiento por montículos. La recursividad es un componente esencial en el desarrollo de algoritmos eficientes de divide y vencerás. El divide y vencerás consiste en dividir un problema en subproblemas más pequeños, resolverlos de forma independiente y combinar sus soluciones para obtener el resultado final. La recursividad permite la descomposición natural del problema en subproblemas y su posterior resolución. Aplicando la recursividad a los algoritmos de divide y vencerás, los problemas complejos pueden resolverse eficazmente con una menor complejidad temporal, lo que los hace adecuados para tareas computacionales a gran escala.
function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1 if (lo < hi) { var p = partition(arr, lo, hi) console.log('partition from, ' + lo + ' to ' + hi + '=> partition: ' + p) quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } if (hi - lo === arr.length - 1) return arr}function partition(arr, lo, hi) { var pivot = arr[hi] var pivotLocation = lo for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}quickSort([1, 4, 3, 56, 9, 8, 7, 5])Búsqueda Binaria
Del mismo modo, el algoritmo de búsqueda binaria aplica la recursividad para buscar eficientemente un valor objetivo en una matriz ordenada dividiendo la matriz por la mitad en cada paso. Si partimos de que los elementos del vector están almacenados en orden ascendente, el proceso de búsqueda binaria puede describirse así: se selecciona un elemento del centro o aproximadamente del centro del vector. Si el valor a buscar no coincide con el elemento seleccionado y es mayor a él, se continúa la búsqueda en la segunda mitad de la matriz. Si por el contrario, el valor a buscar es menor que el valor del elemento seleccionado, la búsqueda continúa en la primera mitad de la matriz.
Aplicaciones de la Recursividad en el Mundo Real
La recursividad es frecuente en diversas aplicaciones tecnológicas del mundo real. Entender la recursividad es crucial cuando se aprenden estructuras de datos y algoritmos porque muchos conceptos y algoritmos fundamentales se basan en técnicas recursivas. Sin una sólida comprensión de la recursividad, resulta difícil comprender y aplicar eficazmente estos conceptos.
Estructuras de Datos y Algoritmos
La recursión se utiliza a menudo para recorrer estructuras de datos como árboles o listas enlazadas. En estos casos, una función recursiva puede visitar cada nodo o elemento llamándose a sí misma en los nodos hijos o en el siguiente elemento de la lista. Al aplicar repetidamente la misma función recursiva, se puede recorrer eficazmente toda la estructura. Los árboles, grafos y otras estructuras de datos a menudo presentan propiedades recursivas, y algoritmos como la búsqueda en profundidad, el backtracking y el divide y vencerás se basan en la recursividad para resolver problemas complejos de forma eficiente. Para estructuras de datos anidadas como árboles, gráficos y montículos, la recursividad es invaluable.
La recursividad se utiliza habitualmente en algoritmos de backtracking, que exploran sistemáticamente todas las soluciones posibles a un problema construyendo una solución de forma incremental y deshaciendo las elecciones que conducen a callejones sin salida. En estos algoritmos, una función recursiva explora cada posible elección y se llama a sí misma para explorar las siguientes. Si una elección conduce a una solución no válida, la función retrocede e intenta una elección diferente. La recursividad permite una aplicación intuitiva y concisa del backtracking, lo que posibilita la exploración eficaz de grandes espacios de soluciones.
Inteligencia Artificial y Aprendizaje Automático
La recursividad desempeña un papel importante en varios aspectos de la inteligencia artificial y el aprendizaje automático. Por ejemplo, en el procesamiento del lenguaje natural, las redes neuronales recursivas (RNN) pueden procesar frases aplicando recursivamente operaciones a las palabras y sus estructuras gramaticales. Los algoritmos recursivos también se utilizan en la construcción de árboles de decisión, donde los nodos dividen recursivamente los datos en función de distintos atributos para tomar decisiones. Comprender la recursividad es valioso para diseñar y aplicar sistemas inteligentes.
Protocolos de Red y Algoritmos de Encaminamiento
La recursividad puede encontrarse en protocolos de red y algoritmos de encaminamiento, especialmente en protocolos que emplean estructuras jerárquicas o distribuidas. Por ejemplo, el protocolo de pasarela fronteriza (BGP) utiliza un mecanismo de enrutamiento recursivo llamado reflexión de ruta, en el que los enrutadores propagan la información de enrutamiento recursivamente a través de la jerarquía de la red. Del mismo modo, en el sistema de nombres de dominio (DNS), las consultas recursivas se utilizan para resolver nombres de dominio contactando iterativamente con servidores DNS autorizados hasta obtener una respuesta final.
Fractales y la Infografía
La recursividad está estrechamente relacionada con los fractales y la infografía. Los fractales son patrones geométricos complejos que muestran autosimilitud a diferentes escalas. Los algoritmos recursivos se utilizan para generar fractales aplicando repetidamente una función matemática o una transformación a subconjuntos más pequeños del patrón. Los sistemas gráficos por ordenador emplean técnicas recursivas, como el trazado de rayos o la subdivisión recursiva, para generar imágenes detalladas y realistas mediante la evaluación recursiva de las interacciones de la luz o la subdivisión de superficies.
Optimización y Consideraciones al Usar Recursividad
La recursividad de cola es una técnica en la que la llamada recursiva es la última operación de una función. Permite al compilador o al intérprete optimizar la función recursiva reutilizando el mismo marco de pila para cada llamada recursiva, eliminando la necesidad de espacio de pila adicional. Esta optimización se denomina optimización de llamada de cola. Puede mejorar la eficiencia de las funciones recursivas y evitar errores de desbordamiento de pila.
La optimización de la recursividad de cola debe aplicarse en funciones recursivas cuando la llamada recursiva es la última operación realizada en la función. Al asegurarse de que la llamada recursiva está en posición de cola, los compiladores e intérpretes pueden optimizar la función para reutilizar el mismo marco de pila, reduciendo los requisitos de memoria. Esta optimización es especialmente útil para funciones recursivas con muchas iteraciones, ya que evita errores de desbordamiento de pila y mejora el rendimiento.
La recursividad puede no ser recomendable en programación y diseño de algoritmos cuando conduce a soluciones ineficientes o impone una sobrecarga de memoria significativa. Si un problema no posee una estructura recursiva o puede resolverse más eficientemente utilizando técnicas iterativas, la recursividad puede no ser la elección óptima. Sin embargo, hay problemas que por su naturaleza recursiva son mucho más fáciles de resolver con recursividad que con intrincados bucles. Por lo tanto, si la eficiencia no es un problema y el problema a resolver tiene una naturaleza recursiva, mejor recursividad ya que se produce un programa más fácil de entender y de depurar.
Practicar técnicas de recursividad es importante.