Recursion: Factorial
Easy+60 XPSee recursion as a call stack: calls push on the way down, pop on the way up.
No visualization loaded.
Watch
—
Press Run to begin.
Recursion is when a function solves a problem by calling itself on a smaller version. factorial(4) = 4 × factorial(3), and factorial(3) = 3 × factorial(2), and so on down to factorial(1) = 1, which needs no further help. The calls stack up on the way DOWN, then the answers multiply back together on the way UP. This animation shows that stack so the 'magic' becomes mechanical.
▸How can a function call itself without looping forever?
Because each call works on a SMALLER input and there's a stopping point. factorial(4) asks factorial(3), which asks factorial(2), which asks factorial(1) — and factorial(1) just returns 1 without asking anything. That stopping point is the 'base case.' No base case = infinite recursion (a crash), so every recursion needs one.
▸What is the 'call stack' the animation keeps showing?
It's the pile of paused, half-finished calls. When factorial(4) calls factorial(3), the (4) call pauses and waits — it gets pushed on the stack. This piles up until factorial(1) returns. Then calls pop off one by one, each multiplying in its number on the way back up. Push going down, pop coming up — exactly like a stack.
▸What's the 'base case' vs the 'recursive case'?
The base case is the simplest input you can answer directly with no further calls (factorial(1) = 1). The recursive case is the rule that shrinks the problem (factorial(n) = n × factorial(n-1)). Every recursive function is just these two parts: 'when do I stop?' and 'how do I shrink?'
▸When should I think recursively instead of using a loop?
When a problem naturally breaks into a smaller copy of itself — sorting halves (merge sort), exploring a tree, walking a maze. Loops and recursion can often do the same job, but recursion reads cleanly when the structure is self-similar. Seeing the call stack here is what makes the trickier recursive algorithms later feel approachable.
How the work grows
O(n) is fair — grows in step with the data. factorial(n) makes n nested calls, so the work grows in step with n. But notice the SPACE: all n calls sit paused on the call stack at once, so deep recursion costs O(n) memory — something a simple loop wouldn't.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.