Dividing a Problem into Smaller Parts

Identify independent subproblems or invariant that survives the split.

Try this in Python

def max_in(a):
    return max(a) if len(a) <= 2 else max(max_in(a[: len(a) // 2]), max_in(a[len(a) // 2 :]))

print(max_in([3, 1, 4, 1, 5]))

Key takeaways

• Proof idea: show answer merges correctly from children.
• Sometimes divide on value not index.
• Tail recursion rarely needed in Python.