Recursión y Pila de Llamadas en JavaScript

La recursión es un concepto fundamental en JavaScript que permite a las funciones llamarse a sí mismas. Este método es esencial para resolver problemas que pueden descomponerse en tareas más simples y repetitivas. Este artículo ofrece una visión completa de la recursión, explorando el contexto de ejecución, la pila de llamadas y sus aplicaciones en el recorrido de estructuras recursivas.

¿Qué es la Recursión?

La recursión en programación es un método en el que una función se llama a sí misma una o más veces hasta que se cumple una condición específica, momento en el cual se procesa el resto de cada repetición. Toda función recursiva se construye a partir de exactamente dos partes:

1. Caso base: la condición bajo la cual la función deja de llamarse a sí misma y devuelve un valor directamente. Sin un caso base, la función se llamaría a sí misma indefinidamente.
2. Caso recursivo: cuando el caso base no se cumple, la función se llama a sí misma con un argumento menor o más simple que la acerca al caso base.

La regla más importante de la recursión: cada llamada recursiva debe avanzar hacia el caso base. Si no lo hace, se produce una recursión infinita y el programa falla con un desbordamiento de pila.

A continuación se muestra el ejemplo útil más pequeño posible: sumar los números del 1 al n:

Para calcular sumTo(5), la función necesita sumTo(4), que necesita sumTo(3), y así sucesivamente hasta sumTo(1), que devuelve 1 directamente. Luego la cadena se desenrolla: cada llamada suma su propio número y devuelve el resultado a quien la llamó.

La misma lógica siempre puede escribirse con un bucle. Compara la versión recursiva anterior con esta versión iterativa:

Ambas producen el mismo resultado. La versión recursiva es más corta y se acerca más a la definición matemática; la versión iterativa usa una sola llamada a función y una cantidad fija de memoria. Comparamos ambas con más detalle en Recursión vs Iteración más adelante.

Contexto de Ejecución y la Pila de Llamadas

Cuando una función se ejecuta en JavaScript, el motor crea un contexto de ejecución (a veces llamado marco de pila): un registro interno que contiene las variables locales de esa llamada, sus parámetros y la línea exacta donde se encuentra actualmente la ejecución.

La pila de llamadas es una pila de estos marcos. Funciona "último en entrar, primero en salir":

• Cuando se llama a una función, su marco se apila en la cima de la pila.
• Cuando una función devuelve, su marco se desapila y el control vuelve al marco de abajo — exactamente donde lo dejó.

En la recursión, cada llamada a la función apila un nuevo marco con su propia copia de los parámetros. Por lo tanto, sumTo(3) produce tres marcos apilados antes de que cualquiera de ellos devuelva:

sumTo(1)   ← cima de la pila, devuelve 1 primero
sumTo(2)
sumTo(3)   ← base, la llamada original, devuelve al final

Una vez que sumTo(1) alcanza el caso base y devuelve, su marco se desapila, sumTo(2) reanuda y devuelve, luego sumTo(3). Por eso la profundidad de la recursión determina directamente cuánta memoria usa la pila de llamadas: n llamadas recursivas significan n marcos activos al mismo tiempo.

Ejemplo: Sueños Anidados

Imagina un escenario donde un personaje de una historia se queda dormido y sueña que es otra persona, quien a su vez se queda dormida para soñar con otro personaje, y así sucesivamente. Cada nivel de sueño representa una llamada recursiva, y despertar de cada nivel de sueño representa desapilar un contexto de ejecución de la pila de llamadas.

En la función dream(level) proporcionada, el caso base y el caso recursivo están claramente definidos:

• Caso Base: Ocurre cuando level === 0. Es la condición que detiene la recursión para que no continúe indefinidamente. En este caso, cuando level llega a 0, la función imprime "Wake up!" y deja de hacer más llamadas recursivas.
• Caso Recursivo: Se define cuando level > 0. En esta situación, la función imprime el level actual y luego se llama a sí misma con level - 1, reduciendo así el level en uno en cada llamada. Esto continúa hasta que se cumple la condición del caso base.

Estas dos partes trabajan juntas para garantizar que la función se ejecute correctamente y termine eventualmente.

Recorridos Recursivos

El recorrido recursivo es una técnica que se utiliza frecuentemente con estructuras que contienen múltiples niveles de objetos anidados, como árboles o directorios. Este método es ideal para realizar operaciones como búsqueda o construcción de una estructura visual a partir de componentes anidados.

Ejemplo: Recorrido del Sistema de Archivos

Así es como podrías usar la recursión para recorrer un sistema de archivos, listando todos los archivos en cada directorio:

En la función listFiles(directory) compartida, la recursión implica recorrer una estructura de directorios:

• Caso Base: Curiosamente, la condición de parada de esta función no se expresa explícitamente como un caso base tradicional (como una sentencia if que termina la recursión). En cambio, se detiene de forma inherente cuando encuentra un directorio sin más subdirectorios (es decir, directory.directories es un array vacío). Esto ocurre porque el método forEach sobre un array vacío no genera más llamadas recursivas.
• Caso Recursivo: El caso recursivo se invoca explícitamente con directory.directories.forEach(listFiles);. Esto ocurre cuando un directorio contiene uno o más subdirectorios, y listFiles se llama recursivamente para cada subdirectorio. Cada llamada recursiva procesa los archivos y directorios dentro de ese subdirectorio, profundizando continuamente en la estructura hasta que no se encuentran más subdirectorios (caso base implícito).

Esta función demuestra eficazmente cómo la recursión puede navegar estructuras anidadas complejas llamándose a sí misma para manejar tareas similares en cada nivel de anidamiento.

Estructuras Recursivas

Las estructuras recursivas son estructuras autorreferenciales donde cada parte se define en términos de partes similares. Ejemplos comunes incluyen organigramas, árboles binarios y más.

Ejemplo: Organigrama

Considera un organigrama donde cada directivo puede tener varios subordinados que a su vez pueden ser directivos.

En la función showOrgChart(employee), la recursión está estructurada para visualizar un organigrama:

• Caso Base: Al igual que en el ejemplo anterior de listFiles, el caso base no se expresa explícitamente como un punto de parada condicional en la función. En cambio, la recursión termina de forma natural cuando un empleado no tiene subordinados (employee.subordinates es un array vacío). El método forEach no ejecuta ninguna iteración cuando el array está vacío, por lo que no se realizan más llamadas recursivas.
• Caso Recursivo: El comportamiento recursivo ocurre con la línea employee.subordinates.forEach(showOrgChart). Esto significa que cada vez que un empleado tiene uno o más subordinados, la función se llama recursivamente para cada subordinado. Esta recursión continúa hacia abajo en la jerarquía, registrando el nombre y el cargo de cada subordinado, hasta que llega a empleados sin subordinados (caso base implícito).

Esta función proporciona una demostración clara de cómo se puede usar la recursión para navegar y mostrar estructuras jerárquicas como los organigramas, donde cada nivel de recursión profundiza más en la estructura.

Recursión vs Iteración

Cualquier función recursiva puede reescribirse como un bucle, y cualquier bucle puede reescribirse como recursión. Elegir entre ellos es una compensación:

Una buena regla general: recurre a la recursión cuando los datos en sí son recursivos (árboles, objetos anidados, el sistema de archivos), y usa un bucle cuando simplemente repites un paso un número conocido de veces. El factorial a continuación es naturalmente recursivo, pero un bucle lo maneja igual de bien — y soporta entradas mucho mayores:

Desbordamiento de Pila y Límites de Profundidad

Dado que cada llamada recursiva añade un marco a la pila de llamadas, la recursión está acotada por qué tan profundo puede crecer la pila. Todo motor JavaScript tiene un tamaño máximo de pila (el número exacto varía según el motor y la plataforma — a menudo desde unos pocos miles hasta decenas de miles de marcos). Si se supera, el programa lanza:

RangeError: Maximum call stack size exceeded

Las dos causas más comunes son un caso base ausente o inalcanzable (recursión infinita) y una recursión legítimamente profunda sobre un conjunto de datos muy grande. Este ejemplo omite deliberadamente un caso base funcional para que la pila se llene:

Para evitar desbordamientos de pila:

• Incluye siempre un caso base al que la recursión esté garantizada de llegar.
• Para problemas muy profundos o sin límites definidos, convierte la recursión en un bucle, que no tiene tal límite de profundidad.
• Para estructuras de datos que pueden ser arbitrariamente profundas, considera usar una pila explícita (un array del que hagas push/pop) en lugar de la pila de llamadas.

Cuándo Usar la Recursión

La recursión es especialmente útil cuando puedes descomponer una tarea en subtareas más pequeñas similares a la tarea general. Es poderosa para:

• Ordenar datos (como con merge sort o quicksort)
• Recorrer árboles, grafos e iterables anidados
• Manipular datos estructurados complejos como JSON o el DOM

Sin embargo, es fundamental asegurarse de que cada llamada recursiva avance hacia el caso base para evitar la recursión infinita y posibles errores de desbordamiento de pila.

Temas Relacionados

• Funciones de JavaScript — cómo se declaran y llaman las funciones.
• Expresiones de Función — funciones almacenadas en variables, que las funciones recursivas suelen usar.
• Iterables — el recorrido recursivo se combina de forma natural con datos iterables.
• Bucles en JavaScript — la alternativa iterativa a la recursión.

Conclusión

Comprender la recursión y la pila de llamadas en JavaScript mejora tu capacidad para resolver problemas complejos de forma eficiente y efectiva. Con práctica, la recursión puede convertirse en una herramienta valiosa en tu arsenal de programación, permitiéndote escribir código más limpio y eficiente. Ya sea recorriendo estructuras de datos o implementando algoritmos complejos, dominar la recursión sin duda elevará tus habilidades de programación.

Práctica