A Beginner's Guide to Recursion

Recursion is a function solving a problem by calling itself on a smaller copy of that same problem. Once it clicks, trees, graphs, backtracking and dynamic programming all become much easier to reason about.

The Nesting Dolls Analogy

Picture a set of wooden nesting dolls on your desk. You want to know what is painted on the very last, smallest doll, but all you can see is the outer one. The only move available is to open the doll in front of you.

So you open it, and inside sits another doll.

1. Some dolls are solid and cannot be opened any further.
2. Every other doll holds a slightly smaller doll inside.

You keep opening dolls until you reach a solid one. That is recursion.

Base Case

The solid doll. The answer is right there, so there is nothing left to open.

Recursive Case

Any hollow doll. You open it and repeat the same action on the smaller doll inside.

Factorial Example

The factorial of n, written n!, multiplies every whole number from n down to 1. It is a clean first example because each factorial is built from a smaller one.

• 0! is defined as 1
• n! = n * (n - 1)!

To get 4! you need 3!, to get 3! you need 2!, and so on.

Here is how that maps to code.

Base Case

When n is 0 the function returns 1 immediately. Without this line every call would ask for a smaller factorial forever and the program would crash with a stack overflow.

It is the solid doll: the one problem we can answer without any more work.

Recursive Case

For any other n the function returns n * factorial(n - 1).

That single line trusts the smaller call to come back with the right answer, then does one multiplication on top of it. You do not have to trace every call in your head to know the result is correct.

Each call waits on the call stack until the one below it returns. When the base case finally returns 1, the waiting calls finish one by one from the bottom up: 1, then 1, then 2, then 6, then 24.

Checklist for Writing Recursive Functions

• Define the base case first, and make sure it handles the smallest possible input.
• Make every recursive call work on a strictly smaller input.
• Combine the smaller answers into the answer for the current call.
• Trust the recursive call instead of tracing it all the way down.

# Return the factorial of n
def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)

def factorial(n):
    if n == 0:
        return 1

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)