Wren wants the total weight of three samples, 42, 18 and 65 grams. Comet scribbles a new function in her notebook.
"The total is the first number plus the total of the rest," she says. "The rest is a shorter list, so the function can call itself."
Wren taps his clipboard. "What does the evidence say? Show me every call, and what each one gives back."
Nova projects a stack of cards, one card for each call. "How can I help?" she asks. "A new call goes on top. A finished call comes off the top and hands back its answer."
Comet types fast, as usual, and runs before tracing. Something goes wrong. Wren smiles. "Good. Now we have data."
# total.py
def total(nums):
"""Sum of a list, the recursive way."""
if len(nums) == 0:
return 0
return nums[0] + total(nums[1:])
print(total([42, 18, 65])) The base case is the empty list, whose total is 0. Every other list gives its first item plus the total of the rest.
nums[1:] is a new, shorter list, so every call moves toward the empty list.
Each call has its own local variables, including its own nums. So four calls means four different lists named nums.
This copy of total prints each call, indented one step for each level of the stack. It adds a depth parameter only for the printing.
# total_trace.py (a copy of total that prints each call)
def total(nums, depth=0):
pad = " " * depth
print(f"{pad}total({nums})")
if len(nums) == 0:
print(f"{pad}base case gives 0")
return 0
result = nums[0] + total(nums[1:], depth + 1)
print(f"{pad}gives {result}")
return result
print(total([42, 18, 65])) total([42, 18, 65])
total([18, 65])
total([65])
total([])
base case gives 0
gives 65
gives 83
gives 125
125 | Call (newest at the bottom) | nums in this call | Gives back |
|---|---|---|
| total([42, 18, 65]) | [42, 18, 65] | 42 plus 83 |
| total([18, 65]) | [18, 65] | 18 plus 65 |
| total([65]) | [65] | 65 plus 0 |
| total([]) | [] | 0 (base case) |
Comet first wrote a function with no base case at all. It only calls itself with a smaller number, forever.
# shrink.py (no base case)
def shrink(n):
return shrink(n - 1)
shrink(3) Python stops a recursion that goes too deep with a RecursionError. The recursion limit is the deepest the stack may grow, and it keeps endless recursion from crashing Python.
The traceback is very long, so here is only its last line: RecursionError: maximum recursion depth exceeded
Next, Comet deleted the base case from total. This time the error is different:
# total.py
def total(nums):
"""Sum of a list, the recursive way."""
return nums[0] + total(nums[1:])
print(total([42, 18, 65])) Traceback (most recent call last):
File "total.py", line 7, in <module>
print(total([42, 18, 65]))
~~~~~^^^^^^^^^^^^^^
File "total.py", line 4, in total
return nums[0] + total(nums[1:])
~~~~~^^^^^^^^^^
File "total.py", line 4, in total
return nums[0] + total(nums[1:])
~~~~~^^^^^^^^^^
File "total.py", line 4, in total
return nums[0] + total(nums[1:])
~~~~~^^^^^^^^^^
[Previous line repeated 1 more time]
IndexError: list index out of range You traced a whole stack of calls and read two very different errors. Tomorrow the crew uses recursion on the test field itself.