Wren lays the sorted catalog weights across the bench, lightest to heaviest. "In week 8, binary search used a loop," he says. "Could it use recursion instead?"
Comet is already sketching. "Look in the middle. If it is not there, search one half. That half is a smaller problem!"
"And sorting?" Wren asks. "What does the evidence say about splitting a list in half?"
Nova projects a tree of boxes that splits the four weights into halves, then into single items. "How can I help?" she asks. "A list of one item is already sorted. That could be a base case."
Comet laughs. "Split until it is easy, then put it back together."
Binary search needs sorted data. It starts in the middle and removes half of what is left each step. It can be written with a loop or with recursion.
Merge sort is a recursive sort. It splits a list in half, sorts each half, and merges the two sorted halves.
Type these three functions into recursion.py, between total and reachable. Your file will then match Nova's full version.
def binary_search_rec(items, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
return binary_search_rec(items, target, mid + 1, high)
else:
return binary_search_rec(items, target, low, mid - 1)
def merge(left, right):
"""Join two sorted lists into one sorted list."""
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(items):
if len(items) <= 1:
return items
mid = len(items) // 2
return merge(merge_sort(items[:mid]), merge_sort(items[mid:])) # try_recursion.py from recursion import binary_search_rec, merge, merge_sort grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] print(binary_search_rec(grams, 39, 0, len(grams) - 1)) print(binary_search_rec(grams, 40, 0, len(grams) - 1)) print(merge([7, 42], [18, 65])) print(merge_sort([42, 18, 65, 7]))
This copy of binary_search_rec prints low, mid and high at each call. The data are the sorted catalog grams, made-up data from the FieldSim story.
# trace_bsr.py (a copy that prints each call)
def binary_search_rec(items, target, low, high):
print(f"call low={low} high={high}")
if low > high:
return -1
mid = (low + high) // 2
print(f" mid={mid} item={items[mid]}")
if items[mid] == target:
return mid
elif items[mid] < target:
return binary_search_rec(items, target, mid + 1, high)
else:
return binary_search_rec(items, target, low, mid - 1)
grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88]
print("Found at", binary_search_rec(grams, 39, 0, 9))
print("Found at", binary_search_rec(grams, 40, 0, 9)) | Call for 39 | low | high | mid | items[mid] | Next |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 30 | 30 is less: search the right half |
| 2 | 5 | 9 | 7 | 51 | 51 is more: search the left half |
| 3 | 5 | 6 | 5 | 39 | found: give back 5 |
call low=0 high=9 mid=4 item=30 call low=5 high=9 mid=7 item=51 call low=5 high=6 mid=5 item=39 Found at 5 call low=0 high=9 mid=4 item=30 call low=5 high=9 mid=7 item=51 call low=5 high=6 mid=5 item=39 call low=6 high=6 mid=6 item=42 call low=6 high=5 Found at -1
# trace_merge_sort.py (a copy that prints each call)
from recursion import merge
def merge_sort(items, depth=0):
pad = " " * depth
print(f"{pad}sort {items}")
if len(items) <= 1:
return items
mid = len(items) // 2
left = merge_sort(items[:mid], depth + 1)
right = merge_sort(items[mid:], depth + 1)
result = merge(left, right)
print(f"{pad}merged {result}")
return result
merge_sort([42, 18, 65, 7]) sort [42, 18, 65, 7]
sort [42, 18]
sort [42]
sort [18]
merged [18, 42]
sort [65, 7]
sort [65]
sort [7]
merged [7, 65]
merged [7, 18, 42, 65] # try_recursion.py from recursion import binary_search_rec, merge, merge_sort grams = [7, 12, 18, 25, 30, 39, 42, 51, 65, 88] print(binary_search_rec(grams, 39)) print(binary_search_rec(grams, 40, 0, len(grams) - 1)) print(merge([7, 42], [18, 65])) print(merge_sort([42, 18, 65, 7]))
Traceback (most recent call last):
File "try_recursion.py", line 5, in <module>
print(binary_search_rec(grams, 39))
~~~~~~~~~~~~~~~~~^^^^^^^^^^^
TypeError: binary_search_rec() missing 2 required positional arguments: 'low' and 'high' | Statement | True or false? |
|---|---|
| Binary search works on data in any order. | ? |
| Binary search can be written with a loop or with recursion. | ? |
| In merge_sort, a list of one item is a base case. | ? |
| merge([7, 42], [18, 65]) gives [7, 18, 42, 65]. | ? |
Your recursion.py is now complete, lead programmer. Tomorrow you will compare recursion with the loops you already know.