Example 1 — Trace calls down and results up
Show the steps and the answer
Find the base case: e == 0 returns 1 with no further call.
Every chain of calls has to end somewhere; here it ends when the exponent reaches 0, since .
Follow the calls down: power(3, 4) → power(3, 3) → power(3, 2) → power(3, 1) → power(3, 0).
Each call lowers e by 1, so the input moves steadily toward the base case and the chain must stop.
Return back up: power(3, 0) = 1, power(3, 1) = 3 × 1 = 3, power(3, 2) = 3 × 3 = 9, power(3, 3) = 3 × 9 = 27, power(3, 4) = 3 × 27 = 81.
No multiplication happens on the way down; each paused call finishes only after the call below it returns.
Count the calls: e took the values 4, 3, 2, 1 and 0, so 5 calls.
With exponent e the function runs e + 1 times, once for each value down to 0.
Answer: power(3, 4) returns 81 after 5 calls.
Takeaway: Trace recursion in two passes: calls going down to the base case, then results coming back up.