Basic

What recursion is

A function is recursive when it calls itself. Recursion solves a problem by solving a smaller version of the same problem, until the version is small enough to answer directly.

What you will see

About 2 min of reading

Try It

Write and run a recursive function.

Count down from 3.

def countdown(n): if n == 0: return 0 return countdown(n - 1) print(countdown(3))

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

What it prints

Add up to 4.

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

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

What it prints

Factorial of 5.

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

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

What it prints

120

Length of a list.

def length(a): if not a: return 0 return 1 + length(a[1:]) print(length([1, 2, 3]))

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

What it prints

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 recursive function calls itself on a smaller input, and a base case answers the smallest input directly so the calls end.

1 call with smaller input

↓

2 reach the base case

↓

3 answer the base case

↓

4 return back up the chain

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

if n == 0: sets nothing on screen

return 0 sets nothing on screen

return countdown(n - 1) sets nothing on screen

print(countdown(3)) 0

Why this works

Two parts always

Every recursive function has a base case that answers without recursing, and a recursive case that calls a smaller version. Missing either breaks it.

Smaller each time

The recursive call must move toward the base case. If the input does not shrink, the calls never end.

Examples

A function that calls itself

def countdown(n):
    if n == 0:
        return 0
    return countdown(n - 1)
print(countdown(3))

countdown calls countdown with a smaller number. Each call is one step closer to zero.

The smaller problem

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

add_up(4) is 4 plus add_up(3). The same function handles a smaller input.

Base case answers directly

def f(n):
    if n == 0:
        return 1
    return f(n - 1)
print(f(0))

At zero the function returns without calling itself. That is the answer for the smallest case.

Factorial

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

fact(5) is 5 times fact(4). The chain of calls multiplies down to one.

One step smaller

def steps(n):
    if n <= 0:
        return 0
    return 1 + steps(n - 1)
print(steps(6))

Each call reduces n by one. The count of calls equals the starting n.

Recursion needs a stop

def bad(n):
    return bad(n)

With no base case the function calls itself forever. The program crashes on a stack overflow.

Trust the smaller call

def length(a):
    if not a:
        return 0
    return 1 + length(a[1:])
print(length([1, 2, 3]))

Assume length of a shorter list works. Add one for the head. That trust is the whole method.

Base case first

def g(n):
    if n <= 1:
        return n
    return g(n - 1)
print(g(1))

Check the base case before the recursive call. Order of the checks decides when it stops.

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.

Next Lesson

The base case

The base case →