Running a Recursion to the Floor

A recursive sum computes the total from zero up to a number by one rule — the sum up to x equals x plus the sum up to x minus one — with zero as the base case.

Ask for the sum up to 10. The rule answers: 10 plus the sum up to 9. That call answers: 9 plus the sum up to 8. The chain keeps descending — 8, 7, 6, 5, 4, 3, 2, 1 — each call holding its number and waiting, until the sum up to 0 hits the base case and answers 0 directly, no call needed. Now the chain unwinds in reverse: 1 plus 0 is 1; 2 plus 1 is 3; 3 plus 3 is 6; then 10, 15, 21, 28, 36, 45 — and at the top, 10 plus 45 is 55. Eleven answers, one rule, and the base case did the only direct work.