One call, one promise
Picture
Recursion becomes less mysterious when you stop trying to hold every call in your head. Give one call a contract: “If you hand me this smaller problem, I will return this answer.” Your job is to define the smallest cases and explain how correct smaller answers produce the current answer.
Predict
Let total(i) mean “the sum of values from index i onward.” Should its base case return the first array value or zero when i == len(values)?
Reveal the reasoning
Zero. That suffix is empty. The contract determines the base case, and zero is what allows values[i] + total(i+1) to work at the final element.
Go deeper: trust the smaller contract, verify the composition
def suffix_sum(values):
def total(i):
if i == len(values):
return 0
return values[i] + total(i + 1)
return total(0)
assert suffix_sum([4, 2, 7]) == 13
assert suffix_sum([]) == 0
For [4, 2, 7], the calls ask total(0) → total(1) → total(2) → total(3). The returns resolve in reverse: 0 → 7 → 9 → 13. Calling descends into an unanswered dependency; returning carries the completed answer back.
Three obligations replace blind faith: the base answer is correct; every recursive dependency is smaller under a measure that cannot decrease forever; combining correct smaller answers gives the promised answer. Here the measure is len(values)-i.
This example takes O(n) time and O(n) call-stack space. A loop is preferable for summing a long list; the example isolates the reasoning you will need for branching structures. Python does not automatically remove recursive frames, and deep inputs can exceed its recursion limit.
Avoid slicing the remaining list at every call: repeated copies can change this simple example’s time and memory costs. An index describes the suffix without copying it.
Analogy limit: the “helper” is the same function with its own arguments and frame, not a magical separate solver.
Change one rule
Replace total(i + 1) with total(i). What failed even though the combination still looks like addition?
Check the variation
The subproblem no longer shrinks. The function asks itself the same unanswered question forever, eventually raising a recursion error.
Connect
Tree summaries replace one smaller suffix with multiple child subtrees. Backtracking explores choices. Memoization changes repeated evaluation, not the contract.