A function that calls itself

Recursion is handing a problem over to a smaller copy of the same problem. You can count a 5-step staircase like this: one step, plus the 4-step staircase that is left. The function does a small part of the job and calls itself for the rest.

1def total(n):
2    if n == 0:
3        return 0
4    return n + total(n - 1)

There are two parts and both are required. The base case (n == 0) answers directly and stops the chain. The step makes the problem smaller (n - 1) and adds its own share to the smaller answer.

When you read it, write the calls one under the other: total(3) waits, total(2) waits, total(1) waits, total(0) returns 0; then the answers add up from the bottom: 1, 3, 6. Every call carries its own n; they do not get mixed up.

Tasks