Recursion

Quiz: counts toward finishing the lesson. Check: just for practice.

Introduction

A recursive function is a function that calls itself. Each time it calls itself, a separate copy is created that has its own values for its parameters and variables. If every copy created another copy, the recursion would never end and the computer would run out of memory. So every recursive function needs at least one base case. A base case is a case where the function doesn't call itself.

Let's look at a common first example of recursion:

The if statement checks whether num is equal to zero. This is the base case. If it's true, the function does not call itself. Otherwise, it calls itself, multiplies the return value by num, and returns the result. We could also write it like this:

The else can be left out because if the condition is true, return 1 runs and the function ends before it reaches the recursive call. The other examples in this lesson use this style.

The Call Stack

When a recursive function runs, several copies of it are active at once, but only the most recent one is executing. The others are paused, waiting for a result. When a recursive call is made, the computer saves its place in the current copy so it can come back later, then starts a new copy. It saves that place on the call stack, which keeps track of all active function calls. Watch the video "Flow of execution example for recursion" to see how this works.

def mystery(n):
    if n == 0:
        return 0
    return mystery(n - 1) * 2 + n

x = mystery(3)
y = mystery(1)

More examples

Here's a recursive function that finds the greatest common divisor of two integers:

The base case is when b evenly divides a, in which case b is the greatest common divisor. Otherwise we make a recursive call, passing b for a and a % b for b. The function just returns whatever the recursive call returns, with no extra work.

Here's a recursive function that computes the hailstone sequence starting from a given number and counts how many steps it takes to reach 1:

Here the base case is when the sequence arrives at 1. There are two recursive cases: one if num is even and one if it is odd. We add 1 to the return value, since the current copy of hailstone takes one more step to reach 1 than the recursive call does. For example, if we start at 3, the sequence goes: 3, 10, 5, 16, 8, 4, 2, 1. Once we know how many steps it takes to go from 10 to 1, we add 1 more step to get the number of steps from 3 to 1.

Writing a Recursive Function

Recursion can feel like magic, because you're writing a function that calls the function you're still writing. The general strategy is to find a way to break the problem into a smaller problem of the same kind, plus a bit of work at the current level.

• In the factorial example, num! is equal to (num-1)! multiplied by num. The smaller problem of the same kind is (num-1)!, and multiplying by num is the bit of work at the current level.
• In the gcd example, the gcd of a and b is the same as the gcd of b and a % b, which is a smaller problem of the same kind. No additional work at the current level is needed.
• In the hailstone sequence example, the smaller problem of the same kind is counting how many steps it takes to get from the next number in the sequence to 1. The bit of work at the current level is adding 1 to that result.

Quizzes

def build_up(n):
    if n == 0:
        return ""
    return build_up(n - 1) + str(n)

def build_down(n):
    if n == 0:
        return ""
    return str(n) + build_down(n - 1)

x = build_up(3)
y = build_down(3)