L59 - Recursión

🧠 Concepto

Una función recursiva es aquella que se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños del mismo tipo. Toda función recursiva necesita dos elementos:

1. Caso base: condición que detiene la recursión.
2. Llamada recursiva: la función se invoca a sí misma con un argumento más pequeño o más simple.

💻 Estructura básica

function funcionRecursiva(parametro) {
  // Caso base
  if (condicionDeTerminacion) {
    return valorBase;
  }
  // Llamada recursiva
  return funcionRecursiva(parametroModificado);
}

Factorial (n!)

function factorial(n) {
  // Caso base
  if (n <= 1) return 1;
  // Llamada recursiva: n * factorial(n - 1)
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120 (5*4*3*2*1)

Traza de ejecución:

factorial(5)
  5 * factorial(4)
      4 * factorial(3)
          3 * factorial(2)
              2 * factorial(1)
                  return 1
              return 2 * 1 = 2
          return 3 * 2 = 6
      return 4 * 6 = 24
  return 5 * 24 = 120

💻 Fibonacci

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 8

⚠️ Problema: Fibonacci recursivo simple tiene O(2ⁿ) — extremadamente lento para n grandes. Para n=50, ¡haría billones de llamadas! (Lo solucionaremos en la lección de memoización).

🎯 Búsqueda en árbol (Deep find)

Uno de los casos más prácticos de recursión es buscar en estructuras anidadas de profundidad desconocida:

const arbol = {
  nombre: 'root',
  hijos: [
    {
      nombre: 'carpeta1',
      hijos: [
        { nombre: 'archivo1.txt', hijos: [] },
        { nombre: 'archivo2.txt', hijos: [] }
      ]
    },
    {
      nombre: 'carpeta2',
      hijos: [
        {
          nombre: 'subcarpeta',
          hijos: [
            { nombre: 'target.txt', hijos: [] }
          ]
        }
      ]
    }
  ]
};

function buscarNodo(arbol, nombreBuscado) {
  if (arbol.nombre === nombreBuscado) {
    return arbol;
  }
  for (const hijo of arbol.hijos) {
    const encontrado = buscarNodo(hijo, nombreBuscado);
    if (encontrado) return encontrado;
  }
  return null;
}

console.log(buscarNodo(arbol, 'target.txt')); // { nombre: 'target.txt', hijos: [] }

📝 Recursión vs Iteración

Aspecto	Recursión	Iteración
Legibilidad	Más natural para árboles, fractales, etc.	Más directa para secuencias lineales
Rendimiento	Puede ser más lenta (overhead de llamadas)	Generalmente más rápida
Memoria	Cada llamada ocupa stack → riesgo de stack overflow	Usa un único frame en el stack
Stack	Limitado (~10k en Chrome)	Ilimitado (memoria disponible)
Casos de uso	Árboles, JSON anidado, backtracking	Bucles simples, arrays, rangos

⚠️ Stack Overflow

Cada llamada recursiva se apila en el Call Stack. Si la recursión es muy profunda, se desborda:

function recursivaInfinita() {
  return recursivaInfinita();
}

recursivaInfinita(); // RangeError: Maximum call stack size exceeded

Límites típicos: ~10k en navegadores modernos, menos en Safari (~2k).

🧠 Tail Call Optimization (TCO)

Una llamada tail ocurre cuando la recursión es la última operación de la función. En ES6 se especificó que los motores deberían optimizar esto reutilizando el mismo stack frame.

// ❌ No es tail call (hay multiplicación después)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

// ✅ Tail call (la recursión es la última operación)
function factorialTail(n, acumulador = 1) {
  if (n <= 1) return acumulador;
  return factorialTail(n - 1, n * acumulador);
}

⚠️ Realidad: solo Safari/Swift implementa TCO de forma fiable. V8 (Chrome/Node) no lo implementa aún. No confíes en TCO para producción.

📝 Cuándo usar recursión

✅ Usar recursión cuando:

• La estructura es inherentemente recursiva (árboles, JSON, DOM).
• El problema se divide naturalmente en subproblemas (quick sort, merge sort).
• La profundidad es pequeña y conocida.

❌ Preferir iteración cuando:

• La profundidad puede ser grande (miles de niveles).
• El rendimiento es crítico.
• El caso base es un simple bucle.

// Alternativa iterativa para búsqueda en árbol (BFS con pila explícita)
function buscarIterativo(arbol, nombre) {
  const pila = [arbol];
  while (pila.length > 0) {
    const nodo = pila.pop();
    if (nodo.nombre === nombre) return nodo;
    pila.push(...nodo.hijos);
  }
  return null;
}

🎯 Regla de oro: usa recursión cuando haga el código más legible y la profundidad sea segura. Caso contrario, usa iteración.