Las dos partes de una función recursiva
Toda función recursiva tiene:
- Un caso base: una condición en la que devuelve un resultado sin volver a llamarse.
- 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)
Resuelto
Tú eres el motor: apila y desapila las llamadas de factorial(3) en el orden en que ocurren. No hace falta apilar console.log.
1function factorial(n) {2 if (n <= 1) return 1;3 return n * factorial(n - 1);4}5 6console.log(factorial(3));Tu pilacima
Movimiento 1 de 6
Autoevaluación: Funciones que se llaman a sí mismas
Resuelto
Elige una respuesta en cada pregunta.
¿Qué es el caso base de una función recursiva?
Cada llamada recursiva, ¿qué ocupa?
¿Qué error aparece cuando una recursión no termina?
¿Cuándo conviene la recursión en lugar de un bucle?
Ordena la salida: Bajar y subir
Resuelto
Hay un console.log antes de la llamada recursiva y otro después. Ordena lo que aparecería en la consola.
1function contar(n) {2 if (n === 0) return;3 console.log("baja", n);4 contar(n - 1);5 console.log("sube", n);6}7 8contar(2);Consola, de arriba abajo
- sube 1
- baja 2
- sube 2
- baja 1
Lo que está antes de la llamada recursiva se ejecuta al bajar: 2, después 1. Lo que está después se ejecuta al subir, cuando cada llamada retoma su trabajo pendiente, en orden inverso: primero termina la más profunda.
Detective: Un caso base que no alcanza
Resuelto
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 exceededPaso 1: toca la línea de código que causa el error.
Paso 2: ¿cómo lo arreglas?
Laboratorio: Potencias recursivas
Resuelto
Escribe potencia(base, exponente) usando recursión, sin bucles ni el operador **.
$ node programa.js
Lo que debe cumplir
- Imprime
8(pendiente) potencia(2, 10)da1024ypotencia(5, 0)da1(pendiente)- Es recursiva, sin
forniwhileni**(pendiente)
Una solución
1function potencia(base, exponente) {2 if (exponente === 0) return 1;3 return base * potencia(base, exponente - 1);4}5 6console.log(potencia(2, 3));potencia(2, 3) apila potencia(2, 2), potencia(2, 1) y potencia(2, 0), que es el caso base y devuelve 1. Al subir: 2 * 1 = 2, 2 * 2 = 4, 2 * 4 = 8. En la práctica usarías 2 ** 3, pero la forma recursiva es la base para recorrer estructuras anidadas.