Stop 18 · Data Structures & AlgorithmsTopics · 11/17

Recursion

Part of the Full Stack Developer Roadmap

In short

Trees, backtracking and dynamic programming all lean on recursion. Once you trust that a function can call itself on a smaller problem, those topics stop being scary.

Solving a problem by having a function call itself on a smaller version of the same problem, with a base case that stops the recursion.

In a cinema, the purple blob taps the shoulder of the person in the row in front.

Think of it like this

Which row am I in?

In a dark cinema hall you can't see the row numbers. So you tap the person in front: "Which row are you in?" They ask the person in front of them, and so on. Row 1 knows the answer, and it passes back, plus one each time.

Watch it happen

The call stack for factorial(3)

push(factorial(3))

factorial(3)

Top of the stack is coloured

1/6factorial(3) can't answer yet. It needs factorial(2) first, so it waits on the stack.

The big ideas

What you need to know

A base case stops it

Every recursive function needs a case it can answer directly. Without one, it calls itself until the stack overflows.

Each call gets smaller

The recursive call must move towards the base case, like n - 1 or a child node.

It uses the call stack

Each waiting call takes stack memory. Very deep recursion in Node.js throws "Maximum call stack size exceeded".

Perfect for nested data

Folders inside folders, comments with replies, JSON inside JSON: recursion follows the shape naturally.

See it in code

Walk through the code

1type Folder = { size: number; children: Folder[] };2 3function totalSize(folder: Folder): number {4  let total = folder.size;               // this folder's own files5  for (const child of folder.children) {6    total += totalSize(child);           // same problem, smaller input7  }8  return total;                          // no children? the loop simply skips9}

1/3Start with this folder's own size.

You don't need to trace every level in your head. Trust that totalSize(child) works, and just add the results.

Save yourself the pain

Common mistakes

Oops

Forgetting the base case, or writing one the input never reaches.

Do this instead

Write the base case first, then check every call moves closer to it.

Oops

Recomputing the same calls again and again, like naive fibonacci(40).

Do this instead

Cache results in a Map (memoisation). That's the doorway to dynamic programming.

Your mission

Think recursively

~30 min

Quick check

Your recursive function crashes with "Maximum call stack size exceeded". What's the most likely cause?

Go deeper

1Solve factorial and Fibonacci both recursively and iteratively, and compare.
2Practice tracing through a recursive call stack on paper before coding.
3Learn to identify the base case and recursive case for any new problem.