La recursión o recursividad es el comportamiento de una función que se llama a sí misma. Estas funciones se llaman recursivas. A diferencia de un bucle, no simplemente se repiten varias veces, sino que funcionan «dentro» de la una a la otra.

Un chiste famoso dice: «Para entender la recursividad hay que entender la recursividad«.

La recursión se considera uno de los conceptos principales en informática. Es un método para resolver problemas, similar a la inducción matemática: para que una función se ejecute, primero se debe obtener su resultado al llamarla con un valor diferente.

Funciona así: la función A de la unidad inicia la función A de dos, esta de tres, y así sucesivamente, hasta que se calcule el valor necesario. Para que la llamada recursiva termine, se debe escribir inmediatamente en la función A una condición de salida de la recursión: por ejemplo, si se obtiene algún valor, no se debe ejecutar la función de nuevo, sino devolver algún resultado.

Si no se escribe una condición de salida, la recursión será infinita. Mientras no se alcance la condición de salida, todas las instancias de la función A trabajarán simultáneamente: una se introduce en la otra.

✔️
Prácticamente todos los lenguajes de programación modernos admiten llamadas recursivas.

¿Quién usa la recursión y para qué sirve?

Los programadores necesitan la recursión de vez en cuando para resolver diferentes problemas. Hay tareas que son más fáciles e intuitivamente más claras de resolver con su ayuda, y hay otras para las que existen algoritmos más óptimos.

Por lo general, la recursión se utiliza en cálculos que implican el uso del resultado de un paso para calcular otro. Por ejemplo, el cálculo de un fractal y su dibujo. A menudo, estas tareas se pueden resolver sin recursión, pero su uso hace que el código sea más simple, más corto y más rápido que las alternativas. Sin embargo, la recursión puede sobrecargar demasiado el ordenador, por lo que estas soluciones no siempre se utilizan.

La recursión también se puede encontrar en otras áreas: física, biología, lingüística e incluso arquitectura. Por ejemplo, las formas fractales como una hoja de helecho o un copo de nieve son recursivas. Las oraciones subordinadas también lo son. Y la forma más clara de recursión son dos espejos colocados uno frente al otro.

Los programadores también usan la recursión por diversión. Por ejemplo, la conocida abreviatura GNU se expande como GNU is Not Unix: la primera letra esconde la misma abreviatura. Esto también es recursión.

Diferencias entre la recursión y el bucle

A nivel intuitivo, una llamada recursiva se puede confundir fácilmente con un bucle. Ambos conceptos implican que la función se ejecuta varias veces. Pero hay una diferencia fundamental:

  • En un bucle, no se llaman nuevas funciones dentro de las llamadas anteriormente;
  • La recursión es una función que se llama a sí misma con diferentes argumentos.

En pocas palabras: la instrucción con el punto «Vuelve al punto 1» es un bucle, la instrucción con el punto «Vuelve a leer la instrucción» es recursión.

Sin embargo, los bucles a menudo reemplazan la recursión, por ejemplo, en situaciones donde los algoritmos recursivos resultan demasiado exigentes en cuanto a recursos. Sin embargo, para usar bucles como reemplazo de la recursión, se necesitarán trucos adicionales.

Interrupción de la recursión

Si a una función recursiva no se le dan condiciones para salir, funcionará infinitamente hasta que una gran cantidad de sus instancias «consuman» toda la memoria operativa del dispositivo y sobrecarguen la pila de llamadas. Por lo tanto, el desarrollador debe proporcionar formas de salir del proceso recursivo.

Por lo general, la salida es alguna condición que se verifica al comienzo de la ejecución de la función. Si se cumple, la función se llamará a sí misma de nuevo; de lo contrario, devolverá algún valor, lo devolverá a su «vecino» anterior y se cerrará.

Por ejemplo, si n > 1, entonces llama a A(n-1). De lo contrario, devuelve 1. Resulta que cuando n se vuelve menor o igual a uno, A no se iniciará de nuevo: la instancia actual simplemente devolverá uno. Las demás instancias recibirán el resultado que necesitan y también se cerrarán en cascada. Este proceso se llama retroceso de la recursión. Y lo que fue antes de eso es el avance directo.

La cantidad de funciones abiertas al final se llama profundidad de la recursión.

Ejemplo de recursión: cálculo de los números de Fibonacci

Un ejemplo conocido de cálculos recursivos son los números de Fibonacci. Cada número siguiente en la secuencia es la suma de los dos anteriores, comenzando por 1.

Resulta así: 1, 1, 2, 3, 5, 8, 13, 21 y así sucesivamente. El uso de la recursión aquí es una forma de cálculo obvia e intuitiva:

  • Supongamos que la función se llama fibonacci(n) y calcula el n-ésimo número de Fibonacci;
  • En el primer paso, la función llama a fibonacci(n-1) y fibonacci(n-2), es decir, a sí misma, pero con diferentes argumentos, y suma los resultados obtenidos;
  • Las nuevas llamadas harán lo mismo hasta que n llegue a uno o cero: este es el primer número de Fibonacci, y en este caso la función devolverá 1;
  • La instancia anterior de la función recibirá dos resultados 1, de uno y cero, los sumará y los enviará «atrás» a los vecinos anteriores;
  • Al final, todas las funciones llamadas recibirán la respuesta de sus «descendientes», sumarán los valores recibidos y los devolverán a la primera función fibonacci(n);
  • Esta sumará los valores finales, devolverá el resultado y se cerrará.

Este es solo un ejemplo simple; hay muchos más algoritmos recursivos. Otro conocido es el cálculo del factorial de un número.

Otros ejemplos de cálculos recursivos

  • Cálculo del factorial de un número: multiplicaciones sucesivas por el número anterior. Por ejemplo, 3! (factorial de tres) es 1 * 2 * 3.
  • Cálculo e imagen de fractales: construcciones donde los elementos más pequeños repiten los más grandes. Ejemplos claros de fractales son un copo de nieve y una hoja de helecho.
  • Recorrido de estructuras de datos ramificadas, como gráficos y árboles.
  • Análisis informático del lenguaje natural, frases y oraciones.
  • Búsqueda de un camino en un laberinto y construcción de rutas: por ejemplo, algoritmos DFS y BFS.
  • Cálculos con series numéricas, como los mismos números de Fibonacci o la búsqueda de números primos.
  • Operaciones matemáticas que requieren acciones repetidas con diferentes valores, como la potenciación mayor que 2, la búsqueda del máximo o mínimo.
  • Operaciones con sistemas numéricos, como la conversión de números de uno a otro.
  • Fuera de las matemáticas y la informática, se pueden recordar muchos otros ejemplos de recursión: desde la autoexcitación de los circuitos electrónicos hasta los cuentos de «Las mil y una noches».

Recursión directa e indirecta

La recursión se puede dividir condicionalmente en directa e indirecta.

  • La directa se llama a sí misma directamente. Es decir, la función A llama a la función A con otros argumentos.
  • La indirecta actúa a través de una «tercera» función. La función A llama a la función B, y esta, a su vez, vuelve a llamar a la función A. Esto también es recursión, simplemente menos obvio.

También existen recursiones lineales y en cascada. En la lineal, una instancia de la función se llama a sí misma solo una vez, en la en cascada, varias veces. Por ejemplo, el cálculo de los números de Fibonacci es una recursión en cascada, porque la función se llama a sí misma dos veces: para n-1 y n-2.

Procesos recursivos e iterativos

Una misma recursión se puede utilizar de diferentes maneras. Por ejemplo, existen los conceptos de proceso recursivo e iterativo. En ambos casos se utiliza la recursión, pero el enfoque hacia ella es diferente.

En un proceso recursivo, todos los cálculos se posponen «para más tarde», como en el ejemplo con los números de Fibonacci. El cálculo final lo realiza la instancia de la función que se llamó por última vez, y luego los resultados se transmiten en cascada a los anteriores.

En un proceso iterativo, todo es al revés. La función calcula todo lo que puede calcular y solo entonces llama a su nueva instancia y le transmite los resultados.

💡
Un caso particular de recursión es la recursión de cola: en ella, la llamada a sí misma es lo último que hace la función antes de terminar.

Ventajas de la recursión

A mucha gente le gusta el enfoque recursivo porque es elegante y conciso, y describir dicho algoritmo a menudo es más rápido que un análogo. Estas son las principales ventajas de crear soluciones recurrentes.

  • Claridad. Leer código recursivo suele ser más fácil que un programa lleno de trucos para resolver el mismo problema sin recursión. Esta es una ventaja importante si se trata de programación comercial, donde otras personas suelen ver el código.
  • Claridad. Algunos problemas, como los mismos números de Fibonacci o los factoriales, son recursivos por su propia definición. Lo mismo ocurre con los problemas de series, fractales, etc. Resolver tal problema a través de la recursión es una de las formas más claras e intuitivas. Además: las personas usan la recursión todo el tiempo, incluso simplemente cuando hablan, y esto funciona una vez más para su comprensión intuitiva.
  • Brevedad. Una función recursiva suele ser más corta que una implementación sin recursión. Es más fácil y cómodo para el desarrollador escribir unas pocas líneas de código que crear un programa enorme, dedicar tiempo y esfuerzo y confundirse con lo escrito.
  • Belleza. Finalmente, muchos consideran que el propio concepto es hermoso y elegante. Y así es: mira los fractales y los copos de nieve: tienen una cierta belleza. La recursión se utiliza incluso en el arte: desde las muñecas matrioshka hasta los intrincados patrones que adornan las catedrales góticas.

Desventajas de la recursión

El enfoque recursivo tiene dos inconvenientes, pero son críticos y limitan seriamente la aplicación de este concepto incluso donde es obvio.

  • Riesgo de desbordamiento. Con todo lo dicho, los programadores usan la recursión con bastante cuidado. Está diseñado de tal manera que, hasta que se ejecute la última llamada a la función, las anteriores no terminarán, ya que, por así decirlo, «introducen» en sí mismas las siguientes. Por lo tanto, estos programas consumen muchos recursos de la computadora. Por lo tanto, los desarrolladores también consideran el parámetro de rendimiento y deciden qué es más rentable en un caso particular: usar recursión o no.
  • Riesgo de infinito. Si algo salió mal y el programador accidentalmente obtuvo una recursión infinita, la única salida es cerrar el programa por la fuerza. Y luego reescribirlo para que el error no se repita en el siguiente inicio.

Qué usar: recursión o bucle

Los inconvenientes anteriores no son una razón para abandonar por completo las soluciones recursivas. Simplemente, en cada caso donde se puede aplicar la recursión, el desarrollador debe preguntarse si es óptimo o no.

  • Si el programa requiere una alta velocidad de funcionamiento y una baja carga o existe riesgo de desbordamiento de memoria, es mejor elegir una opción sin recursión.
  • Si la velocidad no es tan importante, y la implementación sin recursión tomará mucho tiempo y muchas líneas de código, es mejor utilizar un enfoque recursivo.

La comprensión de qué es mejor usar en un caso particular llega con la experiencia. De todos modos, los desarrolladores principiantes deben dominar la recursión: es una parte importante de la programación y la informática en general.

Cómo empezar a trabajar con la recursión

El concepto y ejemplos de funciones recursivas se pueden encontrar en cualquier libro de texto de programación. Por lo general, a los principiantes se les recomienda practicar con tareas «clásicas» simples como los números de Fibonacci o el cálculo del factorial. Luego, puede pasar a tareas más complejas: recorrer un gráfico, analizar texto o cualquier otra cosa. Y qué lenguaje elegir depende de sus preferencias y deseos para la industria.

Si quieres familiarizarte con una gran cantidad de conceptos de informática, ¡apúntate a los cursos! Aprenderás cómo funcionan los diferentes procesos y darás los primeros pasos hacia una nueva profesión solicitada.

Categorizado en:

Fundamentos,