Rocket tests a new hop counter. It is supposed to count down by twos and then say landed.
He starts it at 5. The screen fills with 5, 3, 1, then minus 1, minus 3, minus 5, faster and faster.
Then everything stops with a big red error. "Whoa! What happened?"
Raven reads his code. "What do you notice about the numbers? Did any call ever land on 0?"
Nova blinks slowly. "Here is a hint. Your stop sign only works if a call lands exactly on it."
This function has a smaller step but no base case. It is only defined here, not called.
def forever(n):
print(n)
forever(n - 1) If you called forever(3), it would print 3, 2, 1, 0, minus 1, and keep going.
Every call adds a tray to the stack. Python stops at about 1,000 calls deep and shows a RecursionError.
The message says: maximum recursion depth exceeded. That usually means the base case is missing or never reached.
Rocket's hop counter had a base case of n == 0. Starting at 5 and taking away 2 each time gives 5, 3, 1, minus 1. It skips 0!
The fix is a base case that catches every number at or below 0.
def hop(n):
if n <= 0:
print("landed")
else:
print(n)
hop(n - 2)
hop(5) Output: 5 3 1 landed
| Function | Will it stop? |
|---|---|
| countdown(4) with base case n == 0 and step n - 1 | ? |
| countdown(4) with base case n == 0 and step n + 1 | ? |
| hop(6) with base case n <= 0 and step n - 2 | ? |
| hop(5) with base case n == 0 and step n - 2 | ? |
def hop(n):
if n <= 0:
print("landed")
else:
print(n)
hop(n - 3)
hop(7) | Statement | True or false? |
|---|---|
| n <= 0 is true when n is minus 2. | ? |
| n == 0 is true when n is minus 2. | ? |
| A safe base case catches every number the calls might land on. | ? |
| Python lets a recursion go on forever with no error. | ? |
Good debugging! A RecursionError is a clue, not a disaster. Tomorrow a recursive function hands back a value.