Tasks solved with recursion

JavaScriptJunior~2 min read

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.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.