Recursive algorithms and terminating ranges

The idea

Recursion separates a problem into a base case and one or more smaller cases. Track what each call returns as well as the order in which calls occur. A function that visits a list by index can use index == len(items) as its empty-suffix case, avoiding repeated slices. Slicing at every level creates extra collections and changes the cost of an otherwise simple traversal.

For sorted data, a binary search can shrink a half-open range until no candidate positions remain. The midpoint must be excluded from the next range when comparison proves it cannot be the answer. Write the invariant before coding. Python does not promise tail-call elimination, so a linear-depth recursive traversal can hit recursion limits; use iteration when the input can be long.

def total(items, i=0):
    if i == len(items):
        return 0
    return items[i] + total(items, i + 1)
print(total([4, -1, 3]))
print(total([]))

6
0

Each recursive call handles a shorter suffix, and the empty suffix contributes the additive identity.