Understanding Recursion: Concepts, Code Examples, Visualization, and Common Pitfalls

What Is Recursion?

The article starts with a cinema‑seat scenario to illustrate the recursive idea of asking the person in front for their row number, propagating the question forward until the first row is reached, then returning the answer back through the chain.

Recursion transforms a problem into a smaller instance of the same problem, solves the smallest case first, and then builds the solution back up.

Example: Array Sum

A simple recursive function sums an array by adding the first element to the sum of the rest until the array is empty.

function sum(arr) {
  // base case
  if (arr.length === 0) {
    return 0;
  }
  // recursive step
  return arr[0] + sum(arr.slice(1));
}

Visualising the Recursion Process

By adding a depth parameter and printing indented messages, the execution flow becomes clear.

function sum(arr, depth) {
  const indent = "--".repeat(depth);
  console.log(`${indent}Start Call: sum of [${arr}]`);
  if (arr.length === 0) {
    const res = 0;
    console.log(`${indent}Return: sum of [] is ${res}`);
    return res;
  }
  let res = sum(arr.slice(1), depth + 1);
  console.log(`${indent}After Call: sum of [${arr.slice(1)}], sum is ${res}`);
  res = arr[0] + res;
  console.log(`${indent}Return: sum of [${arr}] is ${res}`);
  return res;
}
sum([1,2,3,4], 0);

How to Write a Recursive Function

Two steps are required: identify the base case (the smallest problem) and formulate the recurrence relation that reduces the larger problem to a smaller one.

Example: Fibonacci Sequence

The nth Fibonacci number is defined as the sum of the two preceding numbers, with base cases f(1)=1 and f(2)=1.

function f(n) {
  if (n === 1) return 1;
  if (n === 2) return 1;
  return f(n - 1) + f(n - 2);
}

Drawbacks of Recursion

Stack overflow when recursion depth exceeds the call‑stack limit.

Excessive repeated calculations, especially in naïve Fibonacci implementations.

Stack overflow can be mitigated by limiting depth and throwing an error when the limit is exceeded.

let depth = 0;
function f(n) {
  ++depth;
  if (depth > 1000) throw Error('Recursion depth exceeded');
  if (n === 1) return 1;
  if (n === 2) return 1;
  return f(n-1) + f(n-2);
}

Repeated work can be avoided with memoisation using a hash table.

let memo = {};
function f(n) {
  if (n === 1) return 1;
  if (n === 2) return 1;
  if (memo[n]) return memo[n];
  const res = f(n-1) + f(n-2);
  memo[n] = res;
  return res;
}

Converting Recursion to Iteration

Recursive logic can be rewritten as loops that simulate the call stack.

// Iterative array sum
function sumIter(arr) {
  let res = 0;
  for (let i = 0; i < arr.length; i++) {
    res += arr[i];
  }
  return res;
}

// Iterative Fibonacci
function fibIter(n) {
  if (n === 1 || n === 2) return 1;
  let pre = 1, prepre = 1, res = 0;
  for (let i = 3; i <= n; i++) {
    res = pre + prepre;
    prepre = pre;
    pre = res;
  }
  return res;
}

While iteration removes function‑call overhead, it does not automatically solve the problem of repeated calculations for non‑linear recursions.