Recursividad en JavaScript: ¿Cómo entender? Con ejemplos!

La recursividad en JavaScript es una técnica poderosa donde una función se llama a sí misma para resolver problemas complejos de manera elegante y eficiente. Conocer qué es, sus características y cómo entenderla te permitirá abordar tareas como cálculos repetitivos o estructuras jerárquicas. En este artículo, exploramos ejemplos prácticos, para qué sirve y cómo hacer que funcione correctamente en tu código.

1. ¿Qué es la recursividad en JavaScript?

La recursividad en JavaScript (y en otros lenguajes de programación) es una técnica donde una función se llama a sí misma directa o indirectamente para resolver un problema.

Este enfoque es útil para resolver problemas que pueden dividirse en subproblemas más pequeños del mismo tipo, como cálculos matemáticos o tareas que tienen una estructura jerárquica o repetitiva.

1. Componentes clave de la recursividad:
2. Sintaxis de una función recursiva:
3. ¿Cómo entender la recursividad de manera mas simple?

1.1. Componentes clave de la recursividad:

1. Caso base:
   • Es la condición que detiene la recursión. Sin él, la función se llamaría infinitamente y terminaría causando un error de «stack overflow».
2. Llamada recursiva:
   • Es la parte donde la función se llama a sí misma con un subconjunto del problema original, moviéndose hacia el caso base.

1.2. Sintaxis de una función recursiva:

La sintaxis básica de una función recursiva en JavaScript es la siguiente:

function nombreFuncion(parametros) {
    if (condicionBase) { // Caso base
        // Código que detiene la recursión
        return valorBase;
    }

    // Llamada recursiva con un problema reducido
    return nombreFuncion(argumentosModificados);
}Lenguaje del código: JavaScript (javascript)

Explicación de cada parte:

1. Definición de la función:
   Se declara como cualquier otra función, pero su característica especial es que se llama a sí misma dentro de su cuerpo.
2. Parámetros:
   Los parámetros se utiliza al menos un parámetro para representar el estado o progreso del problema. Cada vez que la función se llama recursivamente, este parámetro cambia para acercarse al caso base.
3. Caso base (condicionBase):
   • Es una condición que detiene la recursión.
   • Sin un caso base, la función continuará llamándose a sí misma indefinidamente, causando un error de stack overflow.
   • El caso base indica cuándo se ha llegado a la solución del problema.
4. Llamada recursiva:
   • Aquí, la función se llama a sí misma, pero con argumentos modificados, que representan una parte más pequeña del problema.
   • Cada llamada recursiva se «apila» hasta que se cumple el caso base.
5. Retorno:
   El valor de retorno de la función recursiva se propaga hacia atrás por las llamadas apiladas hasta que llega a la primera invocación.

1.3. ¿Cómo entender la recursividad de manera mas simple?

Imagina que tienes una torre de platos apilados y quieres lavarlos. Las reglas para lavar los platos son:

1. Solo puedes lavar un plato a la vez (no puedes tomar toda la torre).
2. Debes empezar con el plato de arriba y trabajar hacia abajo.
3. Cuando termines con un plato, sigues con el siguiente hasta que no quede ninguno.

Ahora, supongamos que eres un poco olvidadizo y, para recordarte qué hacer, cada vez que tomas un plato, te dices:
«Lavo este plato y luego me encargo de la torre restante.»

Cuando llegas al último plato (el caso base), ya no queda una torre, así que solo dices:
«Lavo este plato, ¡y terminé!»

ESTO ES RECURSIVIDAD: Un problema grande (lavar toda la torre) se divide en subproblemas más pequeños del mismo tipo (lavar un plato a la vez), hasta llegar a un punto donde ya no hay más pasos que realizar (el caso base).

1.3.1. Veamos este ejemplo de recursividad con un ejemplo en código:

function lavarPlatos(platos) {
    if (platos === 0) { // Caso base: no hay más platos
        console.log("¡Todos los platos están limpios!");
        return;
    }

    console.log(`Lavando el plato número ${platos}...`);
    lavarPlatos(platos - 1); // Llamada recursiva: me encargo de los platos restantes
}

// Empezamos con 5 platos
lavarPlatos(5);Lenguaje del código: JavaScript (javascript)

SALIDA:

Lavando el plato número 5...
Lavando el plato número 4...
Lavando el plato número 3...
Lavando el plato número 2...
Lavando el plato número 1...
¡Todos los platos están limpios!

¿Qué sucede en este ejemplo?

Si no guiamos con la sintaxis del punto 1.1., en este ejemplo tenemos un caso base que especifica una condición, que dada la misma, finaliza la tarea de la función. Y tenemos una llamada recursiva, que finalizada una tarea, llama de nuevo a la función para la siguiente tarea, pero con una nueva condición.

Ampliemos esta explicación:

• Caso base:
  • La condición if (platos === 0) detiene la recursión.
  • Esto evita que el programa siga llamándose infinitamente.
  • Cuando llega aquí, imprime: ¡Todos los platos están limpios! y termina la función con return.
• Llamada recursiva:
  • En cada llamada a lavarPlatos(platos - 1), la función se llama a sí misma con un número menor de platos.
  • Esto crea una «pila de llamadas» (call stack) donde cada instancia de la función espera que la siguiente termine.
• Proceso:
  • La función realiza una acción en el momento actual (console.log) y luego delega el resto del trabajo a la siguiente instancia de la función.

Ahora veamos el flujo de ejecución de este ejemplo:

Una vez que se llama a la función a lavarPlatos(5), sucede lo siguiente:

• Primera llamada: lavarPlatos(5)
  • platos === 5, así que no entra en el caso base.
  • Imprime: Lavando el plato número 5....
  • Llama a sí misma con lavarPlatos(4).
• Segunda llamada: lavarPlatos(4)
  • platos === 4, así que no entra en el caso base.
  • Imprime: Lavando el plato número 4....
  • Llama a sí misma con lavarPlatos(3).
• Tercera llamada: lavarPlatos(3)
  • platos === 3, así que no entra en el caso base.
  • Imprime: Lavando el plato número 3....
  • Llama a sí misma con lavarPlatos(2).
• Cuarta llamada: lavarPlatos(2)
  • platos === 2, así que no entra en el caso base.
  • Imprime: Lavando el plato número 2....
  • Llama a sí misma con lavarPlatos(1).
• Quinta llamada: lavarPlatos(1)
  • platos === 1, así que no entra en el caso base.
  • Imprime: Lavando el plato número 1....
  • Llama a sí misma con lavarPlatos(0).
• Sexta llamada (última): lavarPlatos(0)
  • Ahora sí entra en el caso base, porque platos === 0.
  • Imprime: ¡Todos los platos están limpios!.
  • Termina la ejecución de esta instancia con return.

CONCLUSIÓN:

• Cada llamada recursiva maneja un plato, imprime un mensaje y delega el resto a la siguiente instancia.
• La condición base asegura que el programa no entre en un bucle infinito.
• Cuando el caso base se cumple (platos === 0), todas las funciones pendientes terminan de ejecutarse y la pila se libera.

2. ¿Para que sirven las funciones recursivas en JS?

Las funciones recursivas son especialmente útiles cuando un problema tiene una estructura repetitiva o jerárquica.

Aquí te dejo casos comunes donde suelen usarse:

1. Cálculos matemáticos
   Los problemas matemáticos que siguen fórmulas definidas recursivamente son perfectos para implementar con recursividad. Algunos ejemplos incluyen:
   • Factorial (n!): El cálculo del factorial se define como n! = n * (n - 1)!.
   • Serie de Fibonacci: La serie Fibonacci se define como F(n) = F(n - 1) + F(n - 2), con los valores base F(0) = 0 y F(1) = 1.
   • Suma de números: Calcular la suma de los números del 1 a n.
2. Estructuras jerárquicas
   Cuando los datos están organizados de forma jerárquica o en forma de árbol, como:
   • Explorar directorios y archivos en un sistema de archivos.
   • Manipular objetos JSON anidados: Por ejemplo, buscar una clave o valor dentro de un objeto profundo.
3. Problemas de teoría de grafos
   Algunos problemas de grafos pueden resolverse recursivamente, como:
   • Búsqueda en profundidad (DFS): Es útil para recorrer grafos o árboles.
   • Encontrar el camino más corto entre nodos.
4. Dividir y conquistar
   Los algoritmos que dividen un problema en partes más pequeñas y lo resuelven recursivamente, como:
   • Merge Sort y Quick Sort: Algoritmos de ordenamiento que dividen el array en subarrays, los ordenan, y luego los combinan.
   • Búsqueda binaria: Divide el array en mitades para buscar un elemento rápidamente.
5. Resolución de laberintos o juegos
   Resolver problemas como:
   • Encontrar un camino en un laberinto.
   • Resolver el juego de las torres de Hanoi.
   • Resolver un Sudoku.
6. Algoritmos de cadenas y arrays
   Ejemplos incluyen:
   • Inversión de una cadena o array.
   • Encontrar subsecuencias o subconjuntos de un array.
7. Problemas combinatorios
   Resolver problemas que implican generar todas las posibles combinaciones o permutaciones, como:
   • Generar subconjuntos.
   • Resolver problemas de camino más corto o el problema del viajero.

2.1. ¿Cuándo NO usar recursividad?

• Problemas muy grandes:
  • Si el número de llamadas recursivas es alto, puede llevar a un error de stack overflow.
• Tareas iterativas simples:
  • En muchos casos, un bucle for o while es más eficiente que la recursividad.

3. Las funciones recursivas y los bucles (for o while) en JS.

Las funciones recursivas y los bucles pueden devolver el mismo resultado porque ambos se usan para resolver problemas repetitivos. Sin embargo, la diferencia principal radica en cuándo y por qué usarlos, dependiendo del contexto y las prioridades del problema.

1. ¿Cuándo usar recursión?
2. ¿Cuándo usar bucles?
3. Diferencia de eficiencia de ambos casos:

3.1. ¿Cuándo usar recursión?

1. Estructuras naturales recursivas:
   • Como árboles, gráficos o problemas que se descomponen en subproblemas similares (por ejemplo, factorial, Fibonacci, búsqueda binaria).
2. Legibilidad:
   • Si la recursión hace que el código sea más intuitivo y fácil de leer.
3. Tamaño pequeño del problema:
   • Si el número de llamadas recursivas es limitado y no hay riesgo de desbordar la pila de llamadas.

3.1.1. Ejemplo recursivo:

Recorrer un árbol binario.

function recorrerArbol(nodo) {
    if (!nodo) return; // Caso base
    console.log(nodo.valor); // Procesar nodo
    recorrerArbol(nodo.izquierdo); // Llamada recursiva
    recorrerArbol(nodo.derecho); // Llamada recursiva
}Lenguaje del código: JavaScript (javascript)

Este código es un ejemplo clásico de cómo recorrer un árbol binario utilizando recursión.

3.2. ¿Cuándo usar bucles?

1. Problemas lineales o iterativos:
   • Cuando necesitas recorrer un rango o procesar una lista de elementos.
2. Eficiencia:
   • Los bucles son más rápidos y consumen menos memoria, ya que no usan la pila de llamadas.
3. Evitar límites de la pila:
   • Si el problema tiene muchas iteraciones (como millones de pasos), un bucle es más seguro.

3.2.1. Ejemplo de bucle ideal:

Procesar una lista de números.

function procesarLista(lista) {
    for (let i = 0; i < lista.length; i++) {
        console.log(lista[i]); // Procesar cada elemento
    }
}Lenguaje del código: JavaScript (javascript)

Este es un bucle, donde la función procesarLista recorre todos los elementos de una lista (o array) y realiza una acción con cada uno de ellos, en este caso, los imprime en la consola.

3.3. Diferencia de eficiencia de ambos casos:

1. Recursión:
   • Consume más memoria porque cada llamada recursiva se guarda en la pila.
   • Puede ser menos eficiente para grandes conjuntos de datos o cálculos profundos.
2. Bucle:
   • Consume menos memoria porque no depende de la pila.
   • Es más rápido y eficiente para tareas repetitivas simples.

RESUMEN:

• Sí, ambos devuelven el mismo resultado en muchos casos, pero la elección depende del contexto:
  • Usa recursión para problemas con estructura recursiva natural o cuando necesitas claridad.
  • Usa bucles para eficiencia y tareas repetitivas simples.

La clave está en analizar las necesidades del problema antes de elegir.

4. La pila de llamada (Call Stack) y la recursividad en JavaScript.

1. ¿Qué es la pila de llamadas (Call Stack)?
2. Cómo funciona la pila de llamadas
3. Problemas comunes: Desbordamiento de pila (Stack Overflow)
4. ¿Cómo evitar el desbordamiento de pila?
5. Conclusión sobre las pilas de llamadas y la recursividad en JS.

4.1. ¿Qué es la pila de llamadas (Call Stack)?

La pila de llamadas es una estructura de datos utilizada por JavaScript para realizar un seguimiento de qué función está siendo ejecutada en un momento dado, y de las funciones que deben completarse después.

Funciona como una pila (stack), siguiendo el principio de último en entrar, primero en salir (LIFO – Last In, First Out).

Cuando una función es llamada:

1. Se agrega (o «apila») en la pila de llamadas.
2. Cuando la función termina, se elimina (o «desapila») de la pila.

4.2. Cómo funciona la pila de llamadas

4.2.1. Flujo básico

Cuando ejecutamos código que llama funciones (incluyendo funciones recursivas):

1. La función actual se coloca en la pila.
2. Si esa función llama a otra función, esta última también se coloca en la pila.
3. Esto continúa hasta que se alcanza una función que no llama a ninguna otra (o se alcanza el caso base en la recursión).
4. Las funciones comienzan a «desapilarse» en el orden inverso al que fueron apiladas, devolviendo valores si corresponde.

4.2.2. Ejemplo simple: Llamadas no recursivas

function greet() {
    console.log("Hola");
    askQuestion();
}

function askQuestion() {
    console.log("¿Cómo estás?");
    sayGoodbye();
}

function sayGoodbye() {
    console.log("Adiós");
}

greet();Lenguaje del código: JavaScript (javascript)

Pila de llamadas durante la ejecución:

1. greet() es llamada y se apila.
2. greet() llama a askQuestion(), que se apila.
3. askQuestion() llama a sayGoodbye(), que se apila.
4. sayGoodbye() termina y se desapila.
5. askQuestion() termina y se desapila.
6. greet() termina y se desapila.

4.2.3. Ejemplo de pila de llamada con recursión: Factorial

function factorial(n) {
    if (n === 0) return 1; // Caso base
    return n * factorial(n - 1); // Caso recursivo
}

console.log(factorial(3)); // 6Lenguaje del código: JavaScript (javascript)

Pila de llamadas para factorial(3)

1. factorial(3) se apila.
2. factorial(3) llama a factorial(2), que se apila.
3. factorial(2) llama a factorial(1), que se apila.
4. factorial(1) llama a factorial(0), que se apila.
5. factorial(0) devuelve 1 y se desapila.
6. factorial(1) devuelve 1×1=11 \times 1 = 11×1=1 y se desapila.
7. factorial(2) devuelve 2×1=22 \times 1 = 22×1=2 y se desapila.
8. factorial(3) devuelve 3×2=63 \times 2 = 63×2=6 y se desapila.

4.3. Problemas comunes: Desbordamiento de pila (Stack Overflow)

4.3.1. ¿Qué es el desbordamiento de pila?

Ocurre cuando la pila de llamadas se llena con demasiadas funciones, sin que estas se desapilen, debido a un error en el caso base o en la lógica recursiva. Esto consume toda la memoria asignada a la pila, y el programa lanza un error.

4.3.2. Ejemplo de desbordamiento: Falta de caso base

function infiniteRecursion() {
    console.log("Llamando recursivamente...");
    infiniteRecursion(); // No hay caso base, la función nunca termina.
}

infiniteRecursion();Lenguaje del código: JavaScript (javascript)

Este código provoca un error «Maximum call stack size exceeded» porque la función se llama infinitamente, llenando la pila de llamadas.

4.4. ¿Cómo evitar el desbordamiento de pila?

1. Asegurarse de definir un caso base adecuado:
   • El caso base debe garantizar que la recursión termine en algún punto.
2. Evitar lógica compleja que retrase el caso base:
   • Si el caso base no se alcanza rápidamente debido a condiciones mal definidas, el programa podría exceder el límite de la pila.
3. Usar técnicas iterativas cuando sea posible:
   • Si el problema puede resolverse mediante un bucle en lugar de una recursión, en algunos casos será más eficiente.

4.5. Conclusión sobre las pilas de llamadas y la recursividad en JS.

La pila de llamadas es un concepto central para entender cómo funciona la recursión en JavaScript. Para manejar recursión de manera eficiente:

• Define siempre un caso base claro.
• Reduce el problema en cada llamada.
• Ten cuidado con problemas grandes que puedan causar desbordamientos.

5. Recursión directa vs recursión indirecta en JavaScript.

Vamos a profundizar en las diferencias entre recursión directa e indirecta con ejemplos detallados:

1. Recursión Directa
2. Recursión Indirecta
3. Diferencias clave:
4. Conclusión:

5.1. Recursión Directa

La recursión directa ocurre cuando una función se llama a sí misma directamente en su cuerpo. Este es el caso más común de recursión.

ESTRUCTURA:

function funcionA() {
    // Lógica de la función
    funcionA(); // Llamada a sí misma
}Lenguaje del código: JavaScript (javascript)

EJEMPLO: Cuenta regresiva

function countdown(n) {
    if (n <= 0) { // Caso base
        console.log("Fin de la cuenta regresiva");
        return;
    }
    console.log(n); // Imprime el número actual
    countdown(n - 1); // Llamada recursiva con n reducido
}

countdown(5);Lenguaje del código: JavaScript (javascript)

Explicación:

1. La función countdown se llama con un valor inicial, por ejemplo, 5.
2. Si el valor de n es mayor que 0, la función imprime n y luego se llama a sí misma con n - 1.
3. Cuando n llega a 0, se alcanza el caso base y la función deja de llamarse a sí misma.

PILA DE LLAMADA PARA countdown(3)

1. Se llama countdown(3) → se imprime 3.
2. Llama a countdown(2) → se imprime 2.
3. Llama a countdown(1) → se imprime 1.
4. Llama a countdown(0) → se imprime «Fin de la cuenta regresiva».
5. Todas las llamadas se desapilan, y la ejecución termina.

5.2. Recursión Indirecta

La recursión indirecta ocurre cuando una función llama a otra función, que a su vez llama a la primera. Aunque el flujo es más complejo que en la recursión directa, sigue siendo un caso válido de recursión.

ESTRUCTURA:

function funcionA() {
    // Lógica de la función
    funcionB(); // Llama a otra función
}

function funcionB() {
    // Lógica de la función
    funcionA(); // Llama a la función original
}Lenguaje del código: JavaScript (javascript)

EJEMPLO: Alternar entre dos funciones

function evenOrOdd(n) {
    if (n === 0) {
        console.log("El número es par");
        return;
    }
    if (n === 1) {
        console.log("El número es impar");
        return;
    }
    odd(n - 1); // Llama a la función odd
}

function odd(n) {
    evenOrOdd(n - 1); // Llama a la función evenOrOdd
}

evenOrOdd(5);Lenguaje del código: JavaScript (javascript)

Explicación:

1. La función evenOrOdd determina si un número es par o impar usando recursión indirecta.
2. Si n no es 0 (par) o 1 (impar), llama a la función odd.
3. La función odd, a su vez, reduce el número en 1 y llama nuevamente a evenOrOdd.
4. Este proceso alterna entre las dos funciones hasta que se alcanza el caso base (n === 0 o n === 1).

PILA DE LLAMADA PARA evenOrOdd(3)

1. Se llama evenOrOdd(3) → llama a odd(2).
2. odd(2) llama a evenOrOdd(1).
3. evenOrOdd(1) imprime «El número es impar» y deja de llamarse.

5.3. Diferencias clave:

Aspecto	Recursión Directa	Recursión Indirecta
Llamada	La función se llama directamente a sí misma.	Una función llama a otra, que luego llama a la primera.
Complejidad	Más simple de entender y seguir.	Más compleja debido a la interacción entre múltiples funciones.
Ejemplo clásico	Factorial, Fibonacci, cuenta regresiva.	Alternar entre funciones, validación de reglas cruzadas.

5.4. Conclusión:

• Recursión directa es más simple y común, adecuada para problemas como factoriales, Fibonacci, o cuentas regresivas.
• Recursión indirecta se utiliza en casos más complejos donde la lógica necesita distribuirse entre múltiples funciones.

6. Entendiendo la recursión de cola (Tail Recursion).

1. ¿Qué es la Recursión de Cola (Tail Recursion)?
2. Ventajas de la recursión de cola:
3. Estructura de la recursión de cola:
4. Ejemplo: Factorial usando Recursión de Cola
5. Soporte de Tail Call Optimization (TCO)
6. Comparación: Recursión normal vs Recursión de cola
7. Conclusión:

6.1. ¿Qué es la Recursión de Cola (Tail Recursion)?

La recursión de cola es un caso particular de recursión donde la llamada recursiva es la última instrucción de la función.
Esto significa que no queda ningún cálculo pendiente después de la llamada recursiva, permitiendo al intérprete optimizar el uso de la pila de llamadas.

6.2. Ventajas de la recursión de cola:

1. Optimización de la pila de llamadas:
   • Si el motor de JavaScript soporta «Tail Call Optimization» (TCO), no se crea una nueva entrada en la pila para cada llamada recursiva. En su lugar, reutiliza la misma entrada.
2. Evita el desbordamiento de pila (Stack Overflow):
   • Es ideal para manejar problemas recursivos con grandes profundidades sin agotar la memoria.
3. Más eficiente en términos de rendimiento comparado con la recursión tradicional.

6.3. Estructura de la recursión de cola:

function tailRecursiveFunction(params, accumulator) {
    if (/* condición de caso base */) {
        return /* valor final */;
    }
    return tailRecursiveFunction(/* nuevos parámetros */, /* acumulador actualizado */);
}Lenguaje del código: JavaScript (javascript)

6.4. Ejemplo: Factorial usando Recursión de Cola

Comparemos una versión no optimizada con una optimizada.

6.4.1. Factorial con recursión tradicional:

function factorial(n) {
    if (n === 0) return 1; // Caso base
    return n * factorial(n - 1); // Llamada recursiva con cálculo pendiente
}

console.log(factorial(5)); // Salida: 120Lenguaje del código: JavaScript (javascript)

Explicación:

1. La llamada recursiva no es la última operación. El cálculo n * factorial(n - 1) se realiza después de que la función regresa.
2. Esto acumula múltiples operaciones pendientes en la pila.

6.4.2. Factorial con recursión de cola

function tailFactorial(n, accumulator = 1) {
    if (n === 0) return accumulator; // Caso base
    return tailFactorial(n - 1, accumulator * n); // Llamada recursiva en la última línea
}

console.log(tailFactorial(5)); // Salida: 120Lenguaje del código: JavaScript (javascript)

Explicación:

1. La llamada recursiva tailFactorial(n - 1, accumulator * n) es la última instrucción de la función.
2. No quedan operaciones pendientes después de la llamada.
3. En cada llamada, el acumulador lleva el resultado parcial, lo que elimina la necesidad de almacenar operaciones intermedias.

6.5. Soporte de Tail Call Optimization (TCO)

Aunque la recursión de cola puede ser eficiente, no todos los motores de JavaScript soportan la optimización de llamadas de cola.
Actualmente:

• Motores que soportan TCO: El motor de JavaScript en Safari (JavaScriptCore) lo soporta.
• Motores que no soportan TCO: V8 (usado en Chrome y Node.js) aún no incluye esta optimización.

6.6. Comparación: Recursión normal vs Recursión de cola

Aspecto	Recursión Tradicional	Recursión de Cola
Llamada recursiva	Puede no ser la última instrucción.	Siempre es la última instrucción.
Acumulación en la pila	Sí, acumula operaciones pendientes.	No, reutiliza la misma entrada.
Eficiencia de la memoria	Menor eficiencia.	Mayor eficiencia si TCO está habilitado.
Uso típico	Problemas simples o con pocas iteraciones.	Problemas con grandes iteraciones.

6.7. Conclusión:

• La recursión de cola es una técnica eficiente que evita desbordamientos de pila si el motor soporta TCO.
• Aunque no todos los entornos de JavaScript lo soportan, es una buena práctica estructurar funciones recursivas de esta forma cuando sea posible.

7. Optimización de recursividad en JavaScript.

La optimización en recursión busca hacer que los algoritmos sean más eficientes, reduciendo tiempo de ejecución y consumo de memoria. Esto es especialmente importante en problemas donde las llamadas recursivas generan cálculos redundantes o donde la profundidad de la recursión puede ser significativa.

Aquí te explicamos dos enfoques diferentes de optimización:

1. Memoization
2. Divide y Vencerás
3. Comparación: Memoization vs Divide y Vencerás
4. Conclusión:

7.1. Memoization

La memoización es una técnica para guardar los resultados de cálculos ya realizados y reutilizarlos en lugar de repetir las operaciones. Esto es especialmente útil en problemas con subproblemas que se repiten, como en la Serie de Fibonacci.

7.1.1. Ejemplo: Fibonacci con memoization

Sin memoization, calcular la Serie de Fibonacci recursivamente implica recalcular muchas veces los mismos valores. Esto lleva a un rendimiento exponencial.

Código sin memoization

function fib(n) {
    if (n <= 1) return n; // Caso base
    return fib(n - 1) + fib(n - 2); // Llamadas recursivas redundantes
}

console.log(fib(6)); // Salida: 8Lenguaje del código: JavaScript (javascript)

PROBLEMA: En este enfoque, los mismos cálculos (por ejemplo, fib(3), fib(2)) se realizan varias veces, lo que resulta ineficiente.

Código con memoization

const fib = (function () {
    const memo = {}; // Objeto para almacenar resultados calculados
    return function (n) {
        if (n in memo) return memo[n]; // Si ya está calculado, lo devolvemos
        if (n <= 1) return n; // Caso base
        return (memo[n] = fib(n - 1) + fib(n - 2)); // Guardar y devolver resultado
    };
})();

console.log(fib(6)); // Salida: 8Lenguaje del código: JavaScript (javascript)

Explicación:

1. memo es un objeto que almacena los valores ya calculados.
2. Antes de calcular fib(n), verificamos si ya está en el objeto memo. Si está, lo devolvemos inmediatamente.
3. Si no, realizamos el cálculo, lo guardamos en memo y luego lo devolvemos.
4. Esto reduce significativamente el número de llamadas recursivas, pasando de exponencial a lineal en este caso.

7.2. Divide y Vencerás

El enfoque de divide y vencerás implica dividir un problema grande en subproblemas más pequeños, resolver cada uno de forma recursiva e independiente y combinar los resultados. Este enfoque es útil para problemas que pueden descomponerse en partes independientes.

7.2.1. Ejemplo: Ordenamiento Por Merge Sort

El algoritmo Merge Sort utiliza el enfoque de divide y vencerás para ordenar un arreglo.

function mergeSort(arr) {
    if (arr.length <= 1) return arr; // Caso base: arreglo de tamaño 1 o vacío

    const mid = Math.floor(arr.length / 2); // Dividir el arreglo en dos mitades
    const left = mergeSort(arr.slice(0, mid)); // Recursión en la mitad izquierda
    const right = mergeSort(arr.slice(mid)); // Recursión en la mitad derecha

    return merge(left, right); // Combinar las dos mitades ordenadas
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    // Combinar elementos en orden
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    // Agregar elementos restantes
    return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([5, 3, 8, 6, 2, 7])); // Salida: [2, 3, 5, 6, 7, 8]Lenguaje del código: JavaScript (javascript)

Explicación:

1. Dividir: El arreglo se divide en dos mitades recursivamente hasta que cada subarreglo tiene un tamaño de 1 (caso base).
2. Resolver: Cada subarreglo de tamaño 1 se considera ordenado.
3. Combinar: Las dos mitades ordenadas se combinan en un único arreglo ordenado utilizando la función merge.

7.3. Comparación: Memoization vs Divide y Vencerás

Aspecto	Memoization	Divide y Vencerás
Enfoque	Evitar cálculos redundantes.	Dividir un problema en subproblemas.
Estructura de datos	Generalmente usa un objeto o mapa.	No requiere almacenamiento adicional.
Casos comunes	Problemas con subproblemas repetidos.	Problemas que pueden dividirse fácilmente.
Ejemplo clásico	Fibonacci, problemas de programación dinámica.	Merge Sort, potencia por división.

7.4. Conclusión:

• Memoization es ideal para problemas con subproblemas repetidos y mejora el rendimiento al evitar cálculos redundantes.
• Divide y vencerás es útil cuando los subproblemas son independientes y pueden combinarse eficientemente.
• Ambos enfoques son esenciales para optimizar la recursividad, dependiendo del tipo de problema que estés resolviendo.

8. Analizar la complejidad de la recursión.

1. ¿Qué es la complejidad de la recursión?
2. Tiempo (O): cantidad de operaciones
3. Espacio (S): memoria utilizada
4. Relación entre tiempo y espacio
5. Comparación con una solución iterativa

8.1. ¿Qué es la complejidad de la recursión?

La complejidad de la recursión se refiere a la evaluación de los recursos necesarios para que una solución recursiva resuelva un problema.

Esto incluye:

1. Tiempo (O): La cantidad de operaciones o pasos que ejecuta el algoritmo.
2. Espacio (S): La memoria utilizada durante la ejecución del algoritmo, especialmente por la pila de llamadas en recursión.

¿PORQUÉ ES IMPORTANTE CONOCER ESTO?

Estas dos métricas ayudan a analizar cuán eficiente es una solución recursiva y a compararla con otras alternativas, como soluciones iterativas.

8.2. Tiempo (O): cantidad de operaciones

La complejidad temporal (O) mide el número de pasos que el algoritmo necesita para completarse en función del tamaño de la entrada.

En el caso de la recursión:

1. Número de llamadas recursivas: Cada vez que la función se llama a sí misma, requiere un paso adicional.
2. Operaciones adicionales: Las operaciones realizadas en cada llamada (por ejemplo, sumar, multiplicar, comparar).

8.2.1. Ejemplo: cálculo factorial

function factorial(n) {
    if (n === 0) return 1; // Caso base
    return n * factorial(n - 1); // Llamada recursiva
}

console.log(factorial(5)); // Salida: 120Lenguaje del código: JavaScript (javascript)

• Cada llamada reduce n en 1, por lo que hay n llamadas en total.
• Complejidad temporal: O(n) (el número de operaciones crece linealmente con el valor de n).
• Para calcular factorial(5), se realizan se realizan 16 pasos:
  • 6 comparaciones.
  • 5 multiplicaciones.
  • 5 llamadas recursivas.

8.3. Espacio (S): memoria utilizada

La complejidad espacial (S) mide cuánta memoria necesita el algoritmo durante su ejecución.

En una solución recursiva, el espacio está influenciado por:

1. Pila de llamadas: Cada llamada recursiva agrega un marco (frame) a la pila hasta que se alcanza el caso base.
2. Variables locales: Cada llamada puede almacenar datos como parámetros, variables locales y valores de retorno.

8.3.1. Ejemplo: cálculo factorial (continuación)

Siguiente el ejemplo del punto 8.2.1.,cuando ejecutamos factorial(5), se crean 6 marcos en la pila (uno por cada llamada desde factorial(5) hasta factorial(0)), por lo tanto:

• Complejidad espacial: También es O(n) (se almacenan n marcos en la pila).

8.4. Relación entre tiempo y espacio

• Más tiempo → más operaciones necesarias.
  • Por ejemplo, calcular un número de Fibonacci sin optimización hace muchas llamadas redundantes.
• Más espacio → más memoria usada.
  • Por ejemplo, la profundidad de la pila en una solución recursiva afecta directamente la memoria utilizada.

8.5. Comparación con una solución iterativa

8.5.1. Ejemplo iterativo: cálculo factorial

function factorialIterativo(n) {
    let resultado = 1;
    for (let i = 1; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

console.log(factorialIterativo(5)); // Salida: 120Lenguaje del código: JavaScript (javascript)

• Tiempo (O): También es O(n) porque el bucle se ejecuta n veces.
• Espacio (S): Es O(1) porque no utiliza pila de llamadas, solo una variable (resultado).

8.5.2. Conclusión entre comparación de solución iterativa y recursiva:

En ambo casos el tiempo son iguales a O(n) porque el número de pasos aumenta proporcionalmente al tamaño de la entrada.

La diferencias esta en el espacio (S), donde:

• Solución con Iteración: O(1) → Uso constante de memoria.
• Solución con Recursión: O(n) → Uso lineal de memoria porque guarda cada llamada.

¿Qué Significa O(1) en Espacio para Iteración?

Significa que:

1. Uso constante de memoria:
   • La cantidad de memoria utilizada no depende del tamaño de la entrada (n). Solo usa unas pocas variables que ocupan espacio fijo en la memoria, independientemente del valor de n.
2. En el caso del ejemplo con iteración:
   • Las únicas variables usadas son resultado y i.
   • No importa si n es 5 o 10,000; el uso de memoria sigue siendo constante.

¿Qué Significa O(n) en Espacio para Recursión?

Significa que:

1. Uso lineal de memoria:
   • La cantidad de memoria utilizada crece proporcionalmente al tamaño de la entrada (n). Esto se debe a que cada llamada recursiva se guarda en la pila de llamadas (call stack) hasta que se resuelve el caso base.
2. En el ejemplo con recursión:
   • Llamadas en la pila: factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0).
   • Hay 6 llamadas activas en la pila (una por cada valor de n)

Conclusión de esta diferencia en este ejemplo:

• La iteración es más eficiente en uso de memoria.
• La recursión puede ser más elegante, pero en problemas grandes puede consumir mucha memoria debido al crecimiento de la pila.

9. Herramientas que nos ayudan con la recursividad

La recursión puede ser difícil de visualizar al principio, ya que implica que las funciones se llaman a sí mismas y acumulan datos en la pila de llamadas. Por eso, es útil usar herramientas que nos permitan observar cómo funciona el flujo de ejecución.

Estas herramientas pueden ser:

1. Consola del navegador
2. Visualizadores como pythontutor.com
3. Comparación entre ambas herramientas
4. Resumen

9.1. Consola del navegador

La consola de desarrolladores de los navegadores es una herramienta poderosa para depurar y comprender cómo se ejecuta un código recursivo.

¿Cómo usarla para seguir la pila de llamadas?

Podemos usar estar dos estrategias:

9.1.1. Añadiendo console.log para ver la ejecución paso a paso

Puedes incluir mensajes en la consola para observar el comportamiento de la recursión.

Ejemplo: Factorial

function factorial(n) {
    console.log(`Entrando a factorial(${n})`); // Seguimiento de la llamada
    if (n === 0) {
        console.log(`Caso base alcanzado con factorial(${n})`);
        return 1; // Caso base
    }
    const resultado = n * factorial(n - 1); // Llamada recursiva
    console.log(`factorial(${n}) = ${resultado}`);
    return resultado;
}

console.log(factorial(5));Lenguaje del código: JavaScript (javascript)

Salida en la consola:

Entrando a factorial(5)
Entrando a factorial(4)
Entrando a factorial(3)
Entrando a factorial(2)
Entrando a factorial(1)
Entrando a factorial(0)
Caso base alcanzado con factorial(0)
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120

Explicación:

• Cada llamada se registra con console.log.
• Puedes ver cómo se alcanzan el caso base y los valores intermedios que se calculan al volver de cada llamada.

9.1.2. Usando el Depurador (Debugger):

Si pausas la ejecución con debugger, puedes inspeccionar cómo las llamadas se apilan.

Ejemplo con Depurador:

function factorial(n) {
    debugger; // Pausar aquí
    if (n === 0) return 1;
    return n * factorial(n - 1);
}

console.log(factorial(5));Lenguaje del código: JavaScript (javascript)

¿Cómo verlo?:

• En la pestaña Sources del navegador, puedes observar las llamadas que se acumulan en la pila.
• Cada vez que el código se detiene en debugger, verás las variables actuales y el estado del programa.

9.2. Visualizadores como pythontutor.com

PythonTutor es una herramienta en línea que permite ver paso a paso cómo se ejecuta un código JavaScript, incluyendo el seguimiento de la pila de llamadas y las variables en cada paso.

9.2.1. ¿Cómo usarlo?

1. Escribe Tu Código en el Editor
   • Copia y pega tu código recursivo en el editor de PythonTutor.
2. Ejecuta Paso a Paso
   • Presiona «Visualize Execution» y avanza paso a paso para ver cómo se comporta la recursión.

9.2.2. Ejemplo usando pythontutor.com

function factorial(n) {
    if (n === 0) return 1; // Caso base
    return n * factorial(n - 1); // Llamada recursiva
}

console.log(factorial(5));Lenguaje del código: JavaScript (javascript)

¿Qué verás?:

• Pila de Llamadas:
  • Cada vez que se llama a factorial, una nueva «caja» se agrega a la pila de llamadas.
    Cuando se resuelve una llamada, esa caja desaparece.
• Variables:
  • Puedes observar cómo cambia el valor de n en cada paso.

Ventaja:
Esta visualización te permite comprender cómo se resuelve la recursión y cómo la pila de llamadas se «desinfla» al final.

9.3. Comparación entre ambas herramientas

Herramienta	Uso	Ventajas
Consola del Navegador	Depurar en tiempo real con console.log o debugger.	No necesitas herramientas externas y puedes trabajar directamente en tu entorno de desarrollo.
PythonTutor	Visualizar paso a paso el flujo de ejecución, incluyendo pila de llamadas y variables.	Ideal para principiantes, ya que muestra gráficamente cómo se comporta la recursión.

9.4. Resumen

1. Consola del navegador: Ideal para observar directamente el comportamiento en tu entorno local con console.log y debugger.
2. PythonTutor: Excelente para principiantes que necesitan una representación gráfica detallada del flujo de ejecución.

Ambas herramientas son fundamentales para comprender cómo funciona la recursión y para depurar problemas como el stack overflow.

10. La recursión con JavaScript y WordPress.

1. ¿Se usa la recursión usualmente al diseñar una web con WordPress?
2. ¿Por qué no es tan común?

10.1. ¿Se usa la recursión usualmente al diseñar una web con WordPress?

En el desarrollo de sitios web, especialmente en WordPress, la recursión no es una técnica que se utilice comúnmente para las tareas típicas del desarrollo (como diseñar páginas, personalizar temas o agregar funcionalidad con plugins).

10.2. ¿Por qué no es tan común?

La recursión, aunque poderosa, puede no ser necesaria en muchas tareas comunes del desarrollo web debido a que:

• Desarrollo Con Herramientas de WordPress:
  WordPress ya tiene funciones y APIs para manejar menús, taxonomías y comentarios, por lo que rara vez necesitas implementar recursión manualmente.
• Simples Alternativas Existen:
  En muchos casos, las estructuras jerárquicas se pueden manejar con bucles o funciones iterativas, que son más eficientes en términos de uso de memoria.
• Desempeño y Pila de Llamadas:
  Si no se implementa correctamente, la recursión puede causar stack overflow, especialmente si se trabaja con una estructura de datos muy profunda.

11. Preguntas frecuentes y resumen sobre recursividad en JS.