Stop 21 · Data Structures & AlgorithmsTopics · 11/17

Recursion

In short

Trees, backtracking and DP all lean on recursion. If a function calling itself still feels like magic, this is the topic to fix before moving on.

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.

The jaadu in a cinema seat taps the shoulder of the person in the row ahead.

Think of it like this

Which row am I in, at the movies?

It's dark and you can't count rows. So you ask the person in front, who asks the person in front of them. The front-row person says '1'. Each answer comes back with 1 added, until it reaches you.

Watch it happen

The call stack during flatten([1, [2, [3]]])

push(flatten(A))

flatten(A)

Top of the stack is coloured

1/6Call with A = [1, [2, [3]]]. 1 is a plain value, so it goes straight into out.

The big ideas

What you need to know

Base case first

The smallest input you can answer directly. Without it, the function never stops.

Shrink the problem

Each call must work on something smaller, so it moves towards the base case.

Calls pile up on the stack

Each call waits for the one it made. Deep recursion uses O(depth) memory.

Too deep crashes

Go too deep and JS throws 'Maximum call stack size exceeded'. Very deep inputs may need a loop instead.

See it in code

Walk through the code

1function flatten(arr) {2  const out = [];3  for (const item of arr) {4    if (Array.isArray(item)) {5      out.push(...flatten(item)); // smaller problem6    } else {7      out.push(item);             // base case: plain value8    }9  }10  return out;11}12 13flatten([1, [2, [3, [4]]], 5]); // [1, 2, 3, 4, 5]

1/4An array inside? Call flatten on that smaller piece and spread its result in.

A classic frontend interview question. Each value is visited once, so time is about O(n). The call stack grows with the nesting depth d, so stack space is O(d).

Save yourself the pain

Common mistakes

Oops

Writing the recursive call first and the base case 'later'.

Do this instead

Write the base case at the top of the function before anything else.

Oops

Not trusting the recursive call and trying to trace every level in your head.

Do this instead

Assume the call works for the smaller input. Just check the base case and how you combine results.

Your mission

Think recursively

~30 min

Quick check

Your recursive function has no base case. What happens when you run it in the browser?

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.