What is recursion?

AlgorithmsJunior~3 min read

Short answer

Recursion is a way of solving problems in which a function calls itself until it reaches a base condition (the base), after which it "unwinds" back, assembling the result.

Key elements: a base case, a recursive step, guaranteed progress toward the base.
Suits problems with a natural hierarchy: trees, graphs, divide and conquer.

Detailed explanation

How a recursive function is structured

Base case: the stopping condition under which the answer is known immediately (without further calls).
Recursive step: reducing the problem to a subproblem of smaller size and calling the same function for that subproblem.
Progress toward the base: at each step we move closer to satisfying the base case (otherwise - infinite recursion).

Each recursive call is placed on the call stack. The recursion depth equals the stack height, equals extra memory O(depth). With too great a depth, a stack overflow is possible. The running time depends on the number of calls and the work done at each level (for example, O(n) for a simple linear reduction, O(2^n) for naive Fibonacci).

Example 1: factorial (recursion)

function factorial(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0 || n === 1) return 1; // base case
  return n * factorial(n - 1);      // recursive step
}

console.log(factorial(5)); // 120

Base: 0! = 1 and 1! = 1. Progress: we reduce n to n-1 at each step.

An iterative equivalent (the same thing without recursion)

function factorialIter(n) {
  if (n < 0) throw new Error('n must be >= 0');
  let res = 1;
  for (let i = 2; i <= n; i++) res *= i;
  return res;
}

console.log(factorialIter(5)); // 120

Where recursion is especially appropriate

Traversing trees and graphs (the DOM, an AST, file systems).
Divide and Conquer: quicksort/merge sort, binary search.
Dynamic programming (top-down with memoization).

Example 2: tree traversal (DFS)

const tree = {
  value: 1,
  children: [
    { value: 2, children: [ { value: 4, children: [] } ] },
    { value: 3, children: [] }
  ]
};

function dfs(node, visit) {
  if (!node) return; // base case: an empty node
  visit(node.value);
  for (const child of node.children) {
    dfs(child, visit); // recursive step
  }
}

dfs(tree, v => console.log(v)); // 1, 2, 4, 3

An iterative variant with an explicit stack:

function dfsIter(root, visit) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    visit(node.value);
    // Push the children in reverse order, so the left one is processed first
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

dfsIter(tree, v => console.log(v)); // 1, 2, 4, 3

Optimization: tail recursion

Tail recursion is when the recursive call is the last operation of the function. In theory this lets a compiler avoid growing the stack (tail call optimization), but most JS engines do not have TCO enabled, so it is not something to rely on for saving stack space in production.

function sumTo(n, acc = 0) {
  if (n === 0) return acc;        // base case
  return sumTo(n - 1, acc + n);    // tail call
}

console.log(sumTo(5)); // 15
// In JS this can still overflow the stack for large n.

Memoization: speeding up exponential recursion

Naively computing Fibonacci numbers with recursion gives exponential time because of repeated computations. Memoization reduces the complexity to O(n) time and O(n) memory.

const fib = (function () {
  const memo = new Map([[0, 0], [1, 1]]);
  return function f(n) {
    if (n < 0) throw new Error('n must be >= 0');
    if (memo.has(n)) return memo.get(n);
    const val = f(n - 1) + f(n - 2);
    memo.set(n, val);
    return val;
  };
})();

console.log(fib(10)); // 55

Advantages and disadvantages of recursion

Pros: simple and expressive code for hierarchical structures; a natural description of Divide and Conquer algorithms.
Cons: call overhead; risk of a stack overflow; sometimes harder to debug; without memoization, exponential repetition is possible.

Recursion vs iteration: how to choose

If the problem's structure is hierarchical (a tree/graph), recursion is often cleaner.
If the depth could be large, iteration (or an explicit stack) is preferable.
If performance matters, compare the call overhead against the benefit of readability and simplicity.

Frequent mistakes and how to avoid them

No base case, or it is unreachable - leads to infinite recursion and a stack overflow.
No progress toward the base (for example, forgetting to decrease n) - the same consequences.
Recomputing the same subproblems - use memoization or DP.

Interview tips

Immediately formulate the base case and progress toward it.
Assess time and memory: complexity in terms of stack depth.
Discuss edge cases (empty structures, n=0, n=1).
If needed, offer an iterative variant or memoization.

Short Answer

Interview ready

Premium

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