Recursion Explained Without Fractals

The One-Sentence Definition

A recursive function is a function that calls itself with a smaller version of the problem until it hits a stopping condition.

That sentence has three pieces. Calls itself is what makes it recursive. Smaller version is what makes it terminate. Stopping condition is what stops the recursion when the smallest version is reached.

Skip any one of the three and you get an infinite loop, a stack overflow, or a function that does the same thing as a regular loop but worse.

The Smallest Useful Example

function factorial(n) {
  if (n <= 1) return 1;     // stopping condition
  return n * factorial(n - 1); // smaller version
}

factorial(4); // 24

Trace through factorial(4): it calls factorial(3) which calls factorial(2) which calls factorial(1) which returns 1. Then 2 * 1 = 2 returns. Then 3 * 2 = 6 returns. Then 4 * 6 = 24 returns.

The clearest way to understand this is to watch it. Our function call-stack visualizer has a recursion mode. Step through factorial(4) and the call/return dance becomes visible.

When Recursion Is the Right Tool

Three situations where recursion is genuinely cleaner than a loop:

1. Tree-shaped data. File systems, DOM trees, JSON structures.
2. Divide-and-conquer algorithms. Merge sort, quicksort, binary search.
3. Naturally self-similar problems. Fibonacci, factorial, towers of Hanoi.

Outside these three cases, prefer loops.

When Recursion Is Wrong

Three signs you are using recursion incorrectly:

1. Your recursive function loops over a flat array. Use a for-loop.
2. You hit Maximum call stack exceeded on real input sizes. The recursion is too deep.
3. Your recursive function recomputes the same subproblem many times. Add memoization or convert to iteration.

Tail Recursion

A recursive call is in tail position if it is the very last thing the function does. Some languages - Scheme, Scala, Elixir - optimize tail calls so they do not grow the stack. JavaScript engines mostly do not. Java does not. Python does not.

Practically: if you write deep recursion in JS or Python, expect a stack overflow around 10,000 to 50,000 calls. Convert to a loop with an explicit stack if you need to go deeper.

A Worked Tree-Walk

The most common real-world recursion is walking a tree:

function walk(node, visit) {
  visit(node);
  for (const child of node.children || []) {
    walk(child, visit);
  }
}

const tree = {
  name: "root",
  children: [
    { name: "a", children: [{ name: "a1" }, { name: "a2" }] },
    { name: "b" },
  ],
};

walk(tree, n => console.log(n.name));
// root, a, a1, a2, b

This is the shape of every JSON validator, every DOM operation, every file-system traversal you will ever write.

Where to Go Next

Read the functions concept page for the foundational mechanics. Once comfortable, the interview questions page has several recursion problems beginners get asked. Also: how to read other peoples code covers tree-walking in real codebases.

Memoization: Making Slow Recursion Fast

The naive recursive Fibonacci is famously slow because it recomputes the same subproblems. fib(40) takes seconds. fib(50) takes minutes. The fix is memoization - caching results of subproblems:

// Slow
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Fast (memoized)
const cache = {};
function fibMemo(n) {
  if (n in cache) return cache[n];
  if (n <= 1) return n;
  cache[n] = fibMemo(n - 1) + fibMemo(n - 2);
  return cache[n];
}

Memoization is a general technique that converts exponential recursive algorithms into linear ones. It is the gateway concept to dynamic programming, which dominates the harder LeetCode problems.

Converting Recursion to Iteration

Any recursive algorithm can be rewritten as an iterative one with an explicit stack. This is occasionally necessary in languages without tail-call optimization when you outgrow the call-stack limit:

// Recursive walk
function walk(node, visit) {
  visit(node);
  for (const child of node.children || []) walk(child, visit);
}

// Iterative version with explicit stack
function walkIter(root, visit) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    visit(node);
    for (const child of node.children || []) stack.push(child);
  }
}

The iterative version uses heap memory (the array) instead of stack memory, which scales much further. For million-node trees, the iterative version is the only one that works.

Recursion vs Loop: Quick Decision Guide

For more on choosing the right structure for your data, see our arrays vs objects post.

Frequently Asked Questions