cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 19 of 218
Ideas this builds on
Recursion19 / 218

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.