Recursion Explained

A function that calls itself

Most functions call other functions. Recursion is the surprising idea that a function can call itself. It sounds like it should spin forever, but done right it is a clean, powerful way to solve problems that contain smaller copies of themselves.

Here is the everyday intuition. Imagine you are standing in a long queue and want to know your position, but you can only see the person directly in front of you. You ask them, "What is your position?" They do not know either, so they ask the person in front of them, and so on. Eventually the question reaches the very first person, who answers "I am number 1." That answer passes back: the next person is 2, then 3, all the way back to you. Each person solved the same problem by asking a slightly smaller version of it. That is recursion.

This lesson assumes you are comfortable with Functions Explained and ideally Functions That Return Values, since recursion leans heavily on returning a result back up the chain.

The two rules of recursion

Every correct recursive function has exactly two parts:

1. The base case — a simple condition that can be answered without recursing. This stops the chain. (The first person in the queue: "I am number 1.")
2. The recursive case — the function calls itself on a smaller version of the problem, moving closer to the base case each time.

Miss the base case, or fail to shrink the problem, and the calls pile up forever until the program crashes with a stack overflow.

A first example: counting down

def countdown(n):
    if n == 0:            # base case: stop here
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)      # recursive case: smaller problem

countdown(3)

Trace it:

countdown(3)  -> prints 3, then calls countdown(2)
countdown(2)  -> prints 2, then calls countdown(1)
countdown(1)  -> prints 1, then calls countdown(0)
countdown(0)  -> base case: prints "Lift off!" and stops

Each call hands a smaller number to the next, marching steadily toward the base case n == 0. The output is 3 2 1 Lift off!.

The call stack

How does the computer keep track of all these half-finished calls? It uses a call stack — a pile where each new call is placed on top, and only the top one runs at a time. When a call finishes, it is removed and the one beneath it resumes.

Consider a function that returns a value, the factorial. The factorial of n (written n!) is n × (n-1) × ... × 1. It is defined recursively:

factorial(n) = n × factorial(n - 1)
factorial(0) = 1            (base case)

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

print(factorial(4))   # 24

Watch the stack grow as the calls go down, then shrink as the answers come back up:

factorial(4) = 4 * factorial(3)        <- waiting
  factorial(3) = 3 * factorial(2)      <- waiting
    factorial(2) = 2 * factorial(1)    <- waiting
      factorial(1) = 1 * factorial(0)  <- waiting
        factorial(0) = 1               <- base case! returns 1
      factorial(1) = 1 * 1   = 1       <- resumes
    factorial(2) = 2 * 1     = 2       <- resumes
  factorial(3) = 3 * 2       = 6       <- resumes
factorial(4) = 4 * 6        = 24       <- final answer

Notice how the deepest call (factorial(0)) finishes first, and its result flows back up through each waiting call. This "go all the way down, then come back up" pattern is the signature of recursion.

A complete worked example

This program solves a problem that is genuinely awkward with a plain loop: summing a list that may contain lists inside lists, nested to any depth. Recursion handles the unknown depth effortlessly.

def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):   # a list inside the list...
            total += deep_sum(item)  # ...so recurse into it
        else:
            total += item            # base case: a plain number
    return total

nested = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(deep_sum(nested))   # 45

Reading the code: deep_sum walks through each item. If the item is an ordinary number it just adds it — that is the base case. If the item is itself a list, the function calls itself on that inner list and adds whatever comes back. Because each recursive call works on a smaller, shallower piece, the process always reaches plain numbers and stops. The total of 1 through 9 is 45, gathered from every level of nesting without you ever knowing how deep it went.

Try it yourself

1. Count up instead. Rewrite countdown as countup(n) that prints 1 2 3 ... n. Hint: print after the recursive call, and make the base case n == 0 do nothing.
2. Sum a range. Write sum_to(n) that returns 1 + 2 + ... + n recursively. Base case: sum_to(0) returns 0.
3. Break it on purpose. Remove the base case from factorial and run factorial(5). Read the RecursionError Python prints — that is the stack overflow protecting you.

Challenge: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ..., where each number is the sum of the previous two. It has two base cases: fib(0) = 0 and fib(1) = 1, and the recursive case fib(n) = fib(n-1) + fib(n-2). Write it and print the first ten values. Then think about why this version gets slow for large n — it recomputes the same calls many times, a perfect motivation for the loops and lists you met in JavaScript Loops and Arrays or Python's own list tools.