Recursion in FP

What is Recursion?

Recursion is when a function calls itself to solve a problem by breaking it into smaller subproblems. In functional programming, recursion is preferred over loops because it avoids mutation and works naturally with immutable data.

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

Common Recursive Patterns

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

Tree Traversal

// 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]

Tail Call Optimization

Normal recursion builds up a call stack. Tail call optimization (TCO) allows the engine to reuse the current stack frame when the recursive call is the last operation.

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

Since TCO isn't widely supported, we can use trampolining to avoid stack overflow.

// 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!)

Real-World Recursive Examples

// 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)