Advanced

Mutual recursion

Mutual recursion is two functions that call each other. It splits a decision into two small functions, each handling one case, instead of one tangled function.

What you will see

False

About 3 min of reading

Try It

Run a mutual recursion.

Even of 4.

def even(n): if n == 0: return True return odd(n - 1) def odd(n): if n == 0: return False return even(n - 1) print(even(4))

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

What it prints

True

Odd of 3.

def even(n): if n == 0: return True return odd(n - 1) def odd(n): if n == 0: return False return even(n - 1) print(odd(3))

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

What it prints

True

Even of 0.

def even(n): if n == 0: return True return odd(n - 1) def odd(n): if n == 0: return False return even(n - 1) print(even(0))

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

What it prints

True

Even of 7.

def even(n): if n == 0: return True return odd(n - 1) def odd(n): if n == 0: return False return even(n - 1) print(even(7))

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

What it prints

False

Data Flow

Mutual recursion is two or more functions calling each other, each handling one case. Every function in the group needs a base case.

1 function A calls B

↓

2 function B calls A

↓

3 each has a base

↓

4 hand-off ends at base

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 even(n): sets nothing on screen

if n == 0: sets nothing on screen

return True sets nothing on screen

return odd(n - 1) sets nothing on screen

def odd(n): sets nothing on screen

if n == 0: sets nothing on screen

return False sets nothing on screen

return even(n - 1) sets nothing on screen

print(even(4)) True

Why this works

Split the cases

When a decision alternates between two shapes, two functions calling each other read better than one with a flag.

Both need a base

Every function in a mutual group needs its own base case. A missing base turns the hand-off into an endless loop.

Examples

Even and odd

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(even(4))

even calls odd and odd calls even. Each handles one case and hands off.

Two small rules

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(odd(3))

The pair reads as two facts. Together they decide any count.

Parse by pairs

def is_expr(t, i):
    return is_term(t, i)
def is_term(t, i):
    return i < len(t)
t = "a+b"
print(is_term(t, 0))

A grammar rule calls another rule. Mutual recursion mirrors the rules.

Base in each

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(even(0))

Both functions need a base at zero. Missing one makes the hand-off loop.

State machine

def read_a(s, i):
    if i >= len(s):
        return True
    if s[i] == "a":
        return read_b(s, i + 1)
    return read_b(s, i)
def read_b(s, i):
    return i >= len(s)
print(read_a("ab", 0))

Each state is a function that moves to the next. Mutual recursion walks the states.

Clearer than one loop

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(even(7))

Two named functions beat one function with a flag. The names carry the meaning.

Same stack cost

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(even(2))

Mutual recursion stacks frames just like self-recursion. The depth still counts.

Each call is small

def even(n):
    if n == 0:
        return True
    return odd(n - 1)
def odd(n):
    if n == 0:
        return False
    return even(n - 1)
print(odd(1))

Each function does one check and one hand-off. The split keeps both tiny.

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.

← Backtracking

Previous Lesson

Backtracking

Next Lesson

Tail recursion and loops

Tail recursion and loops →