Give one recursive call a contract
Separate the meaning of a call, its base case, and its progress toward termination.
Understand the idea
A recursive function is a promise about its parameters. sum(i) may mean the sum of a[i..n). The empty suffix has sum zero; every other call returns a[i] + sum(i + 1). The base case gives an answer directly, while increasing i proves progress toward it.
Trace a small example
For [4, 1, 3], sum(0) waits for sum(1), which waits for sum(2), which waits for sum(3) = 0. Returns then produce 3, 4, and 8. Each caller resumes at the line after its child call with its own local variables still available.
Conditions and cost
A base case that is never reached does not prevent infinite recursion. This traversal uses O(n) work and O(n) stack space. Empty input must be checked before indexing; a recursive version is not automatically better than a loop.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
What proves that sum(i + 1) eventually reaches sum(n)?
Turn the idea into code
Trace factorial(4), using factorial(0) = 1.
Give me a hint
List calls on the way down and multiplication results on the way up.
Show the explained solution
Calls visit 4, 3, 2, 1, 0. Returns are 1, 1, 2, 6, 24. The 0! base value is the empty-product identity.
Your notes
Mark complete when you can explain it yourself.