¿Qué es la recursividad en programación o desarrollo de software?
Si alguna vez has visto una muñeca rusa, has experimentado un ejemplo visual de recursión: un objeto que contiene versiones más pequeñas de sí mismo. En programación, la recursión es una técnica poderosa que permite que una función se llame a sí misma para resolver problemas complejos de manera simple.
La programación recursiva es una técnica algorítmica de la ingeniería del software para la resolución de problemas. Esta técnica esta pensada para resolver problemas en los que el orden de complejidad depende del tamaño del problema. Esta especialmente orientada al desarrollo de funciones en los que los tiempos de computación son elevados.
Ejemplos:
- Búsqueda de un elemento en una lista. Utilizar recursión para buscar un elemento en una lista linealmente no es eficiente y ocupa más espacio en la memoria. Una búsqueda iterativa con un bucle es mucho más directa y rápida.
- Cálculo del factorial de un número. Este problema, por su propia definición matemática, tiene una definición matemática recursiva natural, por lo que su implementación recursiva es directa y mucho más eficiente.
La programación recursiva se basa en una técnica en la que una función se llama a sí misma para resolver un problema. En lugar de abordar el problema completo de una sola vez, la función divide el problema en subproblemas más pequeños y maneja cada uno de ellos recursivamente. Este proceso continúa hasta que se alcanza un caso base o condición de finalización, que detiene las llamadas recursivas y evita que se repita indefinidamente.
En cada llamada recursiva, la función trabaja sobre una versión simplificada o reducida del problema original. Al resolver ese subproblema más pequeño, el programa va acumulando soluciones parciales que, al final, se combinan para resolver el problema en su totalidad. De este modo, la recursión permite descomponer problemas complejos en pasos más sencillos, que la función puede resolver paso a paso de forma automática.
Es importante que cada algoritmo recursivo defina claramente su condición base, ya que sin ella, la función seguiría llamándose a sí misma indefinidamente, lo que provocaría un error de desbordamiento de pila o stack overflow. Por lo tanto, la recursión es una técnica muy poderosa, pero requiere cuidado en su implementación para ser eficiente.
Programación recursiva VS programación iterativa
- En la programación recursiva, una función se llama a sí misma, directa o indirectamente, para resolver un problema. Se descompone un problema en subproblemas más pequeños, resolviendo cada uno hasta llegar a un caso base.
- En la programación iterativa se usan estructuras de control, como bucles (for, while) para repetir una secuencia de instrucciones un número definido de veces o hasta que se cumpla una condición.
Utilizar técnicas de programación iterativa o recursiva dependerá de la naturaleza y complejidad del problema, y sobre todo, del tiempo necesario para resolverse, es decir, su orden de complejidad.
En general, la programación iterativa es más intuitiva y sencilla de ejecutar, es la que se utiliza normalmente por defecto y con la que los programadores suelen tener más afinidad.
Como norma casi general, se utiliza la programación recursiva cuando el tiempo de ejecución crece exponencialmente con el tamaño del problema, en vez de linealmente, ya que para un problema muy grande la función podría tardar demasiado tiempo en terminar o irse al infinito. También se utiliza cuando el tiempo de ejecución para resolver un problema de forma recursiva es muy inferior a la versión iterativa o cuando su consumo de recursos, como la memoria RAM, es más bajo.
Como hemos visto hasta ahora la recursión es una herramienta poderosa para resolver problemas complejos, sin embargo, en algunos casos, puede generar tiempos de ejecución exponenciales si no se usa de manera eficiente. El uso de técnicas como la memoización puede optimizar la recursión para evitar comportamientos innecesariamente lentos.
El orden de complejidad
El concepto de orden de complejidad es una medida que describe el comportamiento del tiempo o el espacio que un algoritmo necesita para ejecutarse en función del tamaño de su entrada. Se utiliza para analizar y comparar la eficiencia de diferentes algoritmos, lo cual es fundamental cuando se trata de problemas que involucran grandes cantidades de datos. Se diferencian 2 tipos de complejidad, la temporal y la espacial.
- Complejidad temporal: Se refiere al tiempo que tarda un algoritmo en ejecutarse a medida que aumenta el tamaño del problema.
- Complejidad espacial: Se refiere a la cantidad de memoria que un algoritmo requiere a medida que aumenta el tamaño del problema.
Para expresar la complejidad, se utiliza la notación Big O (O(n)), que proporciona una manera de representar el comportamiento asintótico de un algoritmo, es decir, cómo se comporta cuando el tamaño del problema tiende a ser grande. La notación Big O describe el peor escenario posible para el tiempo o espacio que requiere un algoritmo, en función de una entrada de tamaño n.
Ejemplos de órdenes de complejidad comunes
Ordenados de mayor a menor eficiencia:
O(1) - Tiempo constante
- El tiempo de ejecución no depende del tamaño de la entrada.
- Ejemplo: Acceder a un elemento en una lista o array por su índice.
- No importa si la lista tiene 10 o 1 millón de elementos, el acceso es inmediato.
O(log n) - Tiempo logarítmico:
- El tiempo de ejecución aumenta logarítmicamente a medida que crece el tamaño de la entrada. Este tipo de complejidad es típico de algoritmos que dividen el problema en mitades en cada paso.
- Ejemplo: Búsqueda binaria.
- Aquí, en cada paso reducimos a la mitad el tamaño de la lista, por lo que el número de operaciones crece logarítmicamente con respecto al tamaño de la lista.
O(n) - Tiempo lineal:
- El tiempo de ejecución aumenta proporcionalmente al tamaño de la entrada.
- Ejemplo: Recorrer una lista para encontrar un elemento.
- Aquí, si hay 1,000 elementos, tendremos que verificar los 1,000; si hay 1 millón, el tiempo aumenta proporcionalmente.
O(n log n) - Tiempo casi lineal:
- Este tipo de complejidad ocurre comúnmente en algoritmos de ordenación eficientes, como Merge Sort o Quick Sort.
- Ejemplo: Algoritmo de ordenación eficiente.
- En este caso, la lista se divide repetidamente en partes más pequeñas (log n divisiones), y cada división implica recorrer toda la lista (n).
O(n²) - Tiempo cuadrático:
- El tiempo de ejecución crece proporcionalmente al cuadrado del tamaño de la entrada. Esto es típico de algoritmos que requieren comparaciones o iteraciones anidadas.
- Ejemplo: Algoritmo de ordenación por selección o burbuja.
- Si la lista tiene 1,000 elementos, el algoritmo hace 1,000² operaciones (1 millón de comparaciones).
O(2^n) - Tiempo exponencial:
- El tiempo de ejecución se duplica con cada incremento en el tamaño de la entrada. Los algoritmos con esta complejidad se vuelven ineficientes muy rápidamente.
- Ejemplo: Cálculo de la serie de Fibonacci sin optimización.
O(n!) - Tiempo factorial:
- El tiempo de ejecución crece factorialmente con el tamaño de la entrada. Es extremadamente ineficiente y ocurre en problemas de combinatoria.
- Ejemplo: Algoritmo que genera todas las permutaciones posibles de un conjunto.
¿Por qué es importante entender el orden de complejidad?
El orden de complejidad te ayuda a predecir cómo se comportará tu algoritmo cuando se aplique a conjuntos de datos grandes. Un algoritmo con una complejidad de O(n) o O(log n) puede ejecutarse eficientemente incluso en millones de datos, mientras que uno con complejidad O(n²) o peor puede volverse inútil con entradas grandes.
Por ejemplo, si tienes una lista de 10 millones de elementos, un algoritmo O(n) como la búsqueda lineal puede ser manejable, pero un algoritmo O(n²) puede tardar muchísimo tiempo en completarse. Elegir el algoritmo adecuado es crucial para mantener un rendimiento aceptable.
Tipos de algoritmos recursivos
Los tipos de recursión se distinguen por la forma en que se dividen los problemas y el número de llamadas recursivas que se realizan. Elegir el tipo correcto de recursión para un problema específico es clave para mejorar la eficiencia y el rendimiento del algoritmo. La optimización de memoria y el tiempo de ejecución son factores importantes a tener en cuenta al decidir cuál es el mejor enfoque recursivo para resolver un problema determinado.
1. Recursión de cola (Tail recursion)
En la recursión de cola, la llamada recursiva es la última operación que realiza la función antes de devolver el resultado. Esto significa que no hay operaciones pendientes después de la llamada recursiva. Este tipo de recursión es eficiente en términos de uso de memoria, ya que no requiere almacenar múltiples llamadas en la pila de ejecución. Algunos lenguajes de programación optimizan este tipo de recursión para evitar un consumo excesivo de memoria.
- Ventaja: Permite optimización de memoria en lenguajes que soportan la optimización de recursión de cola.
- Desventaja: No siempre es fácil convertir un algoritmo en recursión de cola.
2. Recursión sin cola (Non-tail Recursion)
En la recursión no de cola, la llamada recursiva no es la última instrucción que se ejecuta. Después de la llamada recursiva, quedan operaciones pendientes que se deben realizar, como multiplicaciones o sumas. Este tipo de recursión requiere más memoria, ya que el sistema necesita almacenar el estado de cada llamada recursiva hasta que todas las llamadas se completen.
- Ventaja: Es más flexible y se puede aplicar en una amplia variedad de problemas.
- Desventaja: Consume más memoria, ya que debe almacenar información en la pila para cada llamada recursiva.
3. Recursión binaria o árbol recursivo (Binary Recursion)
En la recursión binaria, una función realiza más de una llamada recursiva en cada paso. Esto genera una estructura de árbol, donde cada nodo da lugar a dos (o más) subproblemas. Este tipo de recursión es común en problemas como el cálculo de la serie de Fibonacci o en el recorrido de estructuras de datos jerárquicas, como los árboles.
- Ventaja: Se adapta bien a problemas que naturalmente se dividen en dos subproblemas.
- Desventaja: Genera muchas llamadas recursivas, lo que puede aumentar el tiempo de ejecución si no se optimiza.
4. Recursión múltiple (Multiple Recursion)
La recursión múltiple es una generalización de la recursión binaria, donde una función realiza más de dos llamadas recursivas. Este tipo de recursión se aplica en problemas donde se requieren múltiples subproblemas para resolver el problema original, como en la generación de todas las permutaciones de un conjunto de elementos.
- Ventaja: Útil para problemas que requieren explorar múltiples soluciones o subproblemas simultáneamente.
- Desventaja: La complejidad y el número de llamadas recursivas pueden crecer exponencialmente, lo que puede hacer que el algoritmo sea ineficiente.
5. Recursión anidada (Nested recursion)
En la recursión anidada, una llamada recursiva se realiza dentro de otra llamada recursiva. Esto significa que el resultado de una llamada recursiva es necesario para calcular la siguiente llamada. Este tipo de recursión puede ser más complejo de entender y depurar.
- Ventaja: Útil en problemas donde los resultados intermedios de una llamada recursiva se utilizan inmediatamente en la siguiente.
- Desventaja: Es más difícil de seguir y puede ser confuso, ya que hay múltiples capas de llamadas recursivas.
6. Recursión divide y vencerás (Divide and conquer recursion)
En la recursión de dividir y vencerás, el problema grande se divide en varios subproblemas más pequeños, que se resuelven de manera recursiva. Posteriormente, las soluciones de estos subproblemas se combinan para formar la solución del problema original. Este enfoque se utiliza en algoritmos como la ordenación de listas (Merge Sort) y la búsqueda binaria.
- Ventaja: Es muy eficiente cuando el problema se puede dividir en partes más pequeñas de forma equilibrada.
- Desventaja: Si el problema no se puede dividir de manera eficiente, la recursión puede volverse ineficiente.
7. Recursión Mutua (Mutual Recursion)
En la recursión mutua, dos o más funciones se llaman mutuamente, formando un ciclo de llamadas recursivas entre ellas. Esto se utiliza cuando el problema requiere que varias funciones se llamen entre sí para resolver subproblemas dependientes.
- Ventaja: Útil en casos donde el flujo del programa depende de varios procesos interconectados.
- Desventaja: Es difícil de seguir y depurar, ya que puede ser complicado entender el flujo de control entre las funciones que se llaman mutuamente.
El principio de inducción
La relación entre la recursión y el principio de inducción es fundamental, ya que ambos se basan en la idea de resolver un problema dividiéndolo en subproblemas más pequeños, y ambos dependen de un “caso base” que garantiza que el proceso termine. Es una práctica habitual cuando se diseña una solución recursiva, la de validar si cumple el principio de inducción para determinar si el planteamiento es correcto o no.
Veamos la relación entre ambos conceptos a partir de las definiciones de ambos:
¿Qué es la inducción matemática?
La inducción matemática o principio de inducción es un método de prueba utilizado para demostrar que una proposición es verdadera para todos los números naturales (o enteros no negativos). El principio de inducción se basa en dos pasos fundamentales:
- Caso base: Se demuestra que la proposición es verdadera para un valor inicial, generalmente n = 0 o n = 1
- Paso inductivo: Se asume que la proposición es verdadera para un número arbitrario n (hipótesis inductiva), y luego se demuestra que, bajo esa suposición, también es verdadera para n + 1
Esto garantiza que, si la proposición es verdadera para el caso base y el paso inductivo es correcto, la proposición es verdadera para todos los números naturales.
¿Qué es la recursión?
Como hemos visto en este artículo ya, la recursión es una técnica en programación y matemáticas donde una función o algoritmo se llama a sí mismo para resolver subproblemas más pequeños del problema original. Al igual que en la inducción, la recursión tiene dos componentes principales:
- Caso base: Una condición que detiene las llamadas recursivas y devuelve un resultado directo (es decir, la solución más sencilla del problema).
- Caso recursivo: La función se llama a sí misma con un subconjunto más pequeño del problema original, y usa los resultados de estas llamadas recursivas para construir la solución final.
Relación entre recursión e inducción
La conexión clave entre recursión e inducción es que ambos siguen una estructura similar en su resolución de problemas. De hecho, se puede demostrar que un algoritmo recursivo es correcto utilizando la inducción matemática. Veamos cómo:
Paso 1: Caso base
En la recursión, el caso base define cuándo el algoritmo deja de llamar a sí mismo y resuelve el problema directamente. Este es el equivalente del caso base en la inducción matemática, donde se verifica que la proposición es verdadera para un valor inicial, como n = 0
Paso 2: Paso recursivo y paso inductivo
En el caso recursivo, la función se llama a sí misma con una versión más pequeña del problema, hasta que finalmente alcanza el caso base. Este proceso es similar al paso inductivo en la inducción matemática, donde asumimos que la proposición es verdadera para un número arbitrario n, y luego demostramos que también es verdadera para n + 1
En un algoritmo recursivo, se asume que la función resuelve correctamente el subproblema (hipótesis inductiva), y con esta suposición, construimos la solución del problema más grande (equivalente al paso inductivo en la inducción).
Ejemplo 1: Factorial
El cálculo del factorial de un número n es un ejemplo clásico de recursión y se puede demostrar usando inducción matemática.
1. Definición Recursiva del factorial:
n! =
\begin{cases}
1 & \text{si } n = 0 \\
n \times (n - 1)! & \text{si } n > 0
\end{cases}
2. Prueba por inducción:
- Caso base: Para n = 0 , tenemos 0! = 1 , lo cual es cierto por definición.
- Paso inductivo: Supongamos que n! es verdadero para un número n = k (hipótesis inductiva), es decir, k! = k x (k - 1)!
Ahora necesitamos demostrar que también es cierto para n = k + 1 usando la definición recursiva del factorial:
(k + 1)! = (k + 1) x k!
Por la hipótesis inductiva, sabemos que k! = k x (k - 1)! , por lo que:
(k + 1)! = (k + 1) x k!
Esto completa el paso inductivo, demostrando que la definición recursiva del factorial es correcta para todos los n .
En este ejemplo, la recursión del factorial sigue exactamente la misma estructura que una prueba por inducción matemática: el caso base asegura que el proceso se detiene, y el paso recursivo (inductivo) asegura que podemos construir soluciones más grandes a partir de las más pequeñas.
Ejemplo 2: Serie de Fibonacci
El cálculo de la serie de Fibonacci también sigue esta misma relación entre recursión e inducción:
1. Definición recursiva de Fibonacci:
F(n) =
\begin{cases}
0 & \text{si } n = 0 \\
1 & \text{si } n = 1 \\
F(n - 1) + F(n - 2) & \text{si } n > 1
\end{cases}
2. Prueba por inducción:
- Caso base: Para n = 0 y n = 1 , F(0) = 0 y F(1) = 1 , lo cual es cierto por definición.
- Paso inductivo: Supongamos que F(n) es correcto para n = k y n = k - 1 . Necesitamos demostrar que también es correcto para n = k + 1 .
- Usando la definición recursiva de Fibonacci:
F(k + 1) = F(k) + F(k - 1)
Sabemos, por la hipótesis inductiva, que F(k) y F(k - 1) son correctos, por lo que F(k + 1) también es correcto.
Este es otro ejemplo donde la recursión sigue un principio inductivo.
Ejemplos de problemas complejos que resuelve la recursión
1. Divide y vencerás
Un ejemplo clásico de divide y vencerás es el algoritmo Merge Sort, que se utiliza para ordenar listas.
Pasos de Merge Sort:
1. Dividir: Si la lista tiene más de un elemento, se divide en dos mitades.
2. Resolver: Se aplica recursivamente el mismo proceso a cada mitad hasta que cada sublista tenga un solo elemento (ya ordenado).
3. Combinar: Se combinan las sublistas ordenadas para formar una única lista ordenada.
Ejemplo:
Para la lista [38, 27, 43, 3, 9, 82, 10]:
1. Dividir: Se divide en [38, 27, 43] y [3, 9, 82, 10], y luego en listas más pequeñas hasta llegar a listas de un solo elemento.
2. Resolver: Las listas de un elemento ya están ordenadas.
3. Combinar: Las sublistas ordenadas se combinan en orden hasta obtener [3, 9, 10, 27, 38, 43, 82].
La complejidad de Merge Sort es O(n log n), ya que se divide logarítmicamente y se combina en tiempo lineal.
2. Problemas de optimización
Un ejemplo clásico de un problema de optimización es el problema de la mochila (Knapsack Problem), donde el objetivo es maximizar el valor total de los objetos que se pueden incluir en una mochila, sin exceder su capacidad de peso.
Descripción del problema:
Dado un conjunto de objetos, cada uno con un peso y un valor, el problema consiste en determinar la combinación de objetos que maximiza el valor total en una mochila con una capacidad de peso limitada.
- Entrada:
- Una capacidad de la mochila, W (el peso máximo que puede llevar).
- Una lista de objetos, cada uno con:
- Un peso, wi.
- Un valor, vi.
- Objetivo: Maximizar el valor total de los objetos seleccionados sin superar la capacidad de la mochila.
Tipos de problema de la mochila:
- Mochila 0/1: Para cada objeto, puedes incluirlo completamente en la mochila o no incluirlo. No puedes fraccionar los objetos.
- Mochila fraccionaria: Se permite fraccionar los objetos, es decir, puedes tomar una parte de un objeto.
Ejemplo:
Supongamos que tienes una mochila con una capacidad de 15 kg y los siguientes objetos:
- Objeto 1: Peso = 10 kg, Valor = 60.
- Objeto 2: Peso = 5 kg, Valor = 40.
- Objeto 3: Peso = 3 kg, Valor = 30.
Pregunta: ¿Qué objetos debes incluir en la mochila para maximizar el valor total, sin exceder el límite de 15 kg?
Solución 0/1 (sin fraccionar):
Si seleccionas los objetos 1 y 2, el peso total será 15 kg y el valor será 60 + 40 = 100 , lo cual es la solución óptima para este caso.
Métodos para resolver el Problema de la Mochila:
- Algoritmos de Programación Dinámica (para el caso 0/1): Es un enfoque eficiente para resolver este problema de manera exacta, utilizando una tabla que almacena los resultados de subproblemas.
- Algoritmos Greedy (para el caso fraccionario): Selecciona los objetos en función del valor por unidad de peso, lo que es óptimo cuando se permite fraccionar los objetos.
Importancia:
Este problema es fundamental en optimización combinatoria, y sus aplicaciones incluyen asignación de recursos, planificación financiera y otras áreas donde se busca maximizar beneficios sujetos a restricciones.
Y hasta aquí la introducción a la programación recursiva.
Esperamos que te haya gustado y que no te olvides de seguirnos en LinkedIN que es dónde anunciamos cada artículo nuevo, y en el resto de redes sociales donde comenzaremos a subir contenidos sobre ciencia pero diferentes.
https://www.linkedin.com/company/the-science-driven-company/
https://www.instagram.com/science.driven/