A function that calls itself

You know that a function can call another function. A function can also call itself. That's called recursion, and it's another way to repeat something.

Just as a while loop needs a way out, a recursive function needs a way to stop. This one calls itself every time, so it never ends on its own:

def count_up(n):
    count_up(n + 1)


count_up(1)

Traceback (most recent call last):
  File "main.py", line 5, in <module>
    count_up(1)
    ~~~~~~~~^^^
  File "main.py", line 2, in count_up
    count_up(n + 1)
    ~~~~~~~~^^^^^^^
  File "main.py", line 2, in count_up
    count_up(n + 1)
    ~~~~~~~~^^^^^^^
  File "main.py", line 2, in count_up
    count_up(n + 1)
    ~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Every call starts a new call before it has finished. Python keeps track of all the unfinished calls, and when there are about a thousand of them, it gives up with a RecursionError. The traceback shows the same line a few times and then says how many more times it was repeated.

The base case

A recursive function that works has two parts:

• A base case: a situation so simple that the function handles it without calling itself. That's where the calls stop.
• A recursive case: the function calls itself with a smaller problem, one step closer to the base case.

def countdown(n):
    if n == 0:
        print("Liftoff!")
    else:
        print(n)
        countdown(n - 1)


countdown(3)

3
2
1
Liftoff!

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0). That's the base case: it prints Liftoff! and doesn't call itself, so the calls end there. Each call has its own n: while countdown(2) runs, the n of countdown(3) is still 3.

Each call makes n one smaller, so it gets to 0 sooner or later. But what about countdown(-1)? Then n goes -2, -3, -4 and never hits 0, and the program ends in a RecursionError. The base case n <= 0 would catch that too.

Recursion that changes a list

A recursive function can also change a list. None of the calls below gets a list of its own: in every call, numbers is another name for powers, the one list of the main program, because a function gets the list itself and not a copy (part 5). So each call finds the numbers that the calls before it appended:

def keep_doubling(numbers, limit):
    if numbers[-1] * 2 <= limit:
        numbers.append(numbers[-1] * 2)
        keep_doubling(numbers, limit)


powers = [1]
keep_doubling(powers, 100)
print(powers)

[1, 2, 4, 8, 16, 32, 64]

Here the base case is hidden: when the next number would go over the limit, the condition is false and the function ends without calling itself. A while loop does the same job:

def keep_doubling(numbers, limit):
    while numbers[-1] * 2 <= limit:
        numbers.append(numbers[-1] * 2)

A solution that repeats with a loop is called iterative, and one where a function calls itself recursive. Here the iterative version is shorter and easier to follow, so it's the better choice. Recursion earns its place when a problem breaks into smaller problems of the same kind: the factorial and binary search in the next steps, and the trees of the next module.