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 dividirse en tareas más simples y repetitivas. Este artículo ofrece una visión general 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?

En programación, la recursió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. Así es como funciona:

1. Caso base: Esta es la condición bajo la cual termina la recursión.
2. Caso recursivo: Si no se cumple el caso base, la función se llama a sí misma nuevamente con un nuevo conjunto de parámetros.

Cada vez que se llama a una función recursiva, crea una nueva entrada en la pila de llamadas, que es esencialmente un registro de las llamadas a funciones en curso.

Contexto de ejecución y pila de llamadas

Cuando una función se ejecuta en JavaScript, el motor de JavaScript crea un contexto de ejecución que incluye todas las variables, los parámetros y la posición actual dentro de la función. La pila de llamadas es esencialmente una pila de estos contextos de ejecución. En la recursión, cada llamada a una función recursiva crea un nuevo contexto de ejecución que se apila en la pila.

INFO

Ten en cuenta las limitaciones de tamaño de la pila en JavaScript. Las funciones recursivas pueden consumir rápidamente el espacio de la pila, lo que provoca un error de "Maximum call stack size exceeded" (tamaño máximo de la pila de llamadas excedido). Para evitarlo, optimiza tus algoritmos recursivos o considera usar un enfoque iterativo para llamadas profundamente anidadas.

Ejemplo: Sueños anidados

Imagina un escenario en el que 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 sacar un contexto de ejecución de la pila de llamadas.

---

Output appears here after Run.

In the dream(level) function you provided, the base case and recursive case are clearly defined:

• Caso base: Esto ocurre cuando level === 0. Es la condición que evita que la recursión continúe indefinidamente. En este caso, cuando level llega a 0, la función imprime "Wake up!" y deja de hacer llamadas recursivas adicionales.
• Caso recursivo: Esto se define cuando level > 0. En esta situación, la función imprime el level actual y luego se llama a sí misma nuevamente con level - 1, reduciendo así el level en uno por 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 usa a menudo con estructuras que contienen múltiples niveles de objetos anidados, como árboles o directorios. Este método es ideal para realizar operaciones como búsquedas o construir 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:

---

Output appears here after Run.

In the listFiles(directory) function you shared, the recursion involves traversing a directory structure:

• Caso base: Curiosamente, la condición de parada de esta función no se establece explícitamente como un caso base tradicional (como una sentencia if que termina la recursión). En cambio, deja de recursar inherentemente cuando encuentra un directorio sin subdirectorios adicionales (es decir, directory.directories es un array vacío). Esto se debe a que el método forEach en un array vacío no genera llamadas recursivas adicionales.
• 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 por 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. Los ejemplos comunes incluyen organigramas, árboles binarios y más.

Ejemplo: Organigrama

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

---

Output appears here after Run.

In the showOrgChart(employee) function, the recursion is structured to visualize an organizational chart:

• Caso base: Similar al ejemplo anterior de listFiles, el caso base no se establece explícitamente como un punto de parada condicional en la función. En cambio, la recursión termina naturalmente 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 llamadas recursivas adicionales.
• 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 descendiendo por la jerarquía, registrando el nombre y el puesto de cada subordinado, hasta llegar a empleados sin subordinados (caso base implícito).

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

Cuándo usar la recursión

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

• Ordenar datos (como con merge sort o quicksort)
• Recorrer árboles y grafos
• Manipular datos estructurados complejos

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

Conclusión

Entender la recursión y la pila de llamadas en JavaScript mejora tu capacidad para resolver problemas complejos de manera eficiente y efectiva. Con la 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 codificación.

Practice

¿Qué es la recursión en JavaScript y cómo funciona?

La recursión es cuando una función se llama a sí misma.La recursión no puede usarse para resolver tareas de forma 'tradicional'.La recursión se usa para reemplazar bucles.Una llamada recursiva (de bucle) puede ser reemplazada por un bucle. La elección entre ellos depende de cuál sea más conveniente.Todo proceso recursivo también puede realizarse de forma iterativa.Todo proceso iterativo también puede implementarse con recursión.