Recursion & Backtracking
Breaking problems into smaller versions of themselves, and undoing choices that don't work out.
- 1 Lesson
Dry-run engine
Factorial (Recursive)
Every call gets its own stack frame; recursion is just frames piling up and then unwinding.
- Input · Call
- fact(4)
- Output · Returns
- Press play to run it
How it works
fact(n) returns 1 when n <= 1; otherwise it calls fact(n - 1) and multiplies the result by n. Every call still waiting on another call keeps its own frame on the stack.
call_stack · grows ↓
- sp0x7ff0
- Depth1 frame
- Pending4 × fact(3)
- Returned—
fact(4) pushes its frame at 0x7ff0. 4 > 1, so it can't answer yet: it pauses at 4 * fact(3) and calls fact(3). Its frame keeps n = 4 alive until then.
1 / 8
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems