level 8 · Core techniques
Recursion & the Call Stack
A function that calls itself — and the pile of calls that piles up.
what is it
Start here
Recursion is a function that calls itself on a smaller version of the same problem, until the problem gets so small the answer is obvious.
Everyone's first instinct is that the work happens on the way *down*. It doesn't. Watch the visualization: factorial(5) can't answer anything — it needs factorial(4) first. So it parks itself and waits. factorial(4) does the same. Nothing is computed at all, five calls deep.
Then factorial(1) hits the base case. It doesn't need anyone. It just knows: 1. And *now* the answers come back up the pile, each call finally able to finish its multiplication. The work happens on the way back up.
That pile is the call stack — a real stack, exactly like the one you just learned. And if the base case is missing, or never reached, the pile grows until there's no room left. That is a stack overflow, and now you know precisely what it means.
real-life analogy
Picture it
You're in a queue and want to know your position. You don't know — so you tap the person in front and ask them theirs. They don't know either, so they ask the person in front of *them*. This continues to the very front, where someone finally says 'I'm first'. Then the answer travels back: 'you're 2nd', 'you're 3rd'… Nobody could answer until the front of the line spoke.
interactive visualization
Watch it run
Type one number from 1 to 10. Watch the calls pile up before any answer appears.
the call stack · grows downward
stack empty — every call has returned
answers, on the way back up
nothing has returned yet
factorial(5) means 5 × 4 × 3 × 2 × 1. Watch how the computer gets there — it is not the way you'd do it by hand.
step 01/11
space · play ← → · step
| 1 | function factorial(n) { |
| 2 | if (n <= 1) { |
| 3 | return 1; |
| 4 | } |
| 5 | return n * factorial(n - 1); |
| 6 | } |
variables right now
- n
- 5
the dry run · every step, in words
11 stepscomplexity
What it costs
- best case
- O(n)
- average
- O(n)
- worst case
- O(n)
- extra memory
- O(n)
n calls, so n multiplications: O(n) time. But it also uses O(n) *space* — every waiting call takes up room on the stack. A loop doing the same job uses O(1) space. Recursion is never free.
- O(1)
- O(log n)
- O(n) · this one
- O(n log n)
- O(n²)
common mistakes
Common traps
Writing a recursive function with no base case.
Without a case that returns without recursing, the calls never stop. The stack fills and the program dies. The base case is not optional — it's the floor.
Recursing on the same problem instead of a smaller one.
factorial(n) must call factorial(n − 1), not factorial(n). Every call has to move closer to the base case, or you never reach it.
Believing the multiplication happens on the way down.
It happens on the way back up. Nothing is computed until the base case returns — which is exactly what the call stack visualization shows you.
Assuming recursion is free because the code is short.
Every pending call takes stack space. Deep recursion on a big input can overflow where a simple loop would happily run forever.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+90 XP01What is the base case for?
02In factorial(5), when does the first actual multiplication happen?
03Why does recursion use O(n) space when a loop uses O(1)?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.