Recursion and stack

Time to look at functions from a deeper angle. The first idea worth slowing down for is recursion.

If you have written code for a while, you have probably met it already, and you could skim this chapter. If not, it is one of those tools that reshapes how you break problems apart.

Recursion pays off when a task naturally divides into smaller tasks of the same shape. Sometimes that means “do one easy step, then solve a slightly smaller version of the same problem.” Other times the data itself is nested in a self-similar way, and you want code that mirrors that shape. Either pattern is a signal that recursion might be the clean solution.

A running function can call other functions. The special case where a function calls itself is recursion. Nothing more exotic than that — the surprise is how much you can build from it.

Two ways of thinking

Start with something plain: a function repeatStr(str, n) that builds a string by gluing str to itself n times.

repeatStr("ab", 2) = "abab"
repeatStr("ab", 3) = "ababab"
repeatStr("ab", 4) = "abababab"

There are two natural ways to write it, and the difference between them is the whole point of this section.

1. Iterative thinking — a for loop. Keep a running string and append n times:

function repeatStr(str, n) {
  let result = "";

  // append str to result, n times
  for (let i = 0; i < n; i++) {
    result += str;
  }

  return result;
}

alert( repeatStr("ab", 3) ); // ababab

2. Recursive thinking — shrink the task, then call yourself. Peel off one copy of str and hand the rest to another call of repeatStr:

function repeatStr(str, n) {
  if (n == 1) {
    return str;
  } else {
    return str + repeatStr(str, n - 1);
  }
}

alert( repeatStr("ab", 3) ); // ababab

The recursive version works on a different principle. Every call to repeatStr(str, n) makes a decision, and the code forks into two branches:

1. If n == 1, the answer is immediate: repeatStr(str, 1) is just str. This branch is the base of recursion — the case that stops the process instead of spawning more work. Every recursion needs at least one, or it never ends.
2. Otherwise, rewrite repeatStr(str, n) as str + repeatStr(str, n - 1): one copy of str glued to the result of the same function with a lower n. This is the recursive step: split the job into one cheap action (a single concatenation) plus a smaller instance of the same job (repeatStr with a lower n). Each step shaves n down, until it hits 1.

So repeatStr keeps calling itself, with smaller n each time, until it reaches the base case.

Trace repeatStr("ab", 4) and the shrinking is easy to follow:

Each call is reduced to something simpler, then simpler again, until the answer is obvious. Then those obvious answers concatenate back up the chain: "ab", then "abab", then "ababab", then "abababab".

The greatest number of nested calls in flight at once — counting the very first one — is the recursion depth. For repeatStr(str, n) the depth is exactly n.

Depth matters because the engine caps it. You can safely count on around 10000 nested calls; some engines allow more, but 100000 is beyond most of them. Push past the limit and you get a RangeError: Maximum call stack size exceeded. There is an optimization called tail-call optimization that can flatten certain recursive calls so they use no extra depth, but engine support is spotty and it only kicks in for narrow cases, so don’t lean on it.

That ceiling limits where deep recursion is safe, yet the range of useful cases stays wide. For plenty of problems, thinking recursively yields code that is shorter and easier to maintain.

Try the recursive repeatStr yourself. Change str and n, then watch both the answer and the chain of calls that produced it — the depth of that chain is exactly n.

<div class="row">
<label>str <input id="s" type="text" value="ab"></label>
<label>n <input id="n" type="number" value="5" min="1" max="20"></label>
<button id="go">Compute</button>
</div>
<div id="out"></div>
<pre id="trace"></pre>

.row { display:flex; gap:12px; align-items:center; flex-wrap:wrap; margin-bottom:12px; }
label { display:flex; gap:6px; align-items:center; }
input { width:96px; padding:4px 6px; }
button { padding:5px 12px; cursor:pointer; }
#out { font-weight:600; margin-bottom:8px; }
pre { background:#f4f4f5; padding:10px 12px; border-radius:6px; font-size:13px; line-height:1.5; overflow-x:auto; }

const $ = id => document.getElementById(id);

function repeatStr(str, n) {
if (n === 1) return str;             // base case
return str + repeatStr(str, n - 1);  // recursive step
}

function run() {
const str = $('s').value || 'ab';
const n = Math.max(1, Math.min(20, Number($('n').value)));
$('out').textContent = 'repeatStr("' + str + '", ' + n + ') = "' + repeatStr(str, n) + '"';

const lines = [];
for (let k = n; k >= 1; k--) {
  const rhs = k === 1 ? '"' + str + '"' : '"' + str + '" + repeatStr("' + str + '", ' + (k - 1) + ')';
  lines.push('repeatStr("' + str + '", ' + k + ') = ' + rhs);
}
lines.push('recursion depth = ' + n);
$('trace').textContent = lines.join('\n');
}

$('go').addEventListener('click', run);
run();

The execution context and stack

To see why recursion has a depth limit and a memory cost, you have to look at what the engine tracks while a function runs.

The state of a running function lives in its execution context — an internal record the engine keeps for each call. It holds where control currently is, the local variables, the value of this (unused here), and a handful of other internal fields.

One call means one execution context. Always.

When a function makes a nested call, four things happen in order:

• The current function pauses.
• Its execution context is saved onto a structure called the execution context stack (the “call stack”).
• The nested call runs to completion, in its own fresh context.
• The saved context is popped back off the stack, and the outer function picks up exactly where it left off.

Walk through repeatStr("ab", 3) and watch the stack grow and shrink.

repeatStr(“ab”, 3)

At the start of repeatStr("ab", 3), the context holds str = "ab", n = 3, with control at line 1 of the function body.

The condition n == 1 is false, so control moves into the else branch:

function repeatStr(str, n) {
  if (n == 1) {
    return str;
  } else {
    return str + repeatStr(str, n - 1);
  }
}

alert( repeatStr("ab", 3) );

Same variables, new position — control is now at line 5, about to evaluate str + repeatStr(str, n - 1). That inner repeatStr(str, n - 1) is repeatStr("ab", 2), and it has to run before the concatenation can happen.

repeatStr(“ab”, 2)

To run the nested call, the engine parks the current context on the stack. It happens to be the same function, but that is irrelevant — the mechanism is identical for any function call:

1. The current context is remembered on top of the stack.
2. A brand-new context is created for the subcall.
3. When the subcall finishes, the parked context is popped and resumes.

After entering repeatStr("ab", 2), the stack holds two frames:

The top frame is the one currently executing; frames below it are paused, each remembering its own variables and its exact resume point. That is why returning is effortless — everything the outer call needs was saved.

repeatStr(“ab”, 1)

Same story one level deeper. Line 5 fires another subcall, this time repeatStr("ab", 1). A new context is created and pushed on top:

Two old contexts wait; one runs for repeatStr("ab", 1).

The exit

Inside repeatStr("ab", 1), the condition n == 1 is finally true, so the first branch runs:

function repeatStr(str, n) {
  if (n == 1) {
    return str;
  } else {
    return str + repeatStr(str, n - 1);
  }
}

No further calls. The function returns "ab". Its context is done, so it is discarded, and the frame beneath it comes back to life:

repeatStr("ab", 2) now has its subcall result ("ab"), so it finishes str + repeatStr(str, n - 1) = "ab" + "ab" = "abab" and returns. The last frame is restored:

repeatStr("ab", 3) computes "ab" + "abab" = "ababab" and returns it. Final answer: repeatStr("ab", 3) = "ababab".

The recursion depth here was 3. As the diagrams show, recursion depth equals the maximum number of contexts that pile up on the stack at once.

That is the memory cost. Each context occupies memory. Building the string this way needs memory for n contexts simultaneously, one for every value from n down to 1.

The loop version does not have that problem:

function repeatStr(str, n) {
  let result = "";

  for (let i = 0; i < n; i++) {
    result += str;
  }

  return result;
}

The iterative repeatStr reuses a single context, mutating i and result as it goes. Its memory footprint is small, fixed, and independent of n.

But “can be” is not “should be.” Rewriting is sometimes fiddly — especially when a function fires different subcalls depending on conditions and then merges their results, or when the branching is genuinely tree-shaped. In those cases the flattening is real work, and the memory win may not be worth it.

Recursion often buys you code that is shorter and easier to read and maintain. Most of the time you want clear code more than you want a micro-optimization, which is exactly why recursion earns its place.

Recursive traversals

Recursion truly shines when the data is nested. Consider a music festival represented as an object:

let festival = {
  main: [{
    name: 'Maya',
    fee: 1000
  }, {
    name: 'Nadia',
    fee: 1600
  }],

  fringe: {
    tent: [{
      name: 'Raj',
      fee: 2000
    }, {
      name: 'Theo',
      fee: 1800
    }],

    busking: [{
      name: 'Arjun',
      fee: 1300
    }]
  }
};

A festival has stages, and a stage can take one of two forms:

• It holds an array of acts. The main stage, for instance, is two acts: Maya and Nadia.
• Or it holds substages. fringe splits into tent and busking, each with its own acts.
• And a substage can split further as it grows. tent might one day divide into tentA and tentB slots, which could split again. Not shown here, but the structure allows it to any depth.

Now suppose you want the total of all fees. How?

An iterative approach fights the shape of the data. You could loop over festival, then nest a loop over first-level stages, then nest another loop for the acts inside second-level stages like tent, then another for any third level that appears later… Each new level of nesting demands another loop, and after three or four the code is a tangle. Worse, it only works up to the depth you hard-coded.

Recursion sidesteps all of that. When the function receives a stage, there are exactly two cases:

1. It is a plain stage — an array of acts. Sum their fees in one loop. This is the base case.
2. It is an object with N substages. Make N recursive calls, one per substage, and add up what they return. This is the recursive step — a big task split into smaller ones of the same kind, each of which eventually bottoms out at case 1.

The code is shorter than the description:

let festival = { // the same object, compressed for brevity
  main: [{name: 'Maya', fee: 1000}, {name: 'Nadia', fee: 1600 }],
  fringe: {
    tent: [{name: 'Raj', fee: 2000}, {name: 'Theo', fee: 1800 }],
    busking: [{name: 'Arjun', fee: 1300}]
  }
};

// The function to do the job
function sumFees(stage) {
  if (Array.isArray(stage)) { // case (1)
    return stage.reduce((prev, current) => prev + current.fee, 0); // sum the array
  } else { // case (2)
    let sum = 0;
    for (let substage of Object.values(stage)) {
      sum += sumFees(substage); // recursively call for substages, sum the results
    }
    return sum;
  }
}

alert(sumFees(festival)); // 7700

Short, and it works at any nesting depth without a single change. That is the payoff of matching your code to the recursive shape of the data.

Run it below. The Sum button walks the whole tree with sumFees; the raise button uses a second recursive walk that bottoms out at the same array leaves, mutating each fee before you re-sum. Edit the festival object to add or nest stages — the code copes without changing.

<div class="row">
<button id="sum">Sum all fees</button>
<button id="raise">Give everyone +100</button>
</div>
<div id="out"></div>

.row { display:flex; gap:10px; flex-wrap:wrap; margin-bottom:14px; }
button { padding:6px 12px; cursor:pointer; }
#out { font-size:18px; font-weight:600; }

const festival = {
main: [
  { name: 'Maya', fee: 1000 },
  { name: 'Nadia', fee: 1600 }
],
fringe: {
  tent: [
    { name: 'Raj', fee: 2000 },
    { name: 'Theo', fee: 1800 }
  ],
  busking: [
    { name: 'Arjun', fee: 1300 }
  ]
}
};

function sumFees(stage) {
if (Array.isArray(stage)) {                                  // leaf
  return stage.reduce((sum, p) => sum + p.fee, 0);
}
let sum = 0;
for (const substage of Object.values(stage)) {               // branch
  sum += sumFees(substage);
}
return sum;
}

function raiseAll(stage, amount) {
if (Array.isArray(stage)) {
  stage.forEach(p => { p.fee += amount; });
  return;
}
for (const substage of Object.values(stage)) {
  raiseAll(substage, amount);
}
}

const out = document.getElementById('out');
function show() { out.textContent = 'Total fees: ' + sumFees(festival); }

document.getElementById('sum').addEventListener('click', show);
document.getElementById('raise').addEventListener('click', () => {
raiseAll(festival, 100);
show();
});

show();

Here is the tree of calls it produces:

The rule reads straight off the diagram: objects {...} produce more subcalls, while arrays [...] are the leaves of the recursion tree — they hand back a result immediately.

Two features you have already met do the heavy lifting here:

• arr.reduce, covered in Array methods, to total an array in one expression.
• for (let val of Object.values(obj)), where Object.values returns an array of an object’s values so you can loop over them.

Recursive structures

A recursively-defined data structure is one whose parts have the same shape as the whole. The festival object was exactly that:

A stage is either:

• an array of acts, or
• an object whose values are stages.

The definition refers to itself, which is what makes it recursive.

Web developers work with a famous example every day: HTML and XML documents. An HTML tag can contain a list of:

• text pieces,
• HTML comments,
• other HTML tags (which can in turn contain text, comments, or more tags).

Self-referential again. That is precisely why the DOM is walked with recursive functions.

To make the pattern concrete, here is one more recursive structure that can beat an array in the right situation.

Linked list

Say you need to keep an ordered list of objects. The obvious choice is an array:

let arr = [obj1, obj2, obj3];

Arrays have a weak spot, though: inserting or deleting near the front is expensive. arr.unshift(obj) has to renumber every existing element to open a slot at index 0, and arr.shift() renumbers them all again after removing the first. For a large array, that reshuffle costs real time. The only cheap structural edits are at the end — push and pop — because nothing after them needs renumbering. So an array can be a poor fit for a big queue where you constantly work at the beginning.

When fast insertion and deletion matter more than random access, reach for a linked list.

A linked list element is defined recursively as an object with:

• a value, and
• a next property pointing to the next element — or null at the end.

For example:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

A picture of the chain:

You can build the same list step by step:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

Written this way it is clearer that there are four separate objects, each with a value and a next pointing at its neighbour. The list variable just holds the first object; follow next pointers from there and you can reach every element.

Splitting the list is a single reassignment, and rejoining is another:

let secondList = list.next.next;
list.next.next = null;

To join them back:

list.next.next = secondList;

Insertion and removal anywhere are just as cheap. To prepend a value, wrap the current head in a new node:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend a new value to the list
list = { value: "new item", next: list };

To remove a node from the middle, point the previous node’s next past it:

list.next = list.next.next;

Now list.next skips over the value 1 and jumps straight to 2. The 1 node is no longer part of the chain, and if nothing else references it, the garbage collector reclaims it. No renumbering, no shuffling — just a couple of pointer swaps.

Below, Prepend wraps the current head in a new node (list = { value, next: list }) and Remove head does the pointer swap list = list.next. The chain and its length are rendered by two recursive walks that follow next until they hit null:

<div class="row">
<input id="val" placeholder="value" value="0">
<button id="prepend">Prepend</button>
<button id="removeHead">Remove head</button>
</div>
<div id="chain"></div>
<div id="len"></div>

.row { display:flex; gap:8px; align-items:center; flex-wrap:wrap; margin-bottom:14px; }
input { width:90px; padding:4px 6px; }
button { padding:5px 12px; cursor:pointer; }
#chain { font-family:monospace; font-size:15px; margin-bottom:8px; }
#len { color:#555; font-size:13px; }

let list = {
value: 1,
next: { value: 2, next: { value: 3, next: null } }
};

// recursive walk: turn the chain into text
function toStr(node) {
if (node === null) return 'null';
return node.value + ' -> ' + toStr(node.next);
}

// recursive walk: count the nodes
function count(node) {
if (node === null) return 0;
return 1 + count(node.next);
}

function render() {
document.getElementById('chain').textContent = toStr(list);
document.getElementById('len').textContent = 'length (counted recursively): ' + count(list);
}

document.getElementById('prepend').addEventListener('click', () => {
const raw = document.getElementById('val').value.trim();
const value = raw === '' ? '?' : (isNaN(Number(raw)) ? raw : Number(raw));
list = { value: value, next: list };   // wrap the old head
render();
});

document.getElementById('removeHead').addEventListener('click', () => {
if (list !== null) list = list.next;   // pointer swap
render();
});

render();

Lists can be dressed up for specific needs:

• Add a prev pointer alongside next so you can walk backward (a doubly-linked list).
• Keep a tail variable pointing at the last element, updated on every end insertion/removal, so appending is O(1) without walking the whole chain.
• Shape the structure however the problem demands.

Summary

Recursion is a function calling itself. Used well, it solves certain problems with unusually clean code.

• The recursion step is the call a function makes to a smaller version of the same task.
• The base of recursion is the argument (or condition) simple enough that the function returns without recursing further. Miss it, and the calls never stop.

Every recursive call gets its own execution context on the call stack. The stack grows on the way down and unwinds on the way back up, which is why recursion depth is capped and why deep recursion costs memory proportional to that depth.

A recursively-defined data structure is one defined in terms of itself. A linked list, for instance, is an object holding a value plus a reference to another list — or null:

list = { value, next -> list }

Trees are the same idea, with branching: the HTML element tree and the festival tree above both have branches that can hold more branches. Recursive functions are the natural way to walk them, as sumFees showed.

Any recursive function can be rewritten as an iterative one, and sometimes you should — to save memory or avoid the depth limit. But for a great many tasks, a recursive solution is fast enough and far easier to write and maintain.