Recursion versus Iteration

Thinking recursively, running safely

A recursive function solves a problem by calling itself on a smaller input until it reaches a base case that needs no further calls. Recursion fits naturally shaped data such as trees, nested comments and JSON. Each call usually adds a stack frame, so very deep recursion can overflow the call stack ("Maximum call stack size exceeded" in JavaScript, RecursionError in Python, whose default limit is about 1000 frames). A tail call is a call in final position; languages such as Scheme and Haskell-style runtimes can run tail recursion in constant stack. ES2015 specified proper tail calls, but most JavaScript engines, including V8 (Chrome, Node.js), do not implement them, and Python deliberately does not either, so for deep or unbounded input use a loop or an explicit stack.

Repeating and delaying work

Functional code often replaces loops with recursion, delays work until it is needed, and caches results of pure functions.

Recursion where it fits, a loop where depth is unbounded

Tree size recursively; list sum iteratively.

type Tree = { value: number; children: Tree[] };

// Natural recursion: depth equals tree depth, usually small
const sumTree = (t: Tree): number =>
  t.value + t.children.reduce((acc, c) => acc + sumTree(c), 0);

// Tail-recursive in form, but not optimised by most JS engines:
const sumTo = (n: number, acc = 0): number =>
  n === 0 ? acc : sumTo(n - 1, acc + n);   // base case: n === 0
// sumTo(1_000_000) may throw RangeError: Maximum call stack size exceeded

// Iterative version: constant stack
function sumToLoop(n: number): number {
  let acc = 0;
  for (let i = 1; i <= n; i++) acc += i;
  return acc;
}

Always write the base case first

Start every recursive function with the case that returns without recursing, and check that each recursive call moves strictly closer to it.

त्वरित जाँच: Why can deep recursion fail in Node.js even when written tail-recursively?

• Node.js forbids recursion
• V8 does not implement tail-call optimisation, so each call still uses a stack frame
• Tail calls are a syntax error
• Recursion is always slower than a network call