Recursion
In short: a recursive function solves a problem by calling itself on a
smaller version of the same problem, until a base case is small
enough to answer directly — no more calls. Every call gets its own frame on
the call stack, with its own local variables, completely separate from the
frame that called it. Frames stack up while the calls go deeper, then pop
off and return, one at a time, in reverse order — which is also why
recursion without a base case doesn't loop forever quietly, it crashes with
RecursionError once the stack runs out of room (Python's default limit is
about 1000 frames deep). The DSA course builds whole algorithm families on
top of this; here it's just the base-case-and-stack mechanics.
Price a gift hamper of nested boxes
A gift-wrapping service prices a hamper where boxes can hold smaller boxes,
which can hold smaller boxes still, to any depth. factorial is the
simplest version of the same shape — each call waits for the one it made,
then does one more multiplication before handing its own answer back up:
Step through it and watch the calls pile up before any of them return:
factorial(4) can't finish its multiplication until factorial(3) returns
a value — which can't finish until factorial(2) returns — all the way
down to factorial(1), the base case, which returns 1 with no further
call. Then every waiting multiplication resolves, one level at a time, on
the way back up: 1, then 2, then 6, then 24. The mistake people make
reading this code for the first time is assuming the multiplications happen
on the way down — they don't. Nothing multiplies until the base case is
hit and the unwinding starts.
Compute compound interest, year by year
A savings calculator figures out a balance after n years of compounding,
where each year's answer depends on the year before it — exactly the shape
recursion solves, with each call carrying its own n completely separately
from every other call:
def countdown(n):
if n == 0:
return ["liftoff"]
return [n] + countdown(n - 1)
print(countdown(3))Two different calls to countdown never share one n — countdown(3)'s
local n is 3 for its entire lifetime, even though it's sitting on the
stack waiting on countdown(2), whose own n is 2 in a completely
separate frame. That independence is what makes recursion safe at all: if
every call shared the same variables, this would break the moment two calls
were alive at once.
Flatten a company's reporting chain
A company's org chart is a manager with direct reports, who may themselves manage more people, to any depth — there's no fixed number of levels to loop over, which is exactly where recursion earns its keep over a loop. The mistake that breaks recursive code most often, though, isn't the recursive step — it's forgetting the base case, or writing one that's never actually reached, so the calls never stop on their own:
RecursionErrorRun it and watch it crash. Then make it print 1 through 5 and stop.
Every working recursive function needs two things: at least one case that
returns without recursing (the base case), and a guarantee that every
recursive call moves strictly closer to it. count_up has neither — n
only ever grows, so no condition ever stops it, and Python eventually
refuses to add one more frame.
Quick practice
def mystery(n):
if n == 0:
return 0
return n + mystery(n - 1)
print(mystery(4))def countdown(n):
if n == 0:
return ["liftoff"]
return [n] + countdown(n - 1)
print(countdown(0))🎯 Your turn
Write sum_digits(n) recursively. Add up the digits of a non-negative
integer n:
sum_digits(1234)→10(1+2+3+4)sum_digits(5)→5
Hint — the base case is a single digit: if n < 10: return n. Otherwise,
n % 10 peels off the last digit and n // 10 is everything else —
return n % 10 + sum_digits(n // 10).
Press ▶ Run, try the Live App chips, then ✓ Check. After that, the practice set below counts down, raises to a power, and flattens a nested list — recursion's natural shape.