Recursividad

¿Qué es la Recursividad?

La recursividad es una técnica de programación fundamental donde una función se llama a sí misma para resolver un problema complejo dividiéndolo en subproblemas más pequeños pero estructuralmente idénticos. Es como resolver un rompecabezas gigante dividiéndolo en piezas más pequeñas del mismo tipo hasta llegar a piezas tan simples que puedas resolver directamente.

¿Para qué se utiliza la Recursividad?

La recursividad es utilizada por desarrolladores para:

Resolver problemas que tienen una estructura repetitiva o fractal.
Procesar estructuras de datos como árboles, listas enlazadas y grafos.
Implementar algoritmos matemáticos como factorial, Fibonacci y cálculos exponenciales.
Navegar sistemas de archivos y directorios anidados.
Implementar parsers y compiladores para lenguajes de programación.
Resolver problemas de divide y vencerás como quicksort y mergesort.

¿Cómo funciona?

La recursividad funciona como muñecas rusas (matrioshkas) - cada muñeca contiene una versión más pequeña de sí misma hasta llegar a la muñeca más pequeña que ya no se puede abrir. En programación, cada llamada recursiva resuelve una versión más pequeña del problema hasta llegar al “caso base” que se puede resolver directamente.

Anatomía de una función recursiva

Toda función recursiva debe tener dos elementos esenciales:

1. Caso Base (Condición de parada)

¿Qué es? La condición que detiene la recursión cuando el problema se vuelve lo suficientemente simple.

function factorial(n) {
  // CASO BASE: la recursión se detiene aquí
  if (n <= 1) {
    return 1; // El factorial de 0 y 1 es 1
  }

  // CASO RECURSIVO: la función se llama a sí misma
  return n * factorial(n - 1);
}

// Ejemplo de ejecución:
// factorial(5)
// = 5 * factorial(4)
// = 5 * (4 * factorial(3))
// = 5 * (4 * (3 * factorial(2)))
// = 5 * (4 * (3 * (2 * factorial(1))))
// = 5 * (4 * (3 * (2 * 1)))  ← caso base alcanzado
// = 5 * (4 * (3 * 2))
// = 5 * (4 * 6)
// = 5 * 24
// = 120

2. Caso Recursivo (Llamada a sí misma)

¿Qué es? La parte donde la función se llama a sí misma con un problema más pequeño.

function fibonacci(n) {
  // Casos base
  if (n <= 0) return 0;
  if (n === 1) return 1;

  // Caso recursivo: suma de los dos números anteriores
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Árbol de llamadas para fibonacci(5):
//                    fibonacci(5)
//                   /            \
//              fibonacci(4)    fibonacci(3)
//              /         \        /         \
//         fibonacci(3) fibonacci(2)  fibonacci(2) fibonacci(1)
//         /       \       /    \        /    \
//    fibonacci(2) fibonacci(1) fibonacci(1) fibonacci(0) fibonacci(1) fibonacci(0)
//    /       \
// fibonacci(1) fibonacci(0)

Ejemplos prácticos de recursividad

Navegación de estructuras de datos

// Recorrer un árbol binario
class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

function traverseTree(node) {
  // Caso base: nodo vacío
  if (!node) {
    return [];
  }

  // Caso recursivo: procesar nodo actual y sus hijos
  return [
    node.value, // Nodo actual
    ...traverseTree(node.left), // Subárbol izquierdo
    ...traverseTree(node.right), // Subárbol derecho
  ];
}

// Uso
const tree = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);

console.log(traverseTree(tree)); // [1, 2, 4, 5, 3, 6]

Procesamiento de arrays anidados

// Aplanar arrays multidimensionales
function flattenArray(arr) {
  const result = [];

  for (const element of arr) {
    if (Array.isArray(element)) {
      // Caso recursivo: elemento es array
      result.push(...flattenArray(element));
    } else {
      // Caso base: elemento no es array
      result.push(element);
    }
  }

  return result;
}

// Ejemplos
console.log(flattenArray([1, [2, 3], [4, [5, 6]]]));
// Resultado: [1, 2, 3, 4, 5, 6]

console.log(flattenArray([1, [2, [3, [4, [5]]]]]));
// Resultado: [1, 2, 3, 4, 5]

// Versión más concisa con reduce
function flattenRecursive(arr) {
  return arr.reduce((flat, item) => {
    return flat.concat(Array.isArray(item) ? flattenRecursive(item) : item);
  }, []);
}

Búsqueda en estructuras complejas

// Encontrar un valor en un objeto anidado
function findInObject(obj, searchValue, path = []) {
  // Caso base: valor encontrado
  if (obj === searchValue) {
    return path;
  }

  // Caso base: no es objeto
  if (typeof obj !== 'object' || obj === null) {
    return null;
  }

  // Caso recursivo: buscar en propiedades
  for (const [key, value] of Object.entries(obj)) {
    const result = findInObject(value, searchValue, [...path, key]);
    if (result) {
      return result; // Valor encontrado en esta rama
    }
  }

  return null; // Valor no encontrado
}

// Uso
const complexObject = {
  user: {
    profile: {
      settings: {
        theme: 'dark',
        notifications: {
          email: true,
          push: false,
        },
      },
    },
    posts: [
      { id: 1, title: 'Hello World' },
      { id: 2, title: 'Recursion Explained' },
    ],
  },
};

console.log(findInObject(complexObject, 'dark'));
// Resultado: ['user', 'profile', 'settings', 'theme']

console.log(findInObject(complexObject, 'Recursion Explained'));
// Resultado: ['user', 'posts', '1', 'title']

Algoritmos de ordenamiento recursivos

// Quick Sort - Divide y vencerás
function quickSort(arr) {
  // Caso base: array vacío o con un elemento
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  const equal = [];

  // Dividir array en tres partes
  for (const element of arr) {
    if (element < pivot) {
      left.push(element);
    } else if (element > pivot) {
      right.push(element);
    } else {
      equal.push(element);
    }
  }

  // Caso recursivo: ordenar partes y combinar
  return [
    ...quickSort(left), // Ordenar menores recursivamente
    ...equal, // Elementos iguales al pivot
    ...quickSort(right), // Ordenar mayores recursivamente
  ];
}

// Merge Sort - Más estable
function mergeSort(arr) {
  // Caso base
  if (arr.length <= 1) {
    return arr;
  }

  // Dividir en mitades
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Caso recursivo: ordenar mitades y combinar
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

// Prueba
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log('QuickSort:', quickSort(numbers));
console.log('MergeSort:', mergeSort(numbers));

Generación de estructuras fractales

// Generar un árbol fractal de directorios
function generateFileTree(depth, maxDepth = 3, baseName = 'folder') {
  // Caso base: profundidad máxima alcanzada
  if (depth >= maxDepth) {
    return {
      name: `${baseName}_${depth}`,
      type: 'file',
      size: Math.floor(Math.random() * 1000) + 100,
    };
  }

  // Caso recursivo: crear subdirectorios
  const children = [];
  const numChildren = Math.floor(Math.random() * 4) + 2; // 2-5 hijos

  for (let i = 0; i < numChildren; i++) {
    children.push(generateFileTree(depth + 1, maxDepth, `${baseName}_${depth}_${i}`));
  }

  return {
    name: `${baseName}_${depth}`,
    type: 'directory',
    children: children,
    totalSize: children.reduce((sum, child) => sum + (child.size || child.totalSize || 0), 0),
  };
}

// Uso
const fileSystem = generateFileTree(0, 4, 'project');
console.log(JSON.stringify(fileSystem, null, 2));

Recursividad con memoización (optimización)

// Fibonacci optimizado con memoización
function fibonacciMemoized() {
  const cache = new Map();

  function fibonacci(n) {
    // Verificar cache primero
    if (cache.has(n)) {
      return cache.get(n);
    }

    // Casos base
    if (n <= 0) return 0;
    if (n === 1) return 1;

    // Calcular y guardar en cache
    const result = fibonacci(n - 1) + fibonacci(n - 2);
    cache.set(n, result);

    return result;
  }

  return fibonacci;
}

// Comparación de rendimiento
const fibMemo = fibonacciMemoized();

console.time('Fibonacci sin memoización');
console.log('fibonacci(40):', fibonacci(40));
console.timeEnd('Fibonacci sin memoización');

console.time('Fibonacci con memoización');
console.log('fibMemo(40):', fibMemo(40));
console.timeEnd('Fibonacci con memoización');

// Resultado típico:
// Fibonacci sin memoización: ~1000ms
// Fibonacci con memoización: ~1ms

Recursión mutua (funciones que se llaman entre sí)

// Determinar si un número es par o impar usando recursión mutua
function isEven(n) {
  if (n === 0) return true; // Caso base
  return isOdd(n - 1); // Llamada a función hermana
}

function isOdd(n) {
  if (n === 0) return false; // Caso base
  return isEven(n - 1); // Llamada a función hermana
}

// Uso
console.log(isEven(10)); // true
console.log(isOdd(7)); // true

// Parser simple con recursión mutua
function parseExpression(tokens, pos = 0) {
  let result = parseTerm(tokens, pos);

  while (pos < tokens.length && (tokens[pos] === '+' || tokens[pos] === '-')) {
    const operator = tokens[pos++];
    const term = parseTerm(tokens, pos);
    result = operator === '+' ? result + term : result - term;
  }

  return result;
}

function parseTerm(tokens, pos) {
  let result = parseFactor(tokens, pos);

  while (pos < tokens.length && (tokens[pos] === '*' || tokens[pos] === '/')) {
    const operator = tokens[pos++];
    const factor = parseFactor(tokens, pos);
    result = operator === '*' ? result * factor : result / factor;
  }

  return result;
}

function parseFactor(tokens, pos) {
  if (tokens[pos] === '(') {
    pos++; // consumir '('
    const result = parseExpression(tokens, pos);
    pos++; // consumir ')'
    return result;
  }

  return parseInt(tokens[pos++]);
}

Problemas clásicos de recursividad

// Torre de Hanoi
function hanoi(n, source, destination, auxiliary) {
  const moves = [];

  function solve(disks, src, dest, aux) {
    if (disks === 1) {
      // Caso base: mover un disco
      moves.push(`Move disk from ${src} to ${dest}`);
      return;
    }

    // Caso recursivo:
    // 1. Mover n-1 discos a auxiliar
    solve(disks - 1, src, aux, dest);

    // 2. Mover disco más grande a destino
    moves.push(`Move disk from ${src} to ${dest}`);

    // 3. Mover n-1 discos de auxiliar a destino
    solve(disks - 1, aux, dest, src);
  }

  solve(n, source, destination, auxiliary);
  return moves;
}

// Resolver Torre de Hanoi con 3 discos
const solution = hanoi(3, 'A', 'C', 'B');
solution.forEach((move, index) => {
  console.log(`${index + 1}. ${move}`);
});

// Generar todas las permutaciones de un array
function generatePermutations(arr) {
  // Caso base: array vacío o con un elemento
  if (arr.length <= 1) {
    return [arr];
  }

  const permutations = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));

    // Caso recursivo: generar permutaciones del resto
    const subPermutations = generatePermutations(remaining);

    // Agregar elemento actual al inicio de cada permutación
    for (const perm of subPermutations) {
      permutations.push([current, ...perm]);
    }
  }

  return permutations;
}

// Uso
console.log(generatePermutations([1, 2, 3]));
// Resultado: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Recursividad en el mundo real: DOM y React

// Renderizado recursivo de componentes anidados
function renderComponent(component) {
  // Caso base: componente sin hijos
  if (!component.children || component.children.length === 0) {
    return `<${component.tag}>${component.text || ''}</${component.tag}>`;
  }

  // Caso recursivo: renderizar hijos
  const childrenHTML = component.children
    .map((child) => renderComponent(child)) // Llamada recursiva
    .join('');

  return `<${component.tag}>${childrenHTML}</${component.tag}>`;
}

// Estructura de componente
const app = {
  tag: 'div',
  children: [
    {
      tag: 'header',
      children: [
        { tag: 'h1', text: 'Mi App' },
        { tag: 'nav', text: 'Navegación' },
      ],
    },
    {
      tag: 'main',
      children: [
        {
          tag: 'article',
          children: [
            { tag: 'h2', text: 'Título del artículo' },
            { tag: 'p', text: 'Contenido del artículo...' },
          ],
        },
      ],
    },
  ],
};

console.log(renderComponent(app));
// Genera HTML anidado completo

// Búsqueda recursiva en el DOM
function findElementsWithClass(element, className) {
  const results = [];

  // Caso base: verificar elemento actual
  if (element.classList && element.classList.contains(className)) {
    results.push(element);
  }

  // Caso recursivo: buscar en hijos
  for (const child of element.children) {
    results.push(...findElementsWithClass(child, className));
  }

  return results;
}

// Uso en el navegador
// const elements = findElementsWithClass(document.body, 'highlight');

Detección y prevención de errores comunes

// Error común: Stack Overflow (sin caso base o caso base incorrecto)
function infiniteRecursion(n) {
  console.log(n);
  return infiniteRecursion(n + 1); // ¡Nunca se detiene!
}

// ¡NO EJECUTAR! Causará stack overflow

// Versión segura con límite
function safeRecursion(n, limit = 1000) {
  if (n >= limit) {
    console.log('Límite alcanzado');
    return;
  }

  console.log(n);
  return safeRecursion(n + 1, limit);
}

// Detectar recursión infinita con contador
function fibonacciSafe(n, depth = 0) {
  const MAX_DEPTH = 10000; // Límite de seguridad

  if (depth > MAX_DEPTH) {
    throw new Error(`Recursión demasiado profunda. Depth: ${depth}`);
  }

  if (n <= 0) return 0;
  if (n === 1) return 1;

  return fibonacciSafe(n - 1, depth + 1) + fibonacciSafe(n - 2, depth + 1);
}

// Convertir recursión a iteración (cuando sea necesario)
function fibonacciIterative(n) {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  let a = 0,
    b = 1;

  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b]; // Intercambio destructuring
  }

  return b;
}

// Comparación de rendimiento
console.time('Recursivo');
console.log('fibonacci(35) recursivo:', fibonacci(35));
console.timeEnd('Recursivo');

console.time('Iterativo');
console.log('fibonacci(35) iterativo:', fibonacciIterative(35));
console.timeEnd('Iterativo');

Técnicas avanzadas de recursividad

// Tail Call Optimization (optimización de llamada en cola)
// Nota: No todos los engines de JS soportan TCO completamente

function factorialTailRecursive(n, accumulator = 1) {
  // La llamada recursiva es la última operación
  if (n <= 1) {
    return accumulator;
  }

  // Tail call - no hay operaciones después de la llamada
  return factorialTailRecursive(n - 1, n * accumulator);
}

// Trampolining - evitar stack overflow en engines sin TCO
function trampoline(fn) {
  while (typeof fn === 'function') {
    fn = fn();
  }
  return fn;
}

function factorialTrampoline(n, acc = 1) {
  if (n <= 1) {
    return acc;
  }

  // Retornar función en lugar de llamar directamente
  return () => factorialTrampoline(n - 1, n * acc);
}

// Uso con trampoline
const result = trampoline(() => factorialTrampoline(10000));
console.log(
  'Factorial de 10000 (primeros 50 dígitos):',
  result.toString().substring(0, 50) + '...'
);

// Recursión con continuaciones
function fibonacciCPS(n, cont = (x) => x) {
  if (n <= 0) return cont(0);
  if (n === 1) return cont(1);

  return fibonacciCPS(n - 1, (a) => fibonacciCPS(n - 2, (b) => cont(a + b)));
}

// Uso
fibonacciCPS(10, (result) => console.log('Fibonacci CPS:', result));

Herramientas de debugging para recursión

// Visualizador de llamadas recursivas
function debugRecursion(fn, name = 'function') {
  let depth = 0;

  return function (...args) {
    const indent = '  '.repeat(depth);
    console.log(`${indent}→ ${name}(${args.join(', ')})`);

    depth++;
    const result = fn.apply(this, args);
    depth--;

    console.log(`${indent}← ${name} returns: ${result}`);
    return result;
  };
}

// Wrapper para debugging
const debugFactorial = debugRecursion(factorial, 'factorial');
console.log('\n=== Debug Factorial ===');
debugFactorial(5);

// Profiler de recursión
class RecursionProfiler {
  constructor() {
    this.stats = new Map();
  }

  profile(fn, name) {
    return (...args) => {
      const key = `${name}(${args.join(',')})`;

      if (!this.stats.has(key)) {
        this.stats.set(key, { calls: 0, totalTime: 0 });
      }

      const stats = this.stats.get(key);
      stats.calls++;

      const start = performance.now();
      const result = fn(...args);
      const end = performance.now();

      stats.totalTime += end - start;

      return result;
    };
  }

  getReport() {
    const report = [];

    for (const [key, stats] of this.stats.entries()) {
      report.push({
        function: key,
        calls: stats.calls,
        totalTime: stats.totalTime.toFixed(2) + 'ms',
        avgTime: (stats.totalTime / stats.calls).toFixed(2) + 'ms',
      });
    }

    return report.sort((a, b) => b.calls - a.calls);
  }
}

// Uso del profiler
const profiler = new RecursionProfiler();
const profiledFib = profiler.profile(fibonacci, 'fibonacci');

profiledFib(10);
console.table(profiler.getReport());

Cuándo usar y cuándo evitar recursión

// ✅ BUENOS casos para recursión:

// 1. Estructuras naturalmente recursivas
const processNestedComments = (comments) => {
  return comments.map((comment) => ({
    ...comment,
    replies: comment.replies ? processNestedComments(comment.replies) : [],
  }));
};

// 2. Algoritmos divide y vencerás
const binarySearch = (arr, target, left = 0, right = arr.length - 1) => {
  if (left > right) return -1;

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  return binarySearch(arr, target, mid + 1, right);
};

// 3. Backtracking
const solveMaze = (maze, x, y, path = []) => {
  // Casos base
  if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length) return false;
  if (maze[x][y] === 'wall' || maze[x][y] === 'visited') return false;
  if (maze[x][y] === 'exit') return [...path, [x, y]];

  // Marcar como visitado
  maze[x][y] = 'visited';

  // Probar todas las direcciones
  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];

  for (const [dx, dy] of directions) {
    const result = solveMaze(maze, x + dx, y + dy, [...path, [x, y]]);
    if (result) return result;
  }

  // Backtrack
  maze[x][y] = 'path';
  return false;
};

// ❌ MALOS casos para recursión:

// 1. Simple iteración (usar bucles)
// Malo:
function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0;
  return arr[index] + sumArrayRecursive(arr, index + 1);
}

// Bueno:
function sumArrayIterative(arr) {
  return arr.reduce((sum, num) => sum + num, 0);
}

// 2. Fibonacci sin memoización (exponencial)
// Malo para números grandes:
// fibonacci(40) // Muy lento

// Bueno:
const fibIterative = (n) => {
  if (n <= 1) return n;
  let a = 0,
    b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
};

Conclusión

La recursividad es una herramienta poderosa que puede hacer que problemas complejos se vuelvan elegantemente simples, pero debe usarse con sabiduría. Como un bisturí en manos de un cirujano, puede ser increíblemente precisa y efectiva cuando se usa correctamente, pero peligrosa si se aplica incorrectamente.

Principios clave para recursividad efectiva:

Siempre define un caso base claro - tu función debe saber cuándo parar
Asegúrate de progresar hacia el caso base - cada llamada debe acercarte a la solución
Considera la complejidad - algunos problemas recursivos son exponenciales sin optimización
Usa memoización cuando tengas subproblemas repetidos
Prefiere iteración para problemas simples de contador o acumulación

Cuándo brillan las soluciones recursivas:

Estructuras de datos anidadas (árboles, JSON, DOM)
Algoritmos divide y vencerás
Problemas con definición matemática recursiva
Backtracking y exploración de espacios de solución

Recuerda: La recursividad no es solo una técnica de programación - es una forma de pensar sobre problemas complejos. Te entrena para descomponer grandes desafíos en problemas más pequeños y manejables, una habilidad valiosa tanto en programación como en la vida.

La recursividad bien implementada es poesía en código - elegante, expresiva y poderosa. Pero como toda poesía, requiere práctica y comprensión profunda para dominarla.