JavaScript
Recursividad
Explica cómo diseñar funciones recursivas con caso base y progreso, recorrer árboles y evitar desbordamientos, ciclos o cálculos repetidos.
- Última actualización
- Actualizada
- Nivel
- Aplicación
- Fundamentos de programación
JavaScript
Explica cómo diseñar funciones recursivas con caso base y progreso, recorrer árboles y evitar desbordamientos, ciclos o cálculos repetidos.
La recursividad ocurre cuando una función resuelve un problema llamándose a sí misma con una versión más pequeña del mismo problema.
function countdown(number) {
if (number === 0) {
return;
}
console.log(number);
countdown(number - 1);
}
countdown(3);Resultado:
3
2
1Una función recursiva necesita:
function factorial(number) {
if (number === 0) {
return 1;
}
return number * factorial(number - 1);
}number === 0 es el caso base.factorial(number - 1) reduce el problema.Sin una de estas partes, la recursión puede no terminar.
factorial(3);Se expande conceptualmente así:
factorial(3)
3 * factorial(2)
3 * 2 * factorial(1)
3 * 2 * 1 * factorial(0)
3 * 2 * 1 * 1
6Las llamadas entran al Call Stack antes de que puedan calcularse los resultados finales.
function factorial(3)
function factorial(2)
function factorial(1)
function factorial(0)Cuando se alcanza el caso base, las llamadas terminan en orden inverso.
Esto explica por qué una recursión profunda puede producir:
RangeError: Maximum call stack size exceededfunction countdown(number) {
if (number === 0) {
return;
}
countdown(number);
}El argumento no cambia, así que nunca se acerca al caso base.
También puede avanzar en la dirección incorrecta:
countdown(number + 1);function factorial(number) {
if (!Number.isInteger(number) || number < 0) {
throw new RangeError("Number must be a non-negative integer");
}
if (number === 0) {
return 1;
}
return number * factorial(number - 1);
}Sin validación, datos como -1 nunca alcanzarían el caso base 0 mediante una resta continua.
La recursividad resulta natural cuando los datos también son recursivos.
const category = {
name: "Technology",
children: [
{
name: "Computers",
children: [
{ name: "Laptops", children: [] },
],
},
{
name: "Accessories",
children: [],
},
],
};Cada categoría puede contener otras categorías con la misma estructura.
function collectCategoryNames(category) {
const names = [category.name];
for (const child of category.children) {
names.push(...collectCategoryNames(child));
}
return names;
}function findNodeById(node, targetId) {
if (node.id === targetId) {
return node;
}
for (const child of node.children ?? []) {
const result = findNodeById(child, targetId);
if (result) {
return result;
}
}
return null;
}La función:
La función se llama a sí misma.
function isEven(number) {
if (number === 0) return true;
return isEven(number - 2);
}Dos o más funciones forman el ciclo.
function isEven(number) {
if (number === 0) return true;
return isOdd(number - 1);
}
function isOdd(number) {
if (number === 0) return false;
return isEven(number - 1);
}La recursión indirecta puede ser más difícil de reconocer y depurar.
Este factorial recursivo:
function factorial(number) {
if (number === 0) return 1;
return number * factorial(number - 1);
}Puede escribirse con un bucle:
function factorial(number) {
let result = 1;
for (let current = 2; current <= number; current++) {
result *= current;
}
return result;
}La versión iterativa:
La versión recursiva:
Una implementación recursiva ingenua de Fibonacci repite muchos cálculos.
function fibonacci(number) {
if (number <= 1) {
return number;
}
return fibonacci(number - 1) + fibonacci(number - 2);
}Para fibonacci(5), valores como fibonacci(3) se calculan varias veces.
Una caché puede evitar repeticiones:
function createFibonacci() {
const cache = new Map([[0, 0], [1, 1]]);
function fibonacci(number) {
if (cache.has(number)) {
return cache.get(number);
}
const value = fibonacci(number - 1) + fibonacci(number - 2);
cache.set(number, value);
return value;
}
return fibonacci;
}Esta técnica se llama memoización. Añade memoria para reducir trabajo repetido.
No debes asumir que una estructura recibida es pequeña o válida.
function countNodes(node, visited = new Set()) {
if (visited.has(node)) {
return 0;
}
visited.add(node);
let total = 1;
for (const child of node.children ?? []) {
total += countNodes(child, visited);
}
return total;
}visited evita un ciclo infinito si la estructura contiene referencias circulares.
Para estructuras muy profundas puede utilizarse una pila explícita.
function collectNames(root) {
const pending = [root];
const names = [];
while (pending.length > 0) {
const node = pending.pop();
names.push(node.name);
pending.push(...(node.children ?? []));
}
return names;
}Aquí el array pending representa el trabajo restante sin crear una llamada por nodo.
function calculateMenuCost(item) {
if (item.type === "product") {
return item.price;
}
return item.children.reduce(
(total, child) => total + calculateMenuCost(child),
0,
);
}La estructura puede contener productos o grupos con más elementos. La función aplica la misma regla a cada nivel.
¿Qué problema tiene esta función?
function sumTo(number) {
if (number === 0) {
return 0;
}
return number + sumTo(number);
}La llamada recursiva recibe el mismo número, por lo que nunca se acerca al caso base. Debe utilizar sumTo(number - 1) y validar valores negativos o no enteros según el contrato.
Funciones puras y efectos secundarios diferencia cálculos predecibles de operaciones que observan o modifican el mundo exterior.