Tail calls in Python

Why this matters

Many recursive functions do their work on the way down, then return. Some of them do nothing after the recursive call returns. For those, the call stack keeps a frame that has nothing left to do. Some languages notice this and reuse the frame, so the recursion runs in constant stack space, the same as a loop. Python does not do this. A function that recurses 100000 times in Python fails with RecursionError, even if the function looks like a simple loop.

This lesson shows how to spot the calls that can be turned into a loop, how to rewrite them by hand, and what goes wrong when you do not. The flood fill lesson earlier in this module showed the stack limit with a search. Here the limit is hit by a plain sum.

What a tail position is

A call is in tail position when the value it returns is the value the enclosing function returns, with nothing done to it afterwards. The word "tail" means the last step of the function.

A small way to test this: after the call returns, does the function still have work to do? If yes, the call is not in tail position. If the function only passes the answer up, it is.

These fragments show the difference. They are parts of functions, so they are not complete programs:

def a(n: int) -> int:
    if n == 0:
        return 0
    return a(n - 1)  # tail: the answer of a(n - 1) is returned as it is
 
 
def b(n: int) -> int:
    if n == 0:
        return 0
    return 1 + b(n - 1)  # not tail: after the call returns, 1 is added
 
 
def c(n: int) -> None:
    if n == 0:
        return
    c(n - 1)  # not tail: the next line still runs after the call
    print(n)

In a, the call is the last thing that happens, so it is a tail call. In b, the function adds 1 after the call, so the frame has to wait. In c, a line runs after the call, so the frame has to wait too. The output of c(3) is 1, 2 and 3 on separate lines, printed while the calls return, which is the reverse order of the calls.

Only the first kind can be turned into a loop by the method in this lesson, because nothing is left to do after the call.

Why a tail call can become a loop

Look at what happens to the call stack in a(3). The first call waits for a(2), which waits for a(1), which waits for a(0). Then a(0) returns 0, and each of the other calls returns that value unchanged.

The waiting frames are useless. The call a(2) does nothing with its own number once it has called a(1). So the same work can be done by one frame that keeps changing its number: set n to 2, then 1, then 0, and return when n is 0. That single frame is a loop.

The transformation that does this is called tail call elimination. Some language systems do it for you. In Python you do it by hand.

The accumulator

Many useful functions are not tail calls at first. Consider the factorial of a number. The factorial of 5 is 5 times 4 times 3 times 2 times 1, which is 120. A direct recursive version looks like this:

def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

The call factorial(n - 1) is followed by a multiplication, so it is not a tail call. The fix is to carry the running product in a second parameter, called an accumulator. The accumulator holds the work done so far. Each call multiplies the product before passing it on, so the answer is ready when the recursion reaches the base case.

def factorial_acc(n: int, acc: int) -> int:
    if n <= 1:
        return acc
    return factorial_acc(n - 1, n * acc)

Start it with factorial_acc(5, 1). The call factorial_acc(5, 1) calls factorial_acc(4, 5), which calls factorial_acc(3, 20), then factorial_acc(2, 60), then factorial_acc(1, 120). The last call hits the base case and returns 120. Nothing is left to do in any frame, so the call is now in tail position.

The base case changed as well. It returns acc, not 1, because acc holds everything multiplied so far.

Rewriting a tail call as a loop

Once the call is in tail position, the loop version follows a fixed pattern:

1. Make a local variable for the accumulator and give it the starting value.
2. Turn the base case into the loop condition, so the loop runs while the base case is not yet true.
3. Inside the loop, do the work that the accumulator call did, and update the parameters the way the recursive call did.
4. After the loop, return the accumulator.

Here is the loop for the factorial:

def factorial_loop(n: int) -> int:
    acc = 1
    while n > 1:
        acc = n * acc
        n = n - 1
    return acc

The parameter n is a local name inside the function, so assigning to it is allowed. Changing n does not change the caller's variable, because assigning to n only changes the local name inside the function. The loop does not need to change the caller's data here.

First example: a sum that becomes a loop

The program below sums the numbers from 1 to n with a tail-recursive function, then with a loop. It also shows the stack limit. Each try block catches the RecursionError, which Python raises when the chain of waiting calls is too long, so the rest of the program can run.

The output is:

sum_to(10, 0) = 55
sum_to_loop(10) = 55
factorial(5) = 120
factorial_acc(5, 1) = 120
sum_to_loop(100000) = 5000050000
sum_to(900, 0) = 405450
sum_to(990, 0) = 490545
sum_to(1000, 0) failed: RecursionError
sum_to(100000, 0) failed: RecursionError
factorial_acc(30, 1) = 265252859812191058636308480000000
math.factorial(30) = 265252859812191058636308480000000

The loop handles 100000 numbers with no trouble, because it uses one frame. The tail-recursive sum_to fails at about 1000 even though the call is in tail position, because Python keeps every call on the stack. The next section explains why.

The math module has a factorial function, which you should use in real code. The line math.factorial(30) agrees with the recursive versions, and the accumulator version is there to show the pattern.

Second example: several tail calls and loops

The next program covers several common shapes: a greatest common divisor, a search through a list, and a power. Each has a tail-recursive version and a loop version, and the output shows that both agree.

The greatest common divisor, or gcd, of two numbers is the largest number that divides both. Euclid's method says that the gcd of a and b equals the gcd of b and the remainder of a divided by b. The call stops when the second number is 0. The math module has math.gcd, which you should use in real code.

The search returns the index of the first matching value, or -1 when there is none. The power function multiplies base by itself exp times.

The output is:

gcd(48, 18) = 6
gcd_loop(48, 18) = 6
index_of(1) = 2
index_of_loop(1) = 2
index_of(9) = -1
index_of_loop(9) = -1
power(2, 10, 1) = 1024
power_loop(2, 10) = 1024
sum_array = 20
sum_array_loop = 20
factorial_wrong_base(5, 1) = 0
gcd(0, 5) = 5 5

Two of these need a closer look. In the gcd loop, the line nxt = a % b must come before the two assignments. If you wrote a = b first, the remainder would be computed from the new a, and the answer would be wrong. The order of the three lines is the order the recursive call used when it passed the new values in. Python lets you write a, b = b, a % b on one line, which does the same thing in one step, because the right side is worked out before either name changes.

In the list search, the tail-recursive version takes the index as a parameter. Its loop version uses a local variable i for the same job. The function always has the list and the value, and the index is the only thing that changes between calls, which is why the search fits this shape. For a plain loop over every item, for i in range(len(arr)) is shorter than the while form, and it is the style to use in practice.

The power example shows an accumulator that is a multiplication. Start with acc as 1, and each call multiplies it by base. A loop that does the same is the simplest form of the pattern.

Why Python does not remove tail calls

Python does not promise to remove tail calls, and it does not remove them. The sum_to call above failed at about 1000 for that reason. The Python developers have chosen not to add this feature. One reason is that every call keeps its own frame, and a traceback is a list of those frames. When an error is raised, the traceback lists each function that was running, one line per call. If the interpreter reused frames for tail calls, the traceback would show fewer calls than the code made, which would make debugging harder.

Some other languages make a different choice. Scala has an annotation called @tailrec, which makes the compiler check that a function is tail recursive and refuse to compile it otherwise. Python has nothing like that. A Python function that is tail recursive is still an ordinary recursive call to the interpreter, and the programmer makes the change to a loop.

Python has a setting that changes the limit. sys.setrecursionlimit raises the number of frames allowed, and the earlier lessons showed that it defaults to 1000. Raising it is risky, because the interpreter's own stack space is finite too, and a limit set too high can crash the interpreter. For long inputs, write the loop.

The practical result is simple. In Python, when a recursion can be written as a tail call and the input can be large, write it as a loop. When the input is small, the tail-recursive form can be easier to read.

Common mistakes

Expecting a tail call to be safe

A tail call looks like a loop, but it is still a call. This program has only the one function.

def sum_to(n: int, acc: int) -> int:
    if n == 0:
        return acc
    return sum_to(n - 1, acc + n)
 
 
print(sum_to(10000000, 0))

The output is:

Traceback (most recent call last):
  File "uncaught.py", line 7, in <module>
    print(sum_to(10000000, 0))
          ~~~~~~^^^^^^^^^^^^^
  File "uncaught.py", line 4, in sum_to
    return sum_to(n - 1, acc + n)
  File "uncaught.py", line 4, in sum_to
    return sum_to(n - 1, acc + n)
  File "uncaught.py", line 4, in sum_to
    return sum_to(n - 1, acc + n)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The traceback repeats the same line until the limit. Each repeated line is one call still on the stack. If you see this error with a function that calls itself on its last line, rewrite it as a loop.

Putting work after the call

A common error is to write the accumulator update after the call, which makes the call not a tail call and gives the same error as a plain recursion. An example is return n + sum_to(n - 1, 0), where the result of the call is still changed after it returns. The accumulator must be updated before the call and passed in.

A wrong base case value

The base case must return the accumulator. Returning a fixed number is a common slip. The factorial_wrong_base function in the second example returns 0 at its base case, so the final answer is 0 for every input. The output line factorial_wrong_base(5, 1) = 0 shows the result. Look at the base case first when a tail call gives a result that is always the same.

Forgetting to update the loop variable

When a tail call is turned into a loop, the loop must change the variable the condition checks. If the update is missing, the loop never ends. This version of a list search has no i = i + 1:

def index_of_loop(arr: list[int], value: int) -> int:
    i = 0
    while i < len(arr):
        if arr[i] == value:
            return i
    return -1
 
 
print(index_of_loop([4, 7, 1, 8], 1))

With [4, 7, 1, 8] and the value 1, the first pass checks index 0, finds it is not 1, and loops again with the same i. The program never prints anything and never stops. Run it under timeout 5 when you test a loop you are not sure about. The timeout command stops the program after five seconds, and the shell then reports exit code 124, which is the code timeout uses when it stops a command. The fix is one line, i = i + 1, at the end of the loop body. Note that Python has no i++ operator, so the update must be written as i = i + 1 or i += 1.

Practice

Exercise 1

Say whether the call in each function is a tail call, and say why.

def p(n: int) -> int:
    if n == 0:
        return 1
    return n * p(n - 1)
 
 
def q(n: int, acc: int) -> int:
    if n == 0:
        return acc
    return q(n - 1, acc + n)
 
 
def r(n: int) -> None:
    if n == 0:
        return
    print(n)
    r(n - 1)

Show the answer

In p, the call p(n - 1) is not a tail call, because the result is multiplied by n after the call returns. In q, the call q(n - 1, acc + n) is a tail call, because its value is returned as it is. In r, the call r(n - 1) is a tail call, because it is the last line and nothing runs after it. Its line print(n) runs before the call, so it does not change the tail position.

Exercise 2

Write a function count_digits(n, count) that returns how many digits n has, using a tail call with an accumulator. Then write the loop version. The number 90210 has 5 digits, and the number 7 has 1 digit. Assume n is 0 or more.

Show the answer

def count_digits_tail(n: int, count: int) -> int:
    if n < 10:
        return count + 1
    return count_digits_tail(n // 10, count + 1)
 
 
def count_digits_loop(n: int) -> int:
    count = 0
    while True:
        count = count + 1
        n = n // 10
        if n == 0:
            break
    return count
 
 
print(count_digits_tail(90210, 0))  # 5
print(count_digits_loop(90210))  # 5
print(count_digits_loop(0))  # 1

The loop uses while True with a break so that it runs once even when n is 0, which gives the answer 1 for 0. A plain while n > 0 loop would give 0 for that input.

Exercise 3

Write a function reverse(s, i, acc) that returns the characters of s in reverse order, as a tail call. Then write reverse_loop(s) that does the same with a loop. The reverse of abc is cba, and the reverse of an empty string is an empty string.

Show the answer

def reverse(s: str, i: int, acc: str) -> str:
    if i == len(s):
        return acc
    return reverse(s, i + 1, s[i] + acc)
 
 
def reverse_loop(s: str) -> str:
    acc = ""
    for ch in s:
        acc = ch + acc
    return acc
 
 
print(reverse("abc", 0, ""))  # cba
print(reverse_loop("abc"))  # cba
print(repr(reverse_loop("")))  # ''

The expression s[i] + acc puts a character in front of the string, so each new character goes before the ones already collected. Python's + joins two strings, and it makes a new string each time, which costs time for long inputs. The "".join method is faster for long results.

Exercise 4

The loop below is meant to count how many times value appears in arr. It has a bug that makes it run forever. Find the bug, then fix it. Test the fixed version under timeout 5.

def count_value(arr: list[int], value: int) -> int:
    count = 0
    i = 0
    while i < len(arr):
        if arr[i] == value:
            count = count + 1
    return count

Show the answer

The loop never changes i, so the condition i < len(arr) stays true and the loop runs forever. The fix is to add i = i + 1 at the end of the loop body:

def count_value(arr: list[int], value: int) -> int:
    count = 0
    i = 0
    while i < len(arr):
        if arr[i] == value:
            count = count + 1
        i = i + 1
    return count
 
 
print(count_value([4, 7, 1, 8], 1))  # 1

The fixed function returns 1 for [4, 7, 1, 8] and the value 1. It is the same kind of mistake as the search example in the common mistakes section. A for loop over arr avoids this mistake, because Python moves to the next item for you.

Summary

• A call is in tail position when the function returns its value with no work done after the call.
• A tail call can be rewritten as a loop by moving the work into an accumulator parameter and then into a local variable.
• The base case of an accumulator version returns the accumulator, not a fixed value.
• Python does not remove tail calls, so a tail-recursive function still uses a frame for each call and raises RecursionError on large input.
• When the input can be large, write the recursion as a loop, and check that the loop variable changes on every pass.