Un algoritmo recursivo resuelve un problema reduciéndolo a instancias más pequeñas del mismo problema. Las recurrencias permiten describir cuántas llamadas, operaciones y recursos requiere esa estrategia.
La recursión es una técnica de programación en la que una función se llama a sí misma, directa o indirectamente. No es magia: cada llamada debe trabajar con un caso más pequeño y debe existir una situación simple que pueda resolverse sin hacer otra llamada.
Una recurrencia matemática describe la misma idea desde otro ángulo. Puede expresar el resultado de la función, la cantidad de llamadas o su tiempo de ejecución en función del tamaño de la entrada.
| Componente | Función | Ejemplo en factorial |
|---|---|---|
| Caso base | Detiene la recursión y devuelve un resultado conocido. | 0! = 1 |
| Caso recursivo | Reduce el problema y llama a la función. | n! = n · (n - 1)! |
| Medida de progreso | Debe disminuir hacia el caso base. | n pasa a n - 1 |
| Combinación | Integra el resultado de la llamada menor. | Multiplicar por n |
Si falta el caso base o la medida no disminuye correctamente, la función puede no terminar y agotar la pila de llamadas.
El factorial de un entero no negativo se define como n! = n · (n - 1)!, con 0! = 1. La definición matemática ya tiene estructura recursiva.
function factorial(n) {
if (!Number.isInteger(n) || n < 0) {
throw new Error("n debe ser un entero no negativo");
}
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(0)); // 1
console.log(factorial(5)); // 120La llamada factorial(5) espera el resultado de factorial(4), que espera el de factorial(3), hasta alcanzar el caso base.
Una misma función puede dar lugar a dos recurrencias distintas. Una describe el valor calculado; otra describe el trabajo realizado.
Es importante no confundir el tamaño numérico del resultado, que crece muy rápido, con el costo del algoritmo, que en este caso crece de forma lineal.
Un árbol de llamadas representa cada invocación recursiva como un nodo y cada llamada a un subproblema como una arista. Para factorial el árbol es una cadena, porque cada llamada genera una sola llamada menor.
Los algoritmos que generan dos o más subllamadas forman árboles ramificados. Analizar cuántos nodos hay en cada nivel ayuda a estimar su costo.
Para demostrar que una función recursiva termina, elegimos una medida de tamaño que sea un número natural no negativo. Cada llamada recursiva debe disminuir estrictamente esa medida y no debe poder descender indefinidamente.
Este argumento utiliza el principio del buen orden. También es la base de las pruebas de terminación de bucles.
La estructura de la prueba de corrección de una función recursiva suele coincidir con su código. Para factorial:
La demostración establece corrección para todas las entradas que cumplen la precondición, no solo para las que probamos manualmente.
La búsqueda binaria es recursiva porque, al no encontrar el valor central, busca en la mitad donde todavía podría estar el objetivo. La entrada se reduce aproximadamente a la mitad en cada llamada.
function busquedaBinaria(numeros, buscado, inicio = 0, fin = numeros.length - 1) {
if (inicio > fin) return -1;
const centro = Math.floor((inicio + fin) / 2);
if (numeros[centro] === buscado) return centro;
if (buscado < numeros[centro]) {
return busquedaBinaria(numeros, buscado, inicio, centro - 1);
}
return busquedaBinaria(numeros, buscado, centro + 1, fin);
}
const datos = [3, 8, 12, 17, 24, 31, 42];
console.log(busquedaBinaria(datos, 24)); // 4
console.log(busquedaBinaria(datos, 20)); // -1La precondición esencial es que el arreglo esté ordenado. Sin ella, descartar la mitad del arreglo no es válido.
Si T(n) representa el tiempo de búsqueda binaria sobre un segmento de n elementos, podemos escribir aproximadamente:
La diferencia frente a factorial es fundamental: factorial reduce n en una unidad, mientras que búsqueda binaria reduce n a la mitad. Esa diferencia cambia de crecimiento lineal a logarítmico.
Los algoritmos divide y vencerás dividen un problema grande en subproblemas más pequeños, resuelven cada uno recursivamente y combinan los resultados. Merge sort es un ejemplo clásico.
El número 2 indica que se resuelven dos subproblemas. El término de combinación cuenta el trabajo que se realiza fuera de las llamadas recursivas.
function merge(izquierda, derecha) {
const resultado = [];
let i = 0;
let j = 0;
while (i < izquierda.length && j < derecha.length) {
if (izquierda[i] <= derecha[j]) resultado.push(izquierda[i++]);
else resultado.push(derecha[j++]);
}
return resultado.concat(izquierda.slice(i), derecha.slice(j));
}
function mergeSort(numeros) {
if (numeros.length <= 1) return numeros;
const centro = Math.floor(numeros.length / 2);
const izquierda = mergeSort(numeros.slice(0, centro));
const derecha = mergeSort(numeros.slice(centro));
return merge(izquierda, derecha);
}
console.log(mergeSort([8, 3, 6, 1, 7, 2])); // [1, 2, 3, 6, 7, 8]El caso base es un arreglo de longitud 0 o 1, que ya está ordenado. Cada llamada recursiva usa un arreglo más corto, por lo que la función termina.
Si n es potencia de dos para simplificar, merge sort genera dos subproblemas de tamaño n/2 y combina todos los n elementos:
El análisis formal aparecerá en el tema siguiente. Por ahora importa reconocer que el árbol tiene varios niveles y que cada nivel procesa todos los elementos una vez al combinar.
La definición recursiva directa de Fibonacci es clara, pero ineficiente. Para calcular F(n) llama a F(n - 1) y F(n - 2), que a su vez repiten muchos subproblemas.
El árbol de llamadas se ramifica y contiene nodos repetidos. La recurrencia de costo es aproximadamente T(n) = T(n - 1) + T(n - 2) + c, que crece de forma exponencial.
let llamadas = 0;
function fibonacciRecursivo(n) {
llamadas++;
if (n <= 1) return n;
return fibonacciRecursivo(n - 1) + fibonacciRecursivo(n - 2);
}
const valor = fibonacciRecursivo(8);
console.log(`F(8) = ${valor}`); // F(8) = 21
console.log(`Llamadas realizadas: ${llamadas}`); // 67El valor calculado es correcto, pero el número de llamadas muestra el costo de repetir subproblemas. Para entradas mayores, esa repetición se vuelve muy costosa.
La memoización guarda los resultados de subproblemas ya resueltos. Cuando una llamada necesita el mismo subproblema, reutiliza el valor almacenado en lugar de calcularlo de nuevo.
function crearFibonacciMemoizado() {
const memo = new Map([[0, 0], [1, 1]]);
function fibonacci(n) {
if (memo.has(n)) return memo.get(n);
const valor = fibonacci(n - 1) + fibonacci(n - 2);
memo.set(n, valor);
return valor;
}
return fibonacci;
}
const fibonacci = crearFibonacciMemoizado();
console.log(fibonacci(40)); // 102334155Con memoización, cada valor desde 0 hasta n se calcula una sola vez. El tiempo pasa de exponencial a lineal y se usa memoria adicional para guardar resultados.
| Aspecto | Recursión | Iteración |
|---|---|---|
| Claridad | Suele reflejar definiciones jerárquicas. | Suele ser directa para procesos lineales. |
| Memoria | Usa pila de llamadas. | Puede usar pocas variables. |
| Riesgo | Profundidad excesiva de llamadas. | Errores de actualización o condición de salida. |
| Ejemplo natural | Árboles, divide y vencerás, backtracking. | Recorridos lineales y acumuladores. |
La elección no es solo de rendimiento. Una implementación recursiva puede expresar mejor la estructura del problema, mientras que una iterativa puede evitar costos de pila en procesos simples.
La recursión permite expresar soluciones mediante problemas más pequeños, y las recurrencias proporcionan el lenguaje para estudiar su costo. Comprender ambas ideas permite escribir funciones correctas y elegir cuándo una estrategia recursiva es eficiente.
En el próximo tema analizaremos con mayor precisión la complejidad de algoritmos mediante recurrencias.