Saltar al contenido
Cómo se ejecuta JS por dentro

Recursión y stack overflow

Lección 6 de 712 min5 ejercicios

Una función recursiva es una función que se llama a sí misma. Parece un truco de magia, pero es una forma natural de resolver problemas que se repiten dentro de sí mismos, como recorrer carpetas dentro de carpetas. La clave para entenderla está en algo que ya conoces: la pila de llamadas.

Qué mirar en el pizarrón

La pila crece mientras la función se llama a sí misma y se vacía cuando llega al caso base. Fíjate en la gráfica de profundidad: sube, toca techo y baja. Esa forma de montaña es la recursión.

En el pizarrón

function factorial(n) {  if (n <= 1) return 1;  return n * factorial(n - 1);} console.log(factorial(3));

Pilacima

  1. factorial(3)n = 3
Consola(vacía)

factorial(3) entra a la pila. Como 3 no es ≤ 1, necesita calcular 3 * factorial(2).

Con el foco aquí también puedes avanzar y retroceder con las flechas del teclado.

Ver todos los pasos en texto
  1. Paso 1: factorial(3) entra a la pila. Como 3 no es ≤ 1, necesita calcular 3 * factorial(2). Pila: factorial(3).
  2. Paso 2: Para multiplicar, primero necesita el resultado de factorial(2), que se apila encima. factorial(3) queda en pausa, con la multiplicación a medio hacer. Pila: factorial(3) → factorial(2).
  3. Paso 3: Lo mismo: factorial(1) se apila. La pila crece una llamada por nivel. Pila: factorial(3) → factorial(2) → factorial(1).
  4. Paso 4: 1 se cumple: es el caso base. factorial(1) devuelve 1 sin volver a llamarse. Es lo que detiene la recursión. Pila: factorial(3) → factorial(2) → factorial(1).
  5. Paso 5: factorial(1) sale de la pila y su resultado vuelve a quien la llamó. factorial(2) retoma la multiplicación pendiente: 2 * 1 = 2. Pila: factorial(3) → factorial(2).
  6. Paso 6: factorial(2) devuelve 2 y sale. factorial(3) completa: 3 * 2 = 6. Pila: factorial(3).
  7. Paso 7: La pila queda vacía y se imprime 6. La recursión tiene dos fases: bajar, apilando llamadas hasta el caso base, y subir, resolviendo los resultados pendientes de arriba hacia abajo. Pila: vacía.

Las dos partes de una función recursiva

Toda función recursiva tiene:

  1. Un caso base: una condición en la que devuelve un resultado sin volver a llamarse.
  2. Un caso recursivo: se llama a sí misma con un problema más pequeño, que se acerca al caso base.
function cuentaAtras(n) {
  if (n === 0) {                // caso base
    console.log("¡Despegue!");
    return;
  }
  console.log(n);
  cuentaAtras(n - 1);           // caso recursivo: un problema más pequeño
}

cuentaAtras(3);

Si falta el caso base, o si el problema no se acerca a él, la función se llama para siempre.

Bajar y subir

Como muestra el pizarrón, cada llamada apila un marco nuevo, con sus propias variables. La recursión tiene dos fases:

  • Bajar: cada llamada deja trabajo pendiente y apila la siguiente, hasta llegar al caso base.
  • Subir: el caso base devuelve su resultado, y cada llamada pendiente lo usa para terminar, de arriba hacia abajo.

Lo que escribes antes de la llamada recursiva ocurre al bajar; lo que escribes después, al subir, en orden inverso. Lo vas a comprobar en el ejercicio “Ordena la salida”.

Stack overflow

La pila de llamadas tiene un tamaño máximo, del orden de miles de marcos según el motor. Si una recursión no termina, la pila se llena y el motor lanza:

RangeError: Maximum call stack size exceeded

Es el famoso stack overflow (desbordamiento de pila), el que viste con un pizarrón en el tema La pila de llamadas. Las causas casi siempre son dos: no hay caso base, o hay uno al que nunca se llega, por ejemplo uno que solo comprueba n === 0 cuando n puede ser negativo.

Recursión o bucle

Todo lo que hace una recursión se puede hacer con un bucle, y al revés. ¿Cuál elegir?

  • Para repetir algo N veces o recorrer una lista, un bucle es más simple y no tiene límite de profundidad.
  • Para estructuras anidadas (un árbol de carpetas, un menú con submenús, un JSON con niveles), la recursión refleja la forma de los datos y queda mucho más clara.
const carpeta = {
  nombre: "proyecto",
  hijos: [
    { nombre: "src", hijos: [{ nombre: "index.js", hijos: [] }] },
    { nombre: "README.md", hijos: [] },
  ],
};

function contarElementos(nodo) {
  let total = 1;
  for (const hijo of nodo.hijos) {
    total += contarElementos(hijo);  // cada hijo es una carpeta más pequeña
  }
  return total;
}

console.log(contarElementos(carpeta));  // 4

Resumen

  • Una función recursiva se llama a sí misma con un problema más pequeño.
  • Necesita un caso base alcanzable que devuelva sin volver a llamarse.
  • Cada llamada apila un marco: la recursión baja hasta el caso base y sube resolviendo lo pendiente.
  • Sin un caso base alcanzable: RangeError: Maximum call stack size exceeded.
  • Bucle para repetir; recursión para estructuras anidadas.

¡A practicar!

Tu progreso se guarda en este navegador.

Sé el motor: Apila las llamadas de factorial(3)

Tú eres el motor: apila y desapila las llamadas de factorial(3) en el orden en que ocurren. No hace falta apilar console.log.

function factorial(n) {  if (n <= 1) return 1;  return n * factorial(n - 1);} console.log(factorial(3));

Tu pilacima

    Movimiento 1 de 6

    Autoevaluación: Funciones que se llaman a sí mismas

    Elige una respuesta en cada pregunta.

    1. ¿Qué es el caso base de una función recursiva?

    2. Cada llamada recursiva, ¿qué ocupa?

    3. ¿Qué error aparece cuando una recursión no termina?

    4. ¿Cuándo conviene la recursión en lugar de un bucle?

    Ordena la salida: Bajar y subir

    Hay un console.log antes de la llamada recursiva y otro después. Ordena lo que aparecería en la consola.

    function contar(n) {  if (n === 0) return;  console.log("baja", n);  contar(n - 1);  console.log("sube", n);} contar(2);

    Consola, de arriba abajo

    1. sube 1
    2. baja 2
    3. sube 2
    4. baja 1

    Detective: Un caso base que no alcanza

    La función funciona con 3, pero con -1 desborda la pila. El error salta en una línea, pero el fallo está en otra. Encuéntrala.

    Consola

    6
    suma.js:3
      return n + sumaHasta(n - 1);
                 ^
    
    RangeError: Maximum call stack size exceeded

    Paso 1: toca la línea de código que causa el error.

    Laboratorio: Potencias recursivas

    Escribe potencia(base, exponente) usando recursión, sin bucles ni el operador **.

    programa.jsse ejecuta mientras escribes

    $ node programa.js

    (escribe tu código: se ejecuta solo)

    Lo que debe cumplir

    • Imprime 8 (pendiente)
    • potencia(2, 10) da 1024 y potencia(5, 0) da 1 (pendiente)
    • Es recursiva, sin for ni while ni ** (pendiente)

      domina-js · JavaScript en español, gratis y paso a paso.