PHASE 3Beginner ~26 min· topic 8 of 9

Topic 3.8

Recursion

In one line

A recursive function solves a problem by calling itself on a smaller piece of it, until it reaches a base case simple enough to answer directly; every pending call waits on the call stack, and without a base case the stack overflows.

Think of it like this

Russian nesting dolls (matryoshka). To find the tiny doll in the middle, you open a doll, and inside is a smaller doll of the same kind, so you do the same thing again. You stop when you reach a doll that doesn't open: that's the base case. Then you put them back together from the inside out, which is exactly how the answers of a recursive function come back.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Recursion: A function solving a problem by calling itself on a smaller version of it.
Base case: The simplest input, answered directly, where the self-calls stop.
Recursive case: The part that calls the function again with a smaller input.
Call stack: The engine's list of function calls that haven't finished, newest on top.
Stack frame: One entry on the call stack: a call's parameters, local variables and return point.
Stack overflow: The error when the call stack runs out of room, usually from recursion that never stops.
Tree: Data where each item can contain more items of the same kind, like folders or a page's elements.
Memoisation: Saving the results of calls so the same input is never computed twice.

Step by step

01Find the smaller copy of the problem

The factorial of n (written n!) is n × (n − 1) × … × 1. Notice that 5! = 5 × 4!: the problem contains a smaller copy of itself.

02Write the base case first

Decide when to stop before anything else. For factorial, 1 (and 0) give 1.

factorial.jswhole filejavascript

function factorial(n) {
  if (n <= 1) {
    return 1; // base case: no more calls
  }
  // recursive case goes here
}

03Add the recursive case

Call yourself with a smaller input and combine the answer. n - 1 always gets closer to 1, so it's guaranteed to stop for positive whole numbers.

factorial.jswhole filejavascript

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}
factorial(4); // 24

04Watch the stack grow and shrink

Each call waits for the one it made. The answers come back up in reverse order.

Watch the stack grow and shrinkdiagram

Rendering diagram…

05Recurse into a tree

For nested data, the recursive case is "for each child, do the same thing". A leaf with no children is the base case, so the loop simply doesn't run.

tree.jswhole filejavascript

function countFiles(node) {
  if (node.children.length === 0) {
    return 1; // a file
  }
  let total = 0;
  for (const child of node.children) {
    total += countFiles(child);
  }
  return total;
}

06Know the limits

Forget the base case, or never reach it, and the stack overflows. For very deep or simple counting work, a loop is safer.

Try it yourself

1
Count up instead
In the first example, write countUp(n) that prints 1 up to n using recursion. Hint: make the recursive call before the console.log.
2
Grow the menu
In the second example, add a Recursion child under Functions. Predict the new items and levels values before running.
3
Time the difference
In the third example, change both 20s to 25. How many calls does each version make now? (Predict: does the slow one grow by a little or a lot?)

Code & diagrams

Countdown, factorial and sum New tab

Console

(nothing was printed)

Expected console output

3
2
1
Liftoff!
120
15

Walking a tree: a nested menu New tab

No loop could easily follow branches of unknown depth; recursion handles any depth with the same few lines.

Preview

Press Run to see the page.

Console

Nothing logged yet.

Expected console output

items: 6
levels: 4

Stack overflow and repeated work New tab

The exact overflow depth differs between browsers, so the example only checks it's large. Memoisation cuts 21,891 calls to 39.

Console

(nothing was printed)

Expected console output

RangeError: Maximum call stack size exceeded
more than 1000 frames? true
fib(20) = 6765 using 21891 calls
fastFib(20) = 6765 using 39 calls

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Forget the base case

Delete if (n <= 1) return 1; from factorial and call factorial(5).

terminal

$ Console

── what you'll see ──

Uncaught RangeError: Maximum call stack size exceeded

Break #2

Recursive call that doesn't shrink

Write return n * factorial(n); (forgot the - 1).

terminal

$ Console

── what you'll see ──

Uncaught RangeError: Maximum call stack size exceeded

Myth vs fact

Myth

Recursion is always slower than a loop.

Fact

Each call has a small cost, but it's rarely what makes code slow. Repeated work (like naive Fibonacci) is the real danger, and memoisation fixes it.

Myth

If you write the recursive call last, JavaScript optimises it away.

Fact

Proper tail calls are in the ES2015 spec, but only Safari implements them. In Chrome, Firefox and Node, every call still uses a stack frame.

Myth

Recursion is only for maths puzzles.

Fact

It's the natural tool for any nested data: file trees, the DOM, menus, comment threads, JSON.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Chrome's limit is set by stack bytes, not a fixed number of calls, so functions with many locals overflow sooner. Never rely on a specific depth; convert to an explicit stack (const stack = [root]; while (stack.length) { ... }) when input depth isn't under your control, such as user-supplied JSON.
▸
JSON.stringify, structuredClone and deep-equality helpers are recursive internally, and they guard against cycles (an object that contains itself); your own tree walkers should track visited nodes with a Set when cycles are possible.
▸
The DOM has built-in non-recursive walkers (TreeWalker, querySelectorAll) that are faster than recursing through children yourself on large documents.
▸
Divide-and-conquer recursion (merge sort, binary search on trees) has depth O(log n), so stack size is never an issue there; linear recursion over a list has depth O(n) and is the risky kind.

Remember this

1
Recursion is when a function calls itself. It works for problems that contain smaller copies of the same problem: the factorial of 5 is 5 × factorial(4); the total size of a folder is its files plus the total size of each sub-folder; a list's sum is its first item plus the sum of the rest. Each recursive function has two parts.
2
The base case is the input so small that the answer is known without recursion: factorial(1) is 1, the sum of an empty list is 0, a file has no sub-folders. The recursive case handles everything else by calling the function on a smaller input and combining the result: return n * factorial(n - 1). Every recursive call must move towards the base case; if it doesn't, the calls never stop.
3
The call stack is how the engine keeps track of function calls that haven't finished yet. Each call gets a stack frame, a little record holding its parameters, local variables and where to return to. Calling a function pushes a frame on top; returning pops it off. With recursion, factorial(4) pushes frames for 4, 3, 2 and 1; then factorial(1) returns 1 and the frames pop in reverse order, each multiplying as it goes: 1, 2, 6, 24. You can watch this in DevTools: set a breakpoint in a recursive function and look at the Call Stack pane.
4
The stack has a limited size. If recursion goes too deep, usually because the base case is missing or never reached, the engine throws RangeError: Maximum call stack size exceeded, called a stack overflow. The exact limit depends on the browser and on how big each frame is; in Chrome it's on the order of ten thousand frames. JavaScript engines (except Safari's) don't perform tail-call optimisation, so even a recursive call written as the very last step still uses a frame.
5
Recursion shines with nested, tree-shaped data: folders inside folders, comments with replies, menus with sub-menus, the page's own DOM tree, JSON of unknown depth. A loop walks a flat list well, but a tree can branch anywhere, and recursion follows the branches naturally: "handle this node, then do the same for each child".
6
Any recursion can be rewritten as a loop (sometimes with your own stack array), and loops don't risk overflowing the stack. Use recursion when it makes the code clearly simpler, mostly for trees and divide-and-conquer algorithms; use a loop for simple counting or very deep inputs. Watch out for repeated work: the naive Fibonacci fib(n - 1) + fib(n - 2) recomputes the same values exponentially many times; caching results (memoisation) fixes that. Hectal's /dsa course builds on this with recursion, backtracking and dynamic programming.

Explain it without notes

What two parts does every recursive function need, and why?

What is the call stack, and what happens on it during factorial(3)?

What causes RangeError: Maximum call stack size exceeded, and how do you prevent it?

When would you choose recursion over a loop, and vice versa?

Practice

Write power(base, exp) recursively for whole-number exp >= 0 (base case: exp === 0 returns 1).

Write reverse(text) recursively, so reverse("abc") returns "cba".

Write sumNested(list) that adds all numbers in an array that may contain arrays at any depth, like [1, [2, [3, 4]], 5].

Trade-offs

↔
Recursive code for trees is short and mirrors the data, but depth is limited by the stack; an explicit stack in a loop handles any depth at the cost of more code.
↔
Memoisation trades memory (the cache) for speed (no repeated calls).

Done when you can

I can identify the base case and recursive case of a recursive function.
I can trace how frames are pushed and popped on the call stack.
I can recognise and fix a stack overflow.
I can walk nested data with recursion.
I know when a loop is the better choice, and what memoisation fixes.

Command Palette

Words you'll meet

Step by step

01Find the smaller copy of the problem

02Write the base case first

03Add the recursive case

04Watch the stack grow and shrink

05Recurse into a tree

06Know the limits

Try it yourself

Count up instead

Grow the menu

Time the difference

Code & diagrams

Break it on purpose

Forget the base case

Recursive call that doesn't shrink

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can