Recursión en JavaScript: el caso base que detiene las llamadas
En esta página
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
El post anterior sobre map, filter y reduce cerró señalando que la recursión hace crecer la pila de llamadas ya explicada en el post de Call Stack. Ese mismo post mostró un ejemplo, contarInfinito, que se llamaba a sí misma sin ninguna condición que la detuviera, y terminaba siempre en el mismo RangeError de desborde de pila. Una función recursiva necesita algo que ese ejemplo no tenía: una condición que decida cuándo dejar de llamarse a sí misma.
function cuentaRegresiva(n) {
if (n < 0) {
return;
}
console.log(n);
cuentaRegresiva(n - 1);
}
cuentaRegresiva(3);
// 3
// 2
// 1
// 0cuentaRegresiva se llama a sí misma con n - 1 cada vez, igual que contarInfinito. La diferencia está en las primeras tres líneas: si n es menor que 0, la función corta ahí con un return sin valor, sin llegar a imprimir nada ni a llamarse de nuevo. Esa condición es el caso base: el punto en el que la función deja de recurrir. Sin él, cuentaRegresiva se comportaría exactamente como contarInfinito, restando 1 para siempre y terminando en el mismo RangeError.
cuentaRegresiva(-1);
console.log("listo");
// listoSi el caso base ya se cumple desde la primera llamada, la función corta de inmediato: no imprime nada, no vuelve a llamarse, y el control sigue con la línea que sigue después. El caso base no es una excepción rara, es la condición que se evalúa siempre, en cada llamada, antes de decidir si hace falta seguir recurriendo.
function sumarHasta(n) {
if (n <= 0) {
return 0;
}
return n + sumarHasta(n - 1);
}
console.log(sumarHasta(4));
// 10cuentaRegresiva no devuelve nada útil: solo imprime. sumarHasta es distinta, devuelve un valor, y ese valor depende del resultado de la llamada siguiente. sumarHasta(4) no puede calcular su propio resultado sin conocer primero el de sumarHasta(3), que a su vez necesita el de sumarHasta(2), y así hasta llegar al caso base (sumarHasta(0), que devuelve 0 sin necesitar ninguna otra llamada). Recién ahí, con ese valor conocido, cada llamada pendiente puede terminar de sumar su propio n y devolver su resultado a quien la llamó.
function sumarHasta(n) {
if (n <= 0) {
return 0;
}
const resultado = n + sumarHasta(n - 1);
console.log(`sumarHasta(${n}) devuelve ${resultado}`);
return resultado;
}
sumarHasta(4);
// sumarHasta(1) devuelve 1
// sumarHasta(2) devuelve 3
// sumarHasta(3) devuelve 6
// sumarHasta(4) devuelve 10El orden de estos cuatro mensajes no es el orden en que se hicieron las llamadas: sumarHasta(4) fue la primera en llamarse, y sin embargo es la última en imprimir su resultado. Cada llamada se apila y queda en pausa en la línea const resultado = n + sumarHasta(n - 1), esperando el valor de la llamada siguiente antes de poder seguir. sumarHasta(1) es la primera que puede resolver sin esperar nada más (su llamada interna, sumarHasta(0), ya devolvió el caso base), así que es la primera en imprimir y en desapilarse. Recién entonces sumarHasta(2) tiene el valor que le faltaba para terminar la suma, imprimir el suyo y desapilarse también, y lo mismo en cadena hasta sumarHasta(4).
Es la misma lógica de pila que ya se vio con primero, segundo y tercero en el post de Call Stack, con una diferencia: ahí cada función terminaba con su propio console.log, sin depender de las demás. Acá cada llamada, salvo la del caso base, queda pausada dependiendo del resultado de la que sigue, y no puede desapilarse hasta tenerlo.
Una función recursiva se llama a sí misma. El caso base es la condición que decide cuándo dejar de hacerlo: sin él, la función se comporta como
contarInfinitoy termina en unRangeErrorde desborde de pila. Cuando la función devuelve un valor que depende de la llamada siguiente, cada llamada queda pausada en la pila hasta conocer ese valor, y se resuelve de adentro hacia afuera: primero la más cercana al caso base, última la primera que se llamó.
El próximo post trata el event loop: cómo JavaScript maneja tareas que no pueden resolverse de inmediato sin bloquear el resto del programa, combinando el call stack ya visto con una cola de tareas pendientes.