Recursividad en JavaScript

¿Qué es la recursividad?

La recursividad es una técnica de programación donde una función se invoca a sí misma para resolver un problema. En lugar de usar bucles para iterar, la función se llama repetidamente con versiones más pequeñas del problema hasta llegar a una solución. La recursividad es elegante y poderosa para ciertos tipos de problemas.

La recursividad se basa en el principio de dividir y conquistar: divide el problema en subproblemas más pequeños, los resuelve recursivamente, y combina las soluciones para resolver el problema original. Este enfoque es especialmente útil para problemas con estructura jerárquica o recursiva como árboles, grafos y algoritmos de ordenamiento.

El ejemplo muestra una función recursiva que calcula el factorial. La función factorial se invoca a sí misma con un valor más pequeño (n - 1) hasta llegar al caso base (n === 0 o n === 1). Cada llamada reduce el problema, acercándose gradualmente a la solución.

Caso base y caso recursivo

Toda función recursiva tiene dos partes esenciales: el caso base y el caso recursivo. El caso base es la condición que detiene la recursión y retorna un valor sin invocar la función nuevamente. El caso recursivo es donde la función se invoca a sí misma con una versión más pequeña del problema.

El ejemplo muestra claramente el caso base y el caso recursivo. El caso base es cuando n <= 1, donde la función retorna 1 sin invocarse nuevamente. El caso recursivo es cuando n > 1, donde la función retorna n * factorial(n - 1), invocándose a sí misma con un valor más pequeño.

El caso base es la condición que detiene la recursión, mientras que el caso recursivo es la llamada que reduce el problema a una versión más pequeña. Es fundamental que cada llamada recursiva progrese hacia el caso base, acercándose gradualmente a la solución. Sin un caso base apropiado, la recursión se vuelve infinita y causa un stack overflow. Es importante notar que puede haber múltiples casos base en una función recursiva, cada uno manejando diferentes condiciones de terminación.

Recursividad vs Iteración

La recursividad y la iteración (bucles) son dos enfoques diferentes para resolver problemas repetitivos. La recursividad usa llamadas de función para repetir, mientras que la iteración usa bucles como for, while o do...while. Cada enfoque tiene ventajas y desventajas según el problema.

El ejemplo muestra el mismo problema (factorial) resuelto con recursividad y con iteración. Ambas soluciones producen el mismo resultado, pero el enfoque es diferente. La recursividad es más elegante para ciertos problemas, mientras que la iteración puede ser más eficiente en términos de memoria.

1. <strong>Recursividad:</strong> Usa llamadas de función, más elegante
2. <strong>Iteración:</strong> Usa bucles, más eficiente en memoria
3. <strong>Stack overflow:</strong> Recursividad puede causar stack overflow
4. <strong>Legibilidad:</strong> Recursividad puede ser más difícil de entender
5. <strong>Performance:</strong> Iteración suele ser más rápida
6. <strong>Elegir según problema:</strong> Cada problema tiene el enfoque ideal

Tipos de recursividad

Hay varios tipos de recursividad según la estructura de las llamadas y cómo se manejan los datos. Entender estos tipos te ayuda a elegir el enfoque correcto para cada problema y a escribir código más eficiente.

El ejemplo muestra diferentes tipos de recursividad. La recursividad directa es cuando la función se invoca a sí misma directamente. La recursividad indirecta es cuando la función invoca a otra función, que eventualmente invoca a la original. La recursión múltiple es cuando la función se invoca a sí misma múltiples veces en el caso recursivo.

Los tipos principales incluyen: recursividad directa donde la función se invoca a sí misma directamente, recursividad indirecta donde la función invoca a otra función que eventualmente invoca a la original (también llamada recursividad mutua cuando dos o más funciones se invocan entre sí), recursividad múltiple donde la función se invoca a sí misma múltiples veces en el caso recursivo, recursividad anidada donde hay recursividad dentro de recursividad, y tail recursion donde la llamada recursiva es la última operación de la función, permitiendo optimizaciones del compilador.

Pilas de llamada (Call Stack)

La recursividad usa la call stack (pila de llamadas) para rastrear las invocaciones de función. Cada vez que una función recursiva se invoca, se añade un nuevo frame a la call stack. Cuando se alcanza el caso base, los frames se remueven de la stack en orden inverso. Entender esto es esencial para evitar stack overflow.

El ejemplo muestra cómo la call stack crece con la recursividad. Cada invocación de factorial añade un nuevo frame a la stack. Cuando se alcanza el caso base, los frames se remueven de la stack. Si la recursión es demasiado profunda, la stack puede exceder su tamaño máximo, causando un stack overflow.

El proceso funciona así: cada invocación recursiva hace un push, añadiendo un nuevo frame a la stack, y cada retorno hace un pop, removiendo un frame. La call stack sigue el principio LIFO (Last In, First Out), donde el último frame en entrar es el primero en salir. El stack overflow ocurre cuando la stack excede su tamaño máximo, típicamente por recursión infinita o demasiado profunda. La profundidad de la recursión determina cuántos frames se añaden a la stack, y por lo tanto el riesgo de stack overflow.

Casos de uso prácticos

La recursividad tiene numerosos casos de uso prácticos en JavaScript. Desde recorrer estructuras jerárquicas hasta implementar algoritmos de ordenamiento, la recursividad es una herramienta poderosa para resolver problemas complejos de forma elegante.

El ejemplo muestra varios casos de uso prácticos de recursividad. Recorrer árboles es un caso clásico donde la recursividad es más natural que la iteración. Calcular el factorial y la serie de Fibonacci son ejemplos matemáticos. Buscar en estructuras anidadas es otro caso donde la recursividad simplifica el código.

1. <strong>Recorrer árboles:</strong> Estructuras jerárquicas como DOM o JSON
2. <strong>Algoritmos:</strong> QuickSort, MergeSort, búsqueda binaria
3. <strong>Matemáticas:</strong> Factorial, Fibonacci, potencias
4. <strong>Permutaciones:</strong> Generar todas las combinaciones posibles
5. <strong>Búsqueda:</strong> Buscar en estructuras anidadas complejas
6. <strong>Validación:</strong> Validar estructuras recursivas

Resumen