Advanced

Tail recursion and loops

When the recursive call is the last action, the call can be replaced by a loop. Some languages do that for you; Python does not, so a deep tail recursion still overflows.

What you will see

1275

About 3 min of reading

Try It

Turn a tail recursion into a loop.

Tail sum with acc.

def loop(n, acc): if n == 0: return acc return loop(n - 1, acc + n) print(loop(4, 0))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Loop equivalent.

n, acc = 4, 0 while n != 0: acc += n n -= 1 print(acc)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Tail factorial.

def fact(n, acc): if n == 0: return acc return fact(n - 1, n * acc) print(fact(5, 1))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

120

Loop sum to 50.

total, n = 0, 50 while n > 0: total += n n -= 1 print(total)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

1275

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A tail call is the last action with nothing added after it. It maps to a loop, but Python keeps the frames so deep tail recursion still overflows.

1 call is last action

↓

2 state carried in argument

↓

3 maps to a loop

↓

4 Python keeps frames

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def loop(n, acc): sets nothing on screen

if n == 0: sets nothing on screen

return acc sets nothing on screen

return loop(n - 1, acc + n) sets nothing on screen

print(loop(4, 0)) 10

Why this works

Tail position is the rule

A call is in tail position only if nothing happens after it returns. Adding to the result breaks the tail.

Python has no tail calls

Python keeps a frame for every call, so tail recursion still uses stack. Write a loop for large repetition.

Examples

Tail call is last

def loop(n, acc):
    if n == 0:
        return acc
    return loop(n - 1, acc + n)
print(loop(4, 0))

The call is the whole return, with nothing added after. That is the tail position.

Loop equivalent

n, acc = 4, 0
while n != 0:
    acc += n
    n -= 1
print(acc)

The tail recursion becomes a while loop with the same two variables. Same result.

Python keeps frames

def loop(n, acc):
    if n == 0:
        return acc
    return loop(n - 1, acc + n)
print(loop(3, 0))

Python does not reuse the tail frame, so this still nests. A big n overflows.

Accumulator carries state

def loop(n, acc):
    if n == 0:
        return acc
    return loop(n - 1, acc + n)
print(loop(10, 0))

The running answer travels down as an argument. Nothing waits on a return.

Not tail if added after

def s(n):
    if n == 0:
        return 0
    return n + s(n - 1)
print(s(4))

Adding n after the call means work waits on the return. That is not tail recursion.

Convert by hand

def fact(n, acc):
    if n == 0:
        return acc
    return fact(n - 1, n * acc)
print(fact(5, 1))

Carry the product in acc to make the call tail. Then a loop can replace it.

Tail avoids deep stack

def loop(n, acc):
    if n == 0:
        return acc
    return loop(n - 1, acc + n)
print(loop(50, 0))

In a language with tail calls this uses constant stack. In Python it still grows.

Loop is the safe form

total, n = 0, 50
while n > 0:
    total += n
    n -= 1
print(total)

In Python, write the loop when the count is large. The tail recursion is for clarity only.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Mutual recursion

Previous Lesson

Mutual recursion

Next Lesson

Top-down versus bottom-up

Top-down versus bottom-up →