Data Structure & Algorithms
Recursividad, call stack y casos base
Fundamentos de recursividad: contratos, casos base, medida decreciente, call stack, recursión estructural y conversión a iteración.
- Última actualización
- Actualizada
- Nivel
- Fundamentos
Data Structure & Algorithms
Fundamentos de recursividad: contratos, casos base, medida decreciente, call stack, recursión estructural y conversión a iteración.
Una función recursiva resuelve un problema llamándose con una versión más pequeña del mismo problema.
Para ser correcta necesita:
problema grande
↓ reducir
problema menor
↓ reducir
caso base
↑ devolver
combinar resultadosfunction factorial(n: number): number {
if (!Number.isInteger(n) || n < 0) {
throw new RangeError("n must be a non-negative integer");
}
if (n <= 1) return 1;
return n * factorial(n - 1);
}Modelo:
factorial(4)
= 4 × factorial(3)
= 4 × 3 × factorial(2)
= 4 × 3 × 2 × factorial(1)
= 24El argumento disminuye y está acotado por 1, por lo que termina.
Cada llamada crea un stack frame con:
factorial(4) espera 4 × ...
factorial(3) espera 3 × ...
factorial(2) espera 2 × ...
factorial(1) devuelve 1Después, los frames se resuelven en orden LIFO.
El call stack consume memoria. Una función recursiva de profundidad d suele usar O(d) de espacio adicional, aunque no cree arrays ni objetos explícitos.
Directa:
function countdown(n: number): void {
if (n < 0) return;
countdown(n - 1);
}Indirecta:
function isEven(n: number): boolean {
if (n === 0) return true;
return isOdd(n - 1);
}
function isOdd(n: number): boolean {
if (n === 0) return false;
return isEven(n - 1);
}La terminación debe analizarse a través del ciclo completo de llamadas, no por función aislada.
Una forma rigurosa de justificar terminación es definir una medida no negativa que disminuye en cada llamada:
n en factorial;remaining en una combinación de suma con valores positivos.Si la medida no disminuye o puede oscilar, existe riesgo de recursión infinita.
function sum(values: readonly number[], index = 0): number {
if (index === values.length) return 0;
return values[index] + sum(values, index + 1);
}O(n);O(n);Una versión que llama con values.slice(1) copia subarrays. El tiempo puede volverse O(n²) por las copias, aunque la relación recursiva parezca lineal.
Para diseñar una función recursiva, asume que la llamada pequeña ya funciona y define qué debe hacer la llamada actual.
Para sumar un árbol:
sumTree(node)devuelve la suma de todos los valores del subárbol cuya raíz esnode.
type Node = {
value: number;
left: Node | null;
right: Node | null;
};
function sumTree(node: Node | null): number {
if (!node) return 0;
return node.value + sumTree(node.left) + sumTree(node.right);
}No necesitas imaginar todo el stack simultáneamente. Confías en el contrato para los hijos y combinas sus respuestas.
Algunas estructuras ya son recursivas:
linked list = null o node + linked list
tree = null o node + subtrees
expression = literal o operator + expressionsLa función sigue la forma del dato. El caso base corresponde a la estructura vacía o atómica.
Ambas pueden expresar muchos procesos.
Ventajas:
Costos:
Ventajas:
Costos:
Elige por claridad, profundidad máxima y entorno de ejecución.
DFS recursivo:
function recursiveDfs(node: Node | null): void {
if (!node) return;
recursiveDfs(node.left);
recursiveDfs(node.right);
}Versión iterativa:
function iterativeDfs(root: Node | null): void {
if (!root) return;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop()!;
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
}El stack explícito almacena el trabajo pendiente que antes estaba en frames del runtime.
Una llamada es tail-recursive si es la última operación de la función.
function factorialTail(n: number, accumulator = 1): number {
if (n <= 1) return accumulator;
return factorialTail(n - 1, accumulator * n);
}En teoría, tail-call optimization puede reutilizar el frame. En la práctica, no debes asumir que los engines habituales de JavaScript eliminarán el crecimiento del stack. Para entradas grandes, usa iteración.
function collect(node: Node | null, result: number[]): void {
if (!node) return;
result.push(node.value);
collect(node.left, result);
collect(node.right, result);
}Aquí todas las llamadas comparten result. Puede ser eficiente, pero debes comprender cuándo se agrega y si hace falta deshacer cambios. En backtracking, la restauración es esencial; en un traversal acumulativo, no siempre.
Fibonacci ingenuo:
function fibonacci(n: number): number {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}Calcula los mismos estados muchas veces.
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ └─ fib(2)
└─ fib(3) ← repetidoEl tiempo es exponencial. Memoization guarda cada n y lo reduce a O(n) tiempo y O(n) memoria.
La recursión describe dependencias; no garantiza eficiencia.
Un árbol válido termina en null. Si una referencia accidental apunta a un ancestro, el traversal recursivo no termina.
En grafos debes usar visited. La estructura del dato determina si el caso base estructural es suficiente.
Son problemas distintos:
factorial(10000) puede desbordar el call stack;number;BigInt resuelve precisión entera, no profundidad recursiva.Valida ambos límites según el dominio.
No cuentes solo la profundidad. Pregunta:
Un árbol binario puede generar O(n) llamadas totales y profundidad O(h). Fibonacci genera un árbol exponencial aunque su profundidad sea solo O(n).
visited.Una función recursiva tiene profundidad O(log n). ¿Su tiempo también debe ser O(log n)?
No. Puede crear varias ramas por nivel. Merge sort tiene profundidad O(log n), pero procesa O(n) trabajo por nivel y tarda O(n log n).