Recursión en PF

¿Qué es la recursión?

La recursión ocurre cuando una función se llama a sí misma para resolver un problema descomponiéndolo en subproblemas más pequeños. En programación funcional, la recursión se prefiere sobre los bucles porque evita mutaciones y funciona naturalmente con datos inmutables.

// Classic example: factorial
// 5! = 5 × 4 × 3 × 2 × 1 = 120

// Imperative with loop (mutates counter)
function factorialLoop(n) {
  let result = 1;
  for (let i = n; i > 1; i--) {
    result *= i;
  }
  return result;
}

// Recursive (no mutation)
function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}

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
// = 120

Patrones recursivos comunes

// Sum of array
const sum = arr => {
  if (arr.length === 0) return 0;          // Base case
  const [head, ...tail] = arr;
  return head + sum(tail);                  // Recursive case
};
sum([1, 2, 3, 4, 5]); // 15

// Find in array
const find = (arr, predicate) => {
  if (arr.length === 0) return undefined;
  const [head, ...tail] = arr;
  return predicate(head) ? head : find(tail, predicate);
};
find([1, 2, 3, 4], n => n > 2); // 3

// Map with recursion
const map = (arr, fn) => {
  if (arr.length === 0) return [];
  const [head, ...tail] = arr;
  return [fn(head), ...map(tail, fn)];
};
map([1, 2, 3], n => n * 2); // [2, 4, 6]

// Filter with recursion
const filter = (arr, pred) => {
  if (arr.length === 0) return [];
  const [head, ...tail] = arr;
  return pred(head) 
    ? [head, ...filter(tail, pred)]
    : filter(tail, pred);
};
filter([1, 2, 3, 4], n => n % 2 === 0); // [2, 4]

// Reduce with recursion
const reduce = (arr, fn, acc) => {
  if (arr.length === 0) return acc;
  const [head, ...tail] = arr;
  return reduce(tail, fn, fn(acc, head));
};
reduce([1, 2, 3, 4], (a, b) => a + b, 0); // 10

Recorrido de árboles

// Recursion shines with tree structures
const tree = {
  value: 1,
  children: [
    { value: 2, children: [
      { value: 4, children: [] },
      { value: 5, children: [] }
    ]},
    { value: 3, children: [
      { value: 6, children: [] }
    ]}
  ]
};

// Sum all values in tree
const sumTree = node => {
  const childSum = node.children.reduce(
    (sum, child) => sum + sumTree(child), 
    0
  );
  return node.value + childSum;
};
sumTree(tree); // 21

// Find in tree
const findInTree = (node, predicate) => {
  if (predicate(node)) return node;
  for (const child of node.children) {
    const found = findInTree(child, predicate);
    if (found) return found;
  }
  return null;
};
findInTree(tree, n => n.value === 5); // { value: 5, children: [] }

// Map over tree
const mapTree = (node, fn) => ({
  value: fn(node.value),
  children: node.children.map(child => mapTree(child, fn))
});
mapTree(tree, x => x * 10);
// All values multiplied by 10

// Flatten tree to array
const flatten = node => [
  node.value,
  ...node.children.flatMap(flatten)
];
flatten(tree); // [1, 2, 4, 5, 3, 6]

Optimización de llamadas en cola

La recursión normal acumula llamadas en la pila. La optimización de llamadas en cola (TCO) permite reutilizar el frame actual cuando la llamada recursiva es la última operación.

// NOT tail-recursive (operation after recursive call)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // Multiply AFTER recursive call
}

// Tail-recursive (recursive call is the last thing)
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // Nothing after
}

factorialTail(5);
// factorialTail(5, 1)
// factorialTail(4, 5)     // Reuse stack frame
// factorialTail(3, 20)    // Reuse stack frame
// factorialTail(2, 60)    // Reuse stack frame
// factorialTail(1, 120)   // Reuse stack frame
// 120

// Converting to tail-recursive
// Non-tail: sum uses result after recursive call
const sum = arr => {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
};

// Tail-recursive: use accumulator
const sumTail = (arr, acc = 0) => {
  if (arr.length === 0) return acc;
  return sumTail(arr.slice(1), acc + arr[0]);
};

// Note: TCO is only guaranteed in strict mode in Safari
// Other browsers may not implement it

Trampolining

Dado que la TCO no está ampliamente soportada, podemos usar trampolining para evitar desbordes de pila.

// Trampoline converts recursion to iteration
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

// Instead of calling itself, return a function to call
function sumRecursive(arr, acc = 0) {
  if (arr.length === 0) return acc;
  // Return a thunk (function) instead of recursing
  return () => sumRecursive(arr.slice(1), acc + arr[0]);
}

const sum = trampoline(sumRecursive);
sum([1, 2, 3, 4, 5]); // 15

// Works with large arrays that would overflow stack
const bigArray = Array.from({ length: 100000 }, (_, i) => i);
sum(bigArray); // 4999950000 (no stack overflow!)

Ejemplos recursivos del mundo real

// Deep clone object
const deepClone = obj => {
  if (obj === null || typeof obj !== 'object') return obj;
  if (Array.isArray(obj)) return obj.map(deepClone);
  return Object.fromEntries(
    Object.entries(obj).map(([k, v]) => [k, deepClone(v)])
  );
};

// Flatten nested arrays
const flattenDeep = arr => 
  arr.reduce((flat, item) =>
    flat.concat(Array.isArray(item) ? flattenDeep(item) : item),
    []
  );
flattenDeep([1, [2, [3, [4]]]]); // [1, 2, 3, 4]

// Get nested property safely
const getPath = (obj, path) => {
  if (path.length === 0) return obj;
  if (obj == null) return undefined;
  const [head, ...tail] = path;
  return getPath(obj[head], tail);
};
getPath({ a: { b: { c: 1 }}}, ['a', 'b', 'c']); // 1

// Fibonacci with memoization
const memoize = fn => {
  const cache = new Map();
  return n => {
    if (cache.has(n)) return cache.get(n);
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
};

const fib = memoize(n => 
  n <= 1 ? n : fib(n - 1) + fib(n - 2)
);
fib(50); // 12586269025 (instant with memoization)