Recursion: a function that calls itself

Read these first if they are new to you

Reading Python Basic

The idea in one paragraph

A recursive function solves a problem by calling itself on a smaller version of the same problem. It has two parts. The base case is an input small enough to answer directly, such as an empty list. The recursive case handles one piece and passes the rest to a new call of the same function. Each call waits for the calls it makes, so the newest unfinished call always finishes first. The calls stop only if every chain of calls reaches the base case.

A recursive function answers the smallest case directly and hands the rest to itself

Take the job of adding up a list. The sum of [4, 7, 1] is 4 plus the sum of [7, 1]. That second job is the same problem on a shorter list. Keep shortening, and you reach the empty list, whose sum is 0 with no work at all.

A function that calls itself is recursive, and the technique is called recursion. The function total below writes the idea down. It uses the first value, xs[0], and the slice xs[1:], which holds everything after the first value.

total.py

def total(xs):
    if len(xs) == 0:               # base case: an empty list
        return 0
    return xs[0] + total(xs[1:])   # recursive case: first value plus the total of the rest

print(total([4, 7, 1]))
print(total([]))

12
0

Line 2 tests for the base case, and line 3 answers it without calling anything. Line 4 is the recursive case. It calls total on a list that is one value shorter, so each call moves one step closer to the empty list.

Worked example: total([4, 7, 1]) by hand

Follow the code line by line. Each step does one thing.

[4, 7, 1] is not empty, so the answer is 4 + total([7, 1]). This call waits.
[7, 1] is not empty, so its answer is 7 + total([1]). This call waits too.
[1] is not empty, so its answer is 1 + total([]). A third call waits.
[] is empty: the base case. total([]) returns 0.
total([1]) can now finish: 1 + 0 = 1.
total([7, 1]) finishes: 7 + 1 = 8.
total([4, 7, 1]) finishes: 4 + 8 = 12, which the snippet printed.

Steps 1 to 4 go down to the base case, and no addition happens on the way down. Steps 5 to 7 come back up, and each one does one addition. Each call here makes only one call, so the last call to start is the first to finish.

Your turn. The factorial of a whole number n, written n!, is 1 × 2 × … × n. So 3! = 1 × 2 × 3 = 6, and by the usual convention 0! = 1. This function computes it:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Trace factorial(3) the same way. Which calls does it make, and what does each one return?

Answer

On the way down it calls factorial(2), then factorial(1), then factorial(0), the base case, which returns 1. On the way back up, factorial(1) returns 1 × 1 = 1, factorial(2) returns 2 × 1 = 2, and factorial(3) returns 3 × 2 = 6. That matches 3! = 6.

Each unfinished call waits on a stack until the call it made returns

When total([4, 7, 1]) reaches line 4, it cannot add yet, because it needs total([7, 1]) first. So it pauses. Python keeps the paused call, with its own xs and its place in the code. The new call gets a separate xs of its own, so the calls never overwrite each other's list.

Python keeps the unfinished calls in a call stack. Each new call goes on the stack, and a call leaves it when it returns. So the newest unfinished call always finishes first.

At its deepest, total([4, 7, 1]) has four unfinished calls

Down, then back up. Read the blue arrows first: each call makes the next one and waits. The bottom call is the base case, and it answers without a call. Then read the green arrows from the bottom: each call finishes its addition and hands the result to the call above it. Here the newest call is drawn at the bottom.

The calls stop only if every chain of calls reaches the base case

Recursion needs two things to finish. There must be a base case, and each recursive call must move closer to it. total has both: each call gets a list that is one value shorter, so any list reaches the empty list.

factorial has both only for some inputs. It assumes that n is a whole number that is 0 or more. Call factorial(-1), and the calls go to −2, −3 and on, and never meet n == 0. A call such as factorial(2.5) skips past 0 the same way: 1.5, 0.5, −0.5.

Python does not let such a chain grow forever. It counts the unfinished calls, and when the count passes a limit, it stops the program with an error called RecursionError. The standard sys library, which comes with Python, reports the limit:

limit.py

import sys

print(sys.getrecursionlimit())

Deep recursion fails in Python even when the logic is right

The limit counts every unfinished call, not only calls in a chain that never ends. Run as a script on Python 3.12.3, total handled a list of 998 values and stopped with RecursionError on a list of 999 values. The 1000 printed above is the value on that Python; another version or setup may give another value. The function sys.setrecursionlimit raises the limit, but Python's documentation warns that a limit set too high can crash Python. For a chain of thousands of steps, use a loop.

A loop can do the same job, and recursion fits problems that split into smaller copies

Any of these sums could also be written with a for-loop, and Python's built-in sum([4, 7, 1]) also gives 12. The loop keeps a running total in one name, and it makes no chain of calls:

total_loop.py

def total_loop(xs):
    result = 0
    for x in xs:
        result = result + x
    return result

print(total_loop([4, 7, 1]))

For a flat list, the loop is the plainer choice. Recursion pays off when the smaller pieces of a problem are problems of the same kind, and especially when one call needs two or more smaller calls. A function that builds a KD-tree, for example, splits its points at the middle point and calls itself once for each side. The KD-tree unit shows such a function, build.

This page's total copies the list at every call

The slice xs[1:] makes a new list. For a list of n values, the calls copy (n − 1) + (n − 2) + … + 1 + 0 values, which is n × (n − 1) / 2 in all: 124,750 copies for a list of 500 values. The loop copies none. A faster recursive version passes a position in the list instead of a shorter copy. This page keeps the slice because it shows the smaller problem plainly.

Check yourself

Name the two parts that every recursive function needs, and say what each one does.

Answer
A base case, which answers a small input directly without calling the function again, and a recursive case, which calls the function on a smaller input. The recursive case must move every input closer to the base case, or the calls never stop.
What does this print? How many calls of count are unfinished at the deepest point?
```
def count(xs):
    if len(xs) == 0:
        return 0
    return 1 + count(xs[1:])

print(count([9, 9, 9]))
```
Answer
It prints 3: each non-empty list adds 1, and the empty list adds 0. At the deepest point there are four unfinished calls, on lists of 3, 2, 1 and 0 values. A list of n values always gives n + 1 calls, because the empty list needs a call of its own.
What happens when you call factorial(-1) with the function on this page? How could the caller avoid it?

Answer
The calls go to −2, −3 and on, and never reach the base case n == 0. Python stops the program with a RecursionError once the unfinished calls pass its limit. The function assumes a whole number that is 0 or more, so the caller should pass only such numbers, since the factorial of a negative number is not defined.

Go further

Optional background.

Think Python, chapter 5: Conditionals and Recursion Allen B. Downey Book Intermediate

Sections 5.8 to 5.10 build a countdown function, draw its calls as a stack diagram, and show the RecursionError that infinite recursion causes.
Composing Programs, 1.7: Recursive Functions John DeNero Book Intermediate

Section 1.7.1 compares a recursive factorial with a loop version, and section 1.7.4 covers functions that call themselves twice, such as one for the Fibonacci numbers.

Where this shows up

No unit or explanation builds on this one yet.