Recursion & the Call Stack

Published by Brayan K

Some problems are easiest to solve by having a function call itself. Walking a folder tree, flattening nested arrays, or rendering nested comments are all naturally recursive. The trick that makes it work — and the thing that bites beginners — is the call stack.

Part of the free JavaScript course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Trace the smaller call and the work waiting for its result

A recursive function calls itself, directly or through another function. For the terminating examples here, identify the base case, the change that moves input toward it and the work that remains after the smaller call returns. A base-case line alone is not proof that execution reaches it.

function sumTo(n) {
  console.log("enter", n);
  if (n === 0) {
    console.log("base", n);
    return 0;
  }
  // This call must finish before the current addition can use its result.
  const smaller = sumTo(n - 1);
  const result = n + smaller;
  console.log("return", n, result);
  return result;
}
console.log("answer", sumTo(3));

// ✅ Expected output:
// enter 3
// enter 2
// enter 1
// enter 0
// base 0
// return 1 1
// return 2 3
// return 3 6
// answer 6

Each in-progress call keeps the state needed to continue after the nested call. Deep Dive into JavaScript Execution Context & Call Stack owns the broader execution-context model; this trace focuses on the recursive dependency.

A nested return does not automatically return from its caller

When the smaller call returns, the caller resumes at the call site. If the caller then reaches its end without a return, its own result is undefined, even if the deepest call returned a useful value.

function findBase(n) {
  if (n === 0) return "reached";
  findBase(n - 1);
}
console.log(findBase(0));
console.log(findBase(2));

// ✅ Expected output:
// reached
// undefined
function findBase(n) {
  if (n === 0) return "reached";
  return findBase(n - 1);
}
console.log(findBase(0));
console.log(findBase(2));

// ✅ Expected output:
// reached
// reached

When there is extra work, return the combined result as sumTo does. Functions owns ordinary return behaviour; recursion does not add an implicit return rule.

A reachable base case depends on the actual inputs and direction

The following function has a base case, but its recursive call moves away from that case for the supplied input. It exhausts the call stack. The panel records the error from the checked Node/Chromium engines; error wording and usable stack depth can differ in other engines.

function broken(n) {
  if (n === 0) return 0;
  return 1 + broken(n + 1);
}
broken(1);

// ✅ Expected error:
// RangeError: Maximum call stack size exceeded

Do not use a measured stack-overflow depth as a portable maximum. Fix the progress rule and the input contract, and use an iterative algorithm when nesting may be too deep. The example intentionally avoids printing a machine-dependent call count.

function totalTo(n) {
  if (!Number.isInteger(n) || n < 0 || n > 100) {
    throw new RangeError("n must be an integer from 0 to 100");
  }
  function visit(current) {
    if (current === 0) return 0;
    return current + visit(current - 1);
  }
  return visit(n);
}
console.log(totalTo(3), totalTo(0));
totalTo(0.5);

// ✅ Expected output:
// 6 0

// ✅ Expected error:
// RangeError: n must be an integer from 0 to 100

The upper bound is this small teaching function’s explicit input limit, not a claimed engine limit. An equality base case reached by integer decrements does not justify accepting arbitrary fractions or negative values. Numbers & Math owns numeric input predicates.

Local variables belong to calls; outside state can accumulate

A local binding created inside the function is separate for each call. A variable declared outside the function is shared by every invocation that closes over it. Repeatedly running a function can expose a shared accumulator that was never reset.

function visit(n) {
  const label = "level " + n;
  if (n > 0) visit(n - 1);
  console.log(label);
}
visit(2);

// ✅ Expected output:
// level 0
// level 1
// level 2
let total = 0;
function addDown(n) {
  if (n === 0) return;
  total += n;
  addDown(n - 1);
}
addDown(2);
console.log(total);
addDown(2);
console.log(total);

// ✅ Expected output:
// 3
// 6

Prefer returning the result when callers expect independent calculations. Scope & var/let/const (TDZ) owns binding visibility, and Closures and Scope owns retained shared state.

Nested data supplies the recursive structure

For a finite acyclic array tree of numbers, a number is a leaf and an array contains smaller subproblems. An empty array contributes zero. The function below returns a total without changing the input arrays. Its contract does not include cycles, arbitrary object records or unlimited nesting depth.

function nestedSum(value) {
  if (typeof value === "number") return value;
  if (!Array.isArray(value)) {
    throw new TypeError("Expected a number or an array");
  }
  let total = 0;
  for (const item of value) total += nestedSum(item);
  return total;
}
const data = [2, [3, [], [4]], 1];
console.log(nestedSum(data));
console.log(nestedSum([]));
console.log(JSON.stringify(data));

// ✅ Expected output:
// 10
// 0
// [2,[3,[],[4]],1]

An object can refer back to an ancestor, and then following children need not make progress. Do not describe this acyclic traversal as handling “any depth” or every JavaScript object. Deep Copy vs Shallow Copy & Data Structures owns broader reference and data-shape distinctions.

A loop can traverse nested data with an explicit work list

Tree-shaped input does not force you to use recursive calls. A loop can keep its own pending values. That trades call-stack depth for a data structure you manage; it still uses memory and still needs a policy for cyclic input.

function nestedSumIterative(input) {
  const pending = [input];
  let total = 0;
  while (pending.length > 0) {
    const value = pending.pop();
    if (typeof value === "number") {
      total += value;
    } else if (Array.isArray(value)) {
      for (const item of value) pending.push(item);
    } else {
      throw new TypeError("Expected a number or an array");
    }
  }
  return total;
}
console.log(nestedSumIterative([2, [3, [], [4]], 1]));
console.log(nestedSumIterative([]));

// ✅ Expected output:
// 10
// 0

This sum does not depend on leaf order. A traversal that emits ordered results would also need to choose its push order deliberately. Loops & Iteration owns the loop mechanics.

Repeated subproblems can dominate the work

A branching recursive definition can request the same smaller result many times. Counting calls on a fixed small input makes that repetition visible without relying on a stopwatch or a machine-specific benchmark.

let calls = 0;
function fib(n) {
  calls += 1;
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(6));
console.log("calls", calls);

// ✅ Expected output:
// 8
// calls 25
const cache = new Map();
let computed = 0;
function fib(n) {
  if (cache.has(n)) return cache.get(n);
  computed += 1;
  const result = n < 2 ? n : fib(n - 1) + fib(n - 2);
  cache.set(n, result);
  return result;
}
console.log(fib(6));
console.log("computed inputs", computed);

// ✅ Expected output:
// 8
// computed inputs 7

The cache changes the repeated-work pattern and uses extra storage. It is suitable here because the result depends only on the numeric input and does not change during the calculation. Map & Set owns the collection operations; Performance Optimization owns broader measurement and optimization decisions.

Complete the recursive call for a smaller branch

Count the number of non-array leaves in a finite acyclic nested array. An empty array has no leaves. Fill the recursive expression using the literal hint; the surrounding loop combines the results of the child branches.

function countLeaves(value) {
  if (!Array.isArray(value)) return 1;
  let count = 0;
  for (const child of value) {
    count += ___;
  }
  return count;
}
// 👉 replace ___ with countLeaves(child)
console.log(countLeaves([2, [3, [], [4]], 1]));
console.log(countLeaves([]));

// ✅ Expected output:
// 4
// 0

Total files in a small folder tree

Write totalBytes(node) for this explicit schema: a file has kind file and a nonnegative integer bytes value; a folder has kind folder and a children array. Reject an unknown kind with TypeError. Inputs otherwise satisfy the schema and form a finite acyclic tree of modest depth. A folder total is the sum of its children, and an empty folder contributes zero. Check a nested folder, an empty folder, a single file and an unknown kind.

function totalBytes(node) {
  if (node.kind === "file") return node.bytes;
  if (node.kind !== "folder") {
    throw new TypeError("Unknown node kind");
  }
  let total = 0;
  for (const child of node.children) {
    total += totalBytes(child);
  }
  return total;
}
const project = {
  kind: "folder",
  children: [
    { kind: "file", bytes: 120 },
    {
      kind: "folder",
      children: [
        { kind: "file", bytes: 80 },
        { kind: "folder", children: [] }
      ]
    }
  ]
};
console.log(totalBytes(project));
console.log(totalBytes({ kind: "folder", children: [] }));
console.log(totalBytes({ kind: "file", bytes: 7 }));
console.log(totalBytes(project));
try {
  totalBytes({ kind: "shortcut" });
} catch (error) {
  console.log(error.name + ": " + error.message);
}

// ✅ Expected output:
// 200
// 0
// 7
// 200
// TypeError: Unknown node kind

The repeated project call checks that the calculation does not retain a previous total. This is a model of a folder tree in memory, not a filesystem walk: real filesystems introduce permissions, links, errors and cycles that this schema does not represent.

References: MDN explains recursive functions, the call stack and excessive-recursion errors.

Practice quiz

What does this complete program print? function f(n) { if (n === 0) return "base"; f(n - 1); } console.log(f(2));

  • undefined
  • base
  • 2
  • 0

Answer: undefined. The outer calls do not return the recursive result, so the top-level result is undefined.

What does this complete program print? function visit(n) { if (n === 0) return; visit(n - 1); console.log(n); } visit(3);

  • 3 2 1
  • 1 2 3
  • 0 1 2 3
  • 3 2 1 0

Answer: 1 2 3. The logging runs while calls return, so the deeper call prints first.

What does this complete program print? function sum(n) { if (n === 0) return 0; return n + sum(n - 1); } console.log(sum(3), sum(0));

  • 3 0
  • 6 1
  • 6 0
  • 3 1

Answer: 6 0. Each caller adds its own value to the smaller result; the zero input returns directly.

What does this complete program print? function visit(n) { const saved = n; if (n > 0) visit(n - 1); console.log(saved); } visit(2);

  • 2 2 2
  • 2 1 0
  • 0 0 0
  • 0 1 2

Answer: 0 1 2. Each call has a separate saved binding, which is printed after its smaller call returns.

What does this complete program print? let total = 0; function add(n) { if (n === 0) return; total += n; add(n - 1); } add(2); add(2); console.log(total);

  • 6
  • 3
  • 2
  • 0

Answer: 6. The outside accumulator is reused across both top-level calls.

What does this complete program print? function count(value) { if (!Array.isArray(value)) return 1; let result = 0; for (const child of value) result += count(child); return result; } console.log(count([1, [], [2, 3]]));

  • 4
  • 3
  • 5
  • 2

Answer: 3. The empty array contributes no leaves; the three numeric leaves each contribute one.

What does this complete program print? let calls = 0; function visit(n) { calls++; if (n === 0) return; visit(n - 1); } visit(3); console.log(calls);

  • 3
  • 2
  • 4
  • 5

Answer: 4. The base-case call also runs, so it is included in the call count.

What does this complete program print? const pending = ["A17", "B24"]; while (pending.length) console.log(pending.pop());

  • A17 B24
  • A17
  • B24
  • B24 A17

Answer: B24 A17. An explicit last-in-first-out work list visits the most recently pushed value first.

Continue this course

Related lessons