Suggest an edit

Improve this article

Refine the answer for “What is recursion?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

**Recursion** is a function that calls itself to break a problem into smaller versions of the same problem until it hits a base case it can solve directly.

## Theory

### TL;DR

- Think of Russian nesting dolls: open one, find a smaller one inside, repeat until you reach the tiniest doll that has nothing inside.
- Every recursive function needs two things: a **base case** (stop condition) and a **recursive call** (self-call with a smaller input).
- Use recursion for trees, graphs, and nested structures. Use a loop for flat data to avoid stack overflow.
- Node.js and browsers allow roughly 10,000 call stack frames before throwing `RangeError: Maximum call stack size exceeded`.

### Quick example

```javascript
function factorial(n) {
  if (n <= 1) return 1;        // base case: stop here
  return n * factorial(n - 1); // recursive call: smaller problem each time
}

console.log(factorial(5)); // 120
// Stack builds: factorial(5) -> 5 * factorial(4) -> ... -> 5 * 4 * 3 * 2 * 1
```

Each call adds a frame to the call stack. When `factorial(1)` hits the base case and returns `1`, the stack unwinds. Each frame multiplies its `n` by the result below, working back to `120`.

### How the call stack handles this

V8 (Chrome/Node.js) pushes every recursive call onto the call stack as a new execution context with its own local variables. The frames sit there waiting until the base case fires. Then values unwind upward through each frame in reverse order.

The default stack depth in Node.js is around 10,000 frames. Exceed that and you get `RangeError: Maximum call stack size exceeded`. This is why `factorial(100000)` crashes, and why using recursion on large flat arrays is a bad idea.

### When to use

- **Tree or graph traversal** (DOM, file system, component trees): the structure is nested, so recursion maps to it directly.
- **Parsing nested data** (JSON, HTML): each node can have children of the same shape.
- **Divide-and-conquer algorithms** (quicksort, merge sort): the problem halves with each call.
- **Large flat arrays**: use a loop instead. No nesting means no benefit, only stack risk.
- **Naive Fibonacci**: fine for demos, but time complexity is O(2^n). Add memoization before shipping anything real.

### Common mistakes

**No base case:**
```javascript
function bad(n) {
  return n * bad(n - 1); // no stopping condition
}
// RangeError: Maximum call stack size exceeded
```
Fix: add `if (n <= 1) return 1;` before the recursive call.

**Input not shrinking:**
```javascript
function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n); // n doesn't change, infinite loop
}
```
Passing `n` instead of `n - 1` is the most common mistake I've seen in code reviews. The function looks fine at a glance. Node.js only tells you something is wrong when the stack blows.

Fix: pass `n - 1`. Every call must move closer to the base case.

**Ignoring stack depth:**
`factorial(100000)` crashes in Node.js. If the input can be large, use an iterative approach. You can bump the stack size with `node --stack-size=65500`, but that is a workaround, not a fix.

### Real-world usage

- React Fiber walks the component tree recursively during rendering (the reconciler goes depth-first).
- Lodash `_.flattenDeep` recurses through nested arrays to fully flatten them.
- Node.js directory walking uses recursive patterns to traverse folder hierarchies.
- D3.js tree layouts recurse through node hierarchies to calculate visual positions.

### Follow-up questions

**Q:** Write `factorial` as an iterative function.
**A:** `function factIter(n, acc = 1) { if (n <= 1) return acc; return factIter(n - 1, acc * n); }`. This is tail-recursive in form, but V8 does not optimize tail calls, so the stack still grows.

**Q:** What is the time complexity of naive Fibonacci recursion?
**A:** O(2^n). Each call branches into two more calls, so the total number of calls doubles at every level. Fix it with memoization or a bottom-up loop.

**Q:** Does JavaScript support tail call optimization?
**A:** No. V8 does not perform tail call optimization in practice. Even a correctly structured tail call still adds a frame to the stack. Use a loop for deep recursion.

**Q:** What happens to a recursive call stack if the user switches browser tabs mid-execution?
**A:** JavaScript is single-threaded. The browser pauses execution when the tab loses focus and resumes it on return. Heavy recursion that blocks the main thread freezes the UI until the stack fully unwinds. For expensive operations, use `setTimeout` or Web Workers to avoid blocking.

## Examples

### Basic: sum all numbers in an array

```javascript
function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0;            // base case: past the last element
  return arr[index] + sumArray(arr, index + 1); // add current, recurse on the rest
}

console.log(sumArray([1, 2, 3, 4])); // 10
// Unwinds as: 1 + (2 + (3 + (4 + 0)))
```

The base case fires when `index` equals the array length. From there, each frame returns its element plus everything to the right.

### Intermediate: render a nested component tree

This is a simplified version of what React does when walking the component tree:

```javascript
function renderTree(node) {
  if (!node.children || node.children.length === 0) {
    return `<div>${node.text}</div>`; // base case: leaf node, no children
  }

let html = `<div>${node.text}`;
  node.children.forEach(child => {
    html += renderTree(child); // recurse into each child
  });
  return html + '</div>';
}

const tree = {
  text: 'App',
  children: [
    { text: 'Header', children: [] },
    { text: 'Main', children: [{ text: 'Article', children: [] }] }
  ]
};

console.log(renderTree(tree));
// <div>App<div>Header</div><div>Main<div>Article</div></div></div>
```

Iteration alone cannot handle arbitrary nesting depth cleanly. Recursion handles it in a few lines because the function does not need to know how deep the tree goes.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts962 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.