Suggest an edit

Improve this article

Refine the answer for “Tasks solved with 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 often used for tasks where a large problem splits naturally into subtasks of the same kind.** Below are the most typical classes of such problems, with JavaScript examples.

## Theory

### TL;DR

- Math computations: factorial, Fibonacci numbers, exponentiation.
- Data structure traversal: trees (the DOM, a file system), graphs, DFS.
- Work with arrays: sum, search, filtering via "head plus tail".
- Divide and conquer algorithms: QuickSort, MergeSort, binary search, Tower of Hanoi.
- Processing nested structures: flattening an array, walking arbitrarily nested objects.
- Logic and combinatorial problems: permutations, a path through a maze, the knapsack.

### Quick example

```javascript
// Exponentiation by splitting the task
function pow(x, n) {
  if (n === 0) return 1;      // base case
  return x * pow(x, n - 1);   // recursive step
}

console.log(pow(2, 10)); // 1024
```

### Math computations

The classic case, because the formula is already stated recurrently.

- **Factorial of a number**: `n! = n * (n-1)!`
- **Fibonacci numbers**: `F(n) = F(n-1) + F(n-2)`
- **Exponentiation** by splitting the task:

```javascript
  function pow(x, n) {
    if (n === 0) return 1;
    return x * pow(x, n - 1);
  }
  ```

Here the recursive code repeats the mathematical notation almost word for word, which makes it easy to check by eye.

### Traversing data structures

A tree is made of subtrees, so traversing a tree is traversing each subtree.

- **Trees (the DOM or a file system, for example):**

```javascript
  function traverse(node) {
    console.log(node.value);
    node.children.forEach(traverse);
  }
  ```

- **Graphs**: depth-first search (DFS) is written recursively with almost no effort; breadth-first search (BFS) is usually implemented with a queue, because it goes level by level rather than deep.

For graphs you must remember the visited nodes in a `Set`, otherwise a cycle in the data loops the traversal forever.

### Arrays and nested structures

It is convenient to see an array as "the first element plus the rest of the array".

- Summing elements, searching, filtering:

```javascript
  function sum(arr) {
    if (arr.length === 0) return 0;
    return arr[0] + sum(arr.slice(1));
  }
  ```

- Flattening an array:

```javascript
  function flatten(arr) {
    return arr.reduce((acc, val) =>
      acc.concat(Array.isArray(val) ? flatten(val) : val), []);
  }
  ```

Nested structures of unknown depth are the strongest argument for recursion: a loop would have to maintain an explicit stack.

### Divide and conquer algorithms

The task is split into several smaller ones, each is solved by the same algorithm, and then the results are combined.

- **QuickSort**
- **MergeSort**
- **Binary search**
- **The Tower of Hanoi algorithm**

```javascript
function binarySearch(arr, target, lo = 0, hi = arr.length - 1) {
  if (lo > hi) return -1;                 // base case: nothing left
  const mid = (lo + hi) >> 1;
  if (arr[mid] === target) return mid;
  return arr[mid] < target
    ? binarySearch(arr, target, mid + 1, hi)
    : binarySearch(arr, target, lo, mid - 1);
}
```

### Logic and combinatorial problems

- Enumerating all combinations and permutations;
- finding a path through a maze;
- solving "weighted" problems such as the knapsack.

```javascript
function permutations(items) {
  if (items.length <= 1) return [items];          // base case
  return items.flatMap((item, i) => {
    const rest = [...items.slice(0, i), ...items.slice(i + 1)];
    return permutations(rest).map((p) => [item, ...p]);
  });
}

console.log(permutations(['a', 'b', 'c']).length); // 6
```

Recursion describes backtracking naturally here: make a choice, go deeper, come back and try the next one.

### Common mistakes

- **Recursion where a loop would do.** A linear pass over an array is simpler with a loop and has no stack depth limit.
- **`arr.slice(1)` on a large array.** Every call copies the tail, so instead of `O(n)` you get `O(n^2)` in both time and memory; pass an index instead.
- **A naive `fib` without memoisation.** `fib(n - 1) + fib(n - 2)` produces an exponential number of calls; a cache or a loop makes it linear.
- **Graph traversal without a visited set.** A cycle in the data turns the traversal into an infinite one.
- **Deep recursion over large data.** Walking a million elements crashes with `RangeError: Maximum call stack size exceeded` even when the logic is correct.
- **A forgotten base case in combinatorial problems.** Most often it is `items.length <= 1` or the empty branch of a tree.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.