Recursion

A recursive function is a function that calls itself. Each time, it works on a smaller version of the same problem. It also needs a base case. The base case is the point where the function returns an answer without calling itself again.

def sum_to(number):
    if number == 0:
        return 0
    return number + sum_to(number - 1)

print(sum_to(4))

Output:

10

Each call makes number one smaller. Each call also waits for the answer from the call below it:

sum_to(4) = 4 + sum_to(3)
          = 4 + 3 + sum_to(2)
          = 4 + 3 + 2 + sum_to(1)
          = 4 + 3 + 2 + 1 + sum_to(0)
          = 4 + 3 + 2 + 1 + 0

When number reaches 0, the base case returns 0 without another call. Then the waiting additions finish, from the bottom up, and the first call returns 10.

If the function can never reach its base case, the calls do not stop on their own. Python allows about a thousand calls inside each other. Then it stops the program with a traceback that ends in RecursionError: maximum recursion depth exceeded.

For simple counting, a loop is often clearer. Recursion is most useful when the data itself is nested, such as folders inside folders.

In the exercise, complete the base case and the recursive step.