Ways to make the problem smaller

Smaller does not always mean "one less". You can shrink a list by peeling one element off each end, or by cutting it in the middle and throwing half away. The way you choose decides how many calls are made.

1def find(values, key, lo, hi):
2    if lo > hi:
3        return -1
4    mid = (lo + hi) // 2
5    if values[mid] == key:
6        return mid
7    if values[mid] < key:
8        return find(values, key, mid + 1, hi)
9    return find(values, key, lo, mid - 1)

Searching a sorted list: look at the middle, and if what you want is larger, drop the whole left half. The list is not copied; only the bounds lo and hi close in. Each call halves what is left, so a thousand elements take ten calls.

Peeling from both ends is the same pattern: if the ends agree, call yourself for what is left inside; if they do not, the answer is known at once. The base case is one element left, or none.

Tasks