Teaching recursion to beginners, my current explanation: every call puts a plate on a stack, and a function can only finish when the plates above it are gone.
def countdown(n):
if n == 0:
print("liftoff")
return
print(n)
countdown(n - 1)
countdown(3)
Trace it with plates. countdown(3) puts a plate marked n=3 on the stack, prints 3, and calls countdown(2), which puts a plate n=2 on top, and so on. When n == 0 it prints "liftoff" and returns, the top plate is removed and we are back in the call with n=1, which has nothing left to do and returns, then n=2, then n=3.
Two things students need to see, and plates show both:
- The base case is the plate that does not call anyone. Without it, the pile grows until the table (the stack) breaks. In Python that is
RecursionError, by default after about a thousand plates. - Each plate has its own
n. They do not share it. That is why recursion works without any clever bookkeeping: the bookkeeping is the stack.
Once that clicks, factorial and tree traversal stop being magic and become "the same pile of plates, with a different instruction on each one".