Comet and Wren have a friendly argument across the bench. "Recursion is so neat," Comet says. "Three lines and the total is done."
"The loop is easier for me to follow," Wren says. "What does the evidence say? Do they give the same answers?"
Nova projects the two versions of total side by side, then the two binary searches. "How can I help?" she asks. "Any recursive solution can also be written with a loop, and the other way round. So the choice is yours."
Comet crosses her arms and grins. "Then let our lead programmer trace both and decide."
Wren hands you a fresh sheet of graph paper.
# two_totals.py
def total_loop(nums):
result = 0
for n in nums:
result += n
return result
def total_rec(nums):
if len(nums) == 0:
return 0
return nums[0] + total_rec(nums[1:])
grams = [42, 18, 65, 7, 30, 51, 12, 88, 25, 39]
print(total_loop(grams))
print(total_rec(grams)) The grams are the catalog weights, made-up data from the FieldSim story. Both versions print the same total:
377 377
search.py holds the loop version from week 8. recursion.py holds the recursive one. Both search the sorted catalog grams.
# two_searches.py
from search import binary_search
from recursion import binary_search_rec
grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
for target in [7, 39, 88, 40]:
a = binary_search(grams, target)
b = binary_search_rec(grams, target, 0, len(grams) - 1)
print(target, a, b) 7 0 0 39 5 5 88 9 9 40 -1 -1
| Loop version (search.py) | Recursive version (recursion.py) |
|---|---|
| low and high change inside a while loop | low and high are new arguments for each call |
| while low <= high keeps going | if low > high: return -1 stops |
| low = mid + 1 | return binary_search_rec(items, target, mid + 1, high) |
| one call does all the work | one call per half that is searched |
Trace each program on paper first. Then pick the output you got.
# stars.py
def stars(n):
if n == 0:
return ""
return "*" + stars(n - 1)
print(stars(3))
print(len(stars(5))) # mystery.py
def mystery(n):
if n <= 1:
return 1
return n * mystery(n - 1)
print(mystery(4)) 24
Wren writes assert tests for recursion.py. Each assert compares what a function does with what it should do.
# test_recursion.py
from recursion import total, binary_search_rec, merge_sort
def test_total():
assert total([]) == 0
assert total([42, 18, 65]) == 125
def test_binary_search_rec():
grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
assert binary_search_rec(grams, 39, 0, 9) == 5
assert binary_search_rec(grams, 40, 0, 9) == -1
def test_merge_sort():
assert merge_sort([]) == []
assert merge_sort([42, 18, 65, 7]) == [7, 18, 42, 65]
test_total()
test_binary_search_rec()
test_merge_sort()
print("All recursion tests passed") | Statement | True or false? |
|---|---|
| test_total checks the base case. | ? |
| test_merge_sort checks an empty list. | ? |
| These tests check that reachable gives 26. | ? |
| If every assert holds, the file prints one line. | ? |
Great tracing, lead programmer. You can now follow a stack of calls on paper and choose between a loop and recursion.