TwiddleLab / Code / Recursion: Functions That Call Themselves
The Base Case
What you will learn
- The base case is the line that answers without calling again. It is the floor.
- The recursive case calls the function on a smaller problem, one step closer to the floor.
- Without a floor, or with steps that skip over it, the stack fills up: a stack overflow, RecursionError in Python.
- Base case plus recursive case is the same shape as the first domino plus the knock.
How the lesson goes
This function calls itself forever. Where does it stop?
There is no line that stops it. Bet how many cards pile up before something breaks.
Run it and watch the stack.
It prints 3, 2, 1, 0, -1 and keeps going.
No call ever finishes, so no card ever comes off. Python keeps a limit on the stack so a runaway function crashes with a clear error instead of eating all the memory.
There's a check for 0 now, but it does nothing. Fix it.
Make countdown(3) print 3, 2, 1 and stop.
return ends the current call at once. With it, countdown(0) never reaches the recursive call, so the chain stops at the floor.
Base case and recursive case.
The base case answers right away, without calling again. It is the floor: here, if n == 0, return.
The recursive case calls the function on a smaller problem: countdown(n - 1).
Every recursive call must move closer to the base case. If it never gets there, the stack fills up: a stack overflow.
Floor or fall?
For each function, tap Lands if it reaches its floor, or Overflows if it never does. Then watch.
stairs(5) goes down 2 steps at a time and crashes. Fix the floor.
Change one symbol so it prints 5, 3, 1, Down.
n goes 5, 3, 1, -1, -3 and so on: it is never exactly 0. With n <= 0 the call stairs(-1) is caught by the floor and the chain stops.
Build power(b, e): b multiplied by itself e times.
Its floor: anything to the power 0 is 1. Make power(2, 3) give 8.
power(2, 3) = 2 x power(2, 2) = 2 x 2 x power(2, 1) = 2 x 2 x 2 x power(2, 0), and power(2, 0) is the floor: 1. Return 0 there and everything would multiply to 0.
Math calls this induction. Label the dominoes.
Base case and recursive case have twins in a row of falling dominoes.
In recursion the base case is where the chain is sure to end, and the recursive case links each call to a smaller one. In induction the first domino is where it starts, and the rule links each case to the next. Both need both parts.
Make your power function build a stack exactly 6 cards tall.
Slide e. Your code runs power(2, e) each time. Then Check.
Each call lowers e by 1 until e is 0. Starting from e = 5 that is the calls for 5, 4, 3, 2, 1 and 0: six cards, and only the last one stops.
Previous lesson: A Function That Calls Itself · Next lesson: Trust the Smaller Problem · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
