← Estructuras de datos desde cero · Lección 15/32
Una función que se llama a sí misma
Resolver un pedazo y delegar el resto
Una función recursiva se llama a sí misma con un problema más chico. Para que termine necesita dos cosas:
- Un caso base: el problema tan chico que se contesta sin llamarse otra vez.
- Un paso recursivo que se acerque al caso base en cada llamada.
La cuenta regresiva de abajo imprime n y le pide a otra copia de sí misma que siga desde n - 1. Cuando llega a 0, para.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
3, 2, 1 y el despegue: cuatro llamadas, y la última es la que ya no se llama a sí misma.
Toda la lección en una página
Resolver un pedazo y delegar el resto
Una función recursiva se llama a sí misma con un problema más chico. Para que termine necesita dos cosas:
- Un caso base: el problema tan chico que se contesta sin llamarse otra vez.
- Un paso recursivo que se acerque al caso base en cada llamada.
La cuenta regresiva de abajo imprime n y le pide a otra copia de sí misma que siga desde n - 1. Cuando llega a 0, para.
function cuentaRegresiva(n) {
if (n === 0) { // caso base
console.log("¡despegue!");
return;
}
console.log(n);
cuentaRegresiva(n - 1); // un problema más chico
}
cuentaRegresiva(3);
3, 2, 1 y el despegue: cuatro llamadas, y la última es la que ya no se llama a sí misma.
La pila de llamadas
Cada llamada que no ha terminado espera en la pila de llamadas, una pila de verdad (la de la unidad anterior): la última que entró es la primera que termina. factorial(3) no puede contestar hasta que factorial(2) conteste, y ésa espera a factorial(1).
Cuando la de hasta arriba llega al caso base, las respuestas bajan una por una y cada llamada termina su multiplicación. El programa imprime con sangría al entrar y al salir para que se vea la pila crecer y vaciarse.
function factorial(n, sangria = "") {
console.log(sangria + "entra factorial(" + n + ")");
let r;
if (n <= 1) r = 1; // caso base
else r = n * factorial(n - 1, sangria + " "); // espera la respuesta
console.log(sangria + "sale factorial(" + n + ") = " + r);
return r;
}
factorial(3);
Las tres entran en orden 3, 2, 1 y salen al revés, 1, 2, 3: eso es una pila. factorial(1) es la única que contesta sola; las otras multiplican lo que les regresan.
Sin caso base, se desborda
Si la función nunca llega a un caso base, la pila crece hasta que el lenguaje dice basta. En JavaScript eso es un RangeError: desbordamiento de pila (*stack overflow*). Pasa con el caso base olvidado, y también con uno que el paso recursivo nunca alcanza, como bajar de 2 en 2 esperando llegar a 1 desde un número par.
Por lo mismo, aunque esté bien escrita, una recursión de cientos de miles de niveles puede desbordarse: ahí conviene un ciclo.
function sinFin(n) {
return sinFin(n + 1); // nunca para
}
function deDosEnDos(n) {
if (n === 1) return "llegué";
return deDosEnDos(n - 2); // desde un par, se salta el 1
}
for (const prueba of [() => sinFin(0), () => deDosEnDos(7), () => deDosEnDos(8)]) {
try {
console.log(prueba());
} catch (e) {
console.log(e.name + ": " + e.message);
}
}
La primera y la tercera truenan con RangeError. Desde el 7 sí se llega al 1; desde el 8 se pasa de largo (8, 6, 4, 2, 0, −2…) y nunca para.
Fibonacci: cuando la recursión repite trabajo
Cada número de Fibonacci es la suma de los dos anteriores: 1, 1, 2, 3, 5, 8… Escrito tal cual, fib(n) llama a fib(n - 1) y a fib(n - 2), y cada una vuelve a abrirse en dos. El mismo fib(3) se calcula miles de veces y las llamadas crecen como O(2ⁿ).
La cura es memorizar: guardar en un Map lo ya calculado y devolverlo en vez de recalcular. Con eso cada fib(k) se calcula una sola vez: O(n). Es el mismo problema que «¿de cuántas formas subes una escalera de 1 en 1 o de 2 en 2?», el reto de abajo.
let llamadas = 0;
function fib(n) {
llamadas++;
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
let llamadasMemo = 0;
const memo = new Map();
function fibMemo(n) {
llamadasMemo++;
if (n <= 2) return 1;
if (memo.has(n)) return memo.get(n); // ya lo sabía
const r = fibMemo(n - 1) + fibMemo(n - 2);
memo.set(n, r);
return r;
}
for (const n of [10, 20, 25]) {
llamadas = 0;
const r = fib(n);
console.log("fib(" + n + ") =", r, "con", llamadas, "llamadas");
}
console.log("con memoria, fib(25) =", fibMemo(25), "con", llamadasMemo, "llamadas");
De fib(10) a fib(25) las llamadas pasan de 109 a 150 049. Con memoria, el mismo fib(25) sale en 47 llamadas.