Nova has collected 2,000 glow readings. Rocket runs the recursive total on them.
A red error fills the screen: RecursionError. "But my total function works!" Rocket says. "It worked on three numbers."
Raven counts on her fingers. "What do you notice about how many trays that would need?"
"One tray for every reading," Rocket says. "That is 2,000 trays!"
Nova dims her lights. "Here is a hint. Python only lets the stack get so tall."
Each recursive call adds a tray to the call stack. Python stops at about 1,000 trays and shows a RecursionError.
The recursive total makes one call per item, plus one for the empty list. So 2,000 readings is too deep.
A loop does not add trays. It handles a long list easily.
def total_loop(nums):
total = 0
for n in nums:
total = total + n
return total
readings = list(range(1, 2001))
print(len(readings))
print(total_loop(readings)) Output: 2000 2001000
| Pick a loop when | Pick recursion when |
|---|---|
| you repeat the same step many times | the problem has smaller copies of itself inside |
| the list could be very long | you split a problem into halves (coming in week 9) |
| a running total or count is all you need | data is nested, like a box in a box (coming in week 10) |
| Statement | True or false? |
|---|---|
| A loop and a recursion can give the same answer. | ? |
| Recursion is always the better choice. | ? |
| A very deep recursion can cause a RecursionError. | ? |
def depth(n):
if n == 0:
return 0
return 1 + depth(n - 1)
print(depth(50))
print(depth(500)) | Statement | True or false? |
|---|---|
| depth(500) needs more trays than depth(50). | ? |
| A loop adds a tray for every pass. | ? |
| total_loop can add 2,000 numbers with no error. | ? |
| The best tool depends on the job. | ? |
Week 5 complete! You compared two ways to solve one problem, just like real engineers do. Next week we start searching the star catalog.