Recursión y Pila
Exploraremos la recursividad, un concepto fundamental en la programación. Es especialmente útil en situaciones donde una tarea puede dividirse en sub-tareas más simples del mismo tipo. En términos más simples, cuando una función se llama a sí misma para resolver una parte del problema.
Enfoques de la Recursividad
Consideremos una función pow(x, n) que eleva x a la potencia n. Hay dos maneras de implementar esto:
Iterativa: Usando un bucle for
function pow(x, n) {
let result = 1;
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}
console.log(pow(2, 3)); // 8
Recursiva: Simplificando la tarea
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
console.log(pow(2, 3)); // 8
En el enfoque recursivo, cuando pow(x, n) se llama, se divide en dos ramas:
- Si
n == 1, el resultado esx. - Si
n != 1, el resultado esx * pow(x, n - 1).
La función se llama a sí misma recursivamente hasta que n es 1.
Comparación de Recursión e Iteración
La recursión a menudo resulta en un código más corto y fácil de leer. Sin embargo, tiene un límite en cuanto a la profundidad de recursión debido a las restricciones de memoria del motor JavaScript. Un enfoque iterativo puede ser más eficiente en términos de memoria.
Contexto de Ejecución y Pila
Cada llamada de función tiene un contexto de ejecución asociado, que incluye variables locales y el flujo de control. Cuando una función llama a otra, el contexto de la función actual se guarda en la pila de contexto de ejecución.
Ejemplo de pow(2, 3)
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
console.log(pow(2, 3));
Durante la ejecución:
pow(2, 3)llama apow(2, 2).pow(2, 2)llama apow(2, 1).pow(2, 1)devuelve 2, lo que permite apow(2, 2)devolver 4.- Finalmente,
pow(2, 3)devuelve 8.
Cada llamada recursiva añade un nuevo contexto a la pila, y la profundidad de la recursión determina el número máximo de contextos en la pila.
Comparación de Memoria
El enfoque iterativo usa menos memoria, ya que sólo necesita un contexto de ejecución, mientras que el recursivo necesita un contexto para cada llamada.
Recorridos Recursivos
La recursión es útil para recorrer estructuras de datos complejas, como la estructura de una empresa:
let company = {
sales: [{ name: 'John', salary: 1000 }, { name: 'Alice', salary: 1600 }],
development: {
sites: [{ name: 'Peter', salary: 2000 }, { name: 'Alex', salary: 1800 }],
internals: [{ name: 'Jack', salary: 1300 }]
}
};
function sumSalaries(department) {
if (Array.isArray(department)) {
return department.reduce((prev, current) => prev + current.salary, 0);
} else {
let sum = 0;
for (let subdep of Object.values(department)) {
sum += sumSalaries(subdep);
}
return sum;
}
}
console.log(sumSalaries(company)); // 7700
Este código suma los salarios de todos los empleados, recorriendo recursivamente los subdepartamentos.
Estructuras Recursivas
Listas Enlazadas
Una lista enlazada se define recursivamente como un objeto con un valor y una referencia al siguiente objeto:
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
Esta estructura permite operaciones eficientes de inserción y eliminación, aunque no es tan rápida para acceder a elementos por índice como un array.
Conclusión
La recursividad es una herramienta poderosa en la programación que permite resolver problemas complejos de manera elegante. Si bien puede tener limitaciones en cuanto a la memoria y la profundidad de recursión, su capacidad para simplificar el código y hacerlo más mantenible es invaluable.
