Recursion & the Call Stack

Imagine you are standing between two mirrors that face each other.

You see yourself inside yourself, again and again, and each reflection is a little smaller than the one before. If the reflections did not shrink, the tunnel would feel endless. Recursion is exactly this picture, turned into code.

A function calls itself. But each call must be a little smaller than the last, moving toward a place where it can finally stop. That shrinking is the whole secret, and we are going to build it up slowly.

A function that calls itself

Let us begin with the most ordinary thing in Python — a function that does not call itself.

def greet():
    print("Hello")

greet()

When Python reaches greet(), it steps inside the function, runs the line, and comes back out. A function call is really a small promise: pause here, go do that, then return to this spot.

Now suppose a function calls itself.

def countdown(n):
    print(n)
    countdown(n - 1)

We ask it to count down from 3:

countdown(3)

We might expect 3, 2, 1, 0 and then a stop. Instead Python prints:

3
2
1
0
-1
-2
-3
...

It never stops. Why? Because we never told it where to stop. Every call cheerfully makes another call, one smaller, forever. So a recursive function needs more than the calling-itself part. It needs a place to stop.

The two parts every recursion needs

Every recursion that actually works has exactly two parts.

The base case is the small, easy situation where we already know the answer and make no further calls. The recursive case is where the function calls itself on a smaller version of the problem, stepping one notch closer to the base case.

Here is the countdown again, fixed:

def countdown(n):
    if n == 0:          # base case — stop here
        print("Done")
        return

    print(n)
    countdown(n - 1)    # recursive case — n gets smaller

Now countdown(3) prints:

3
2
1
Done

Watch the number on each call: 3 → 2 → 1 → 0. It is always getting smaller, so it is always heading home. The base case is the doormat at home; the recursive case is each step down the path toward it.

What recursion really is

Now that the idea is in your hands, here is the name and the precise sentence.

Recursion is a way of solving a problem by calling the same function on a smaller version of the same problem, until the problem becomes so small that you can answer it directly.

In one line:

recursion = solve a smaller copy of the same problem + stop at the base case

That sentence would have meant little on the first line of this lesson. It means something now, because you have already watched a countdown shrink its way to zero.

Watching it work: factorial

Let us take a real problem. The factorial of 4, written 4!, is:

4! = 4 × 3 × 2 × 1 = 24

The important thing to notice is that a factorial is built out of a smaller factorial:

4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1

The problem keeps turning into the same kind of problem, only smaller. That is the signal that recursion will fit beautifully.

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

When we call factorial(4), Python first travels down, each call waiting on the next:

factorial(4) = 4 × factorial(3)
factorial(3) = 3 × factorial(2)
factorial(2) = 2 × factorial(1)
factorial(1) = 1

Then, having hit the base case, it travels back up, each waiting call now able to finish:

factorial(1) returns 1
factorial(2) returns 2 × 1 = 2
factorial(3) returns 3 × 2 = 6
factorial(4) returns 4 × 6 = 24

So every recursion has two journeys. It goes down until the base case, then it comes back up carrying the answers. Hold on to that picture — it is the heart of the next section.

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

def list_sum(nums):
    if nums == []:            # base case: nothing left to add
        return 0
    return nums[0] + list_sum(nums[1:])   # add the first, recurse on the rest

print("factorial(4) =", factorial(4))
print("factorial(6) =", factorial(6))
print("sum of [4, 7, 2] =", list_sum([4, 7, 2]))

This prints:

factorial(4) = 24
factorial(6) = 720
sum of [4, 7, 2] = 13

list_sum slices off the first element on every call — [4, 7, 2] becomes [7, 2], then [2], then []. That is three recursive calls before the empty-list base case returns 0, and the partial sums add back up on the way out to give 13.

The call stack: a pile of unfinished work

Where does Python keep all those waiting calls? It keeps them in a pile.

Think of a stack of plates. The last plate you put on top is the first one you take off. Function calls behave the same way: when one function calls another, Python sets the first one aside, waiting, and puts the new call on top. This pile of waiting calls is the call stack.

For factorial(4), the pile grows to four calls deep before a single one finishes. Each call sits there holding its own value of n, waiting for the call above it to hand back an answer. Then the pile unwinds from the top, each call finishing the multiplication it was paused on.

Each call gets its own small box of memory, called a stack frame. The frame stores that call’s value of n, any temporary values, and a note about where to continue once the call below it returns. The call stack is simply how a program remembers work it has paused.

When recursion never comes home

Now we can see clearly why the broken countdown was so dangerous. Consider this:

def bad(n):
    print(n)
    bad(n + 1)

bad(1)

Here n keeps getting bigger, never reaching any base case. The pile of waiting calls grows and grows:

bad(1)
bad(2)
bad(3)
...

At some point Python refuses to pile on more and stops with:

RecursionError: maximum recursion depth exceeded

It is tempting to read that as the real problem. It is not. The real mistake happened earlier — the recursion never moved toward a base case, so the stack could only grow.

Five shapes of recursion

Now that the idea is solid, let us name the shapes recursion can take. They differ only in who calls and when the work happens.

Direct recursion is the kind you have already seen: a function calls itself.

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

Indirect recursion is a circle: one function calls a second, and the second calls the first back.

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

Calling is_even(4) bounces between the two — is_even → is_odd → is_even → is_odd → is_even — but the number shrinks each step, so it still reaches zero and stops.

Head recursion does its work after the recursive call returns. The call comes first; the print waits.

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

head(3) prints 1, 2, 3 — ascending — because each print is paused until the smaller calls below it finish.

Tail recursion does its work before the recursive call, which sits at the very end (the “tail”).

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

tail(3) prints 3, 2, 1 — descending — because each print runs on the way down.

Tree recursion is the interesting one: a single call makes more than one recursive call, so the calls branch like a tree. The classic example is Fibonacci, where each number is the sum of the two before it.

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)   # two calls — the branch

That little + hides a surprisingly expensive habit, and it is worth seeing exactly why.

The repeated-work problem

Look closely at what fib(5) actually asks for:

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)

Notice fib(3) appears twice — once on its own, and again inside fib(4). Each of those re-computes everything beneath it from scratch. Draw the full tree and the waste becomes obvious.

The number of calls grows exponentially with n — the dreaded O(2ⁿ) shape — so fib(40) already needs hundreds of millions of calls. The recursion is correct; it is just doing the same work over and over. The fix is to remember.

Remembering answers: memoisation

Imagine a teacher asks you, “What is fib(3)?” You work it out and say “2”. A minute later the teacher asks the very same question. A tired student recomputes it. A wise student glances at their notebook, where they wrote it down the first time, and answers “2” instantly.

That notebook is the whole idea. Memoisation means storing the answer to each call the first time you compute it, so that the next time the same call comes up, you read the answer instead of redoing the work.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}

    if n in memo:            # already in the notebook? read it
        return memo[n]

    if n == 0:
        return 0
    if n == 1:
        return 1

    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Each value of fib is now computed exactly once and reused everywhere it is needed. That collapses the cost from O(2ⁿ) down to O(n) — fib_memo(50) returns in an instant.

lru_cache: memoisation for free

This pattern is so common that Python hands you a ready-made notebook. You add one line above your function and the caching happens automatically.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

The decorator @lru_cache simply means “remember this function’s answers”. LRU stands for Least Recently Used: if you cap the notebook at a fixed size, the entry untouched for the longest is the one thrown out to make room. With maxsize=None it never throws anything out.

Run the comparison below and watch the same fib go from painfully slow to instant — the only change is the one decorator line.

from functools import lru_cache

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print("fib_naive(32) =", fib_naive(32))
print("fib_fast(32)  =", fib_fast(32))
print("cache stats:", fib_fast.cache_info())

Both print the same answer, fib(32) = 2178309. The difference is the work behind it. The naive version makes 7,049,155 calls to get there, rebuilding the same sub-results millions of times over. The cached version computes each fib(k) once, for k from 0 to 32 — just 33 distinct values — and reads the rest straight from the notebook:

fib_naive(32) = 2178309
fib_fast(32)  = 2178309
cache stats: CacheInfo(hits=30, misses=33, maxsize=None, currsize=33)

The cache_info() line reports misses (answers that had to be computed — exactly 33, one per distinct value) and hits (answers reused from the notebook — the 30 lookups the naive version threw away). You can wipe the notebook any time with fib_fast.cache_clear().

When should you reach for recursion?

Recursion is the natural fit when a problem visibly contains smaller copies of itself: factorials, Fibonacci, walking a tree or a folder-inside-a-folder, generating permutations, backtracking, graph search. In all of these, the recursive shape mirrors the problem, and the code reads almost like the definition.

Be more careful when the input is very large (you may overflow the stack), when the function does not clearly shrink toward a base case, or when a plain loop would simply be clearer. Counting from 1 to 5, for instance, can be written recursively, but a for loop says it better.

A good programmer does not reach for recursion everywhere. They reach for it where the problem is already recursive in shape.

A checklist you can carry

Whenever you sit down to write a recursive function, four questions get you unstuck:

1. What is the smallest case whose answer I already know?   (the base case)
2. How do I make the problem one step smaller?              (the recursive step)
3. What does the recursive call hand back to me?
4. How do I combine that smaller answer into the full one?

For factorial, the answers are quick — smallest case factorial(1) = 1; smaller problem factorial(n - 1); it hands back (n-1)!; combine by multiplying with n. And those four answers are the function.

One more: climbing stairs

Here is a problem that looks nothing like factorial but yields to the same thinking. There are 5 stairs, and you may climb either 1 or 2 at a time. How many different ways are there to reach the top?

Let ways(n) mean “the number of ways to climb n stairs”. Your very first move is either a single step (leaving n - 1 stairs) or a double step (leaving n - 2 stairs), and every full climb begins with one of those two choices. So:

ways(n) = ways(n - 1) + ways(n - 2)
ways(0) = 1     (one way to stand still — already at the top)
ways(1) = 1

That is the Fibonacci shape again, which means memoisation pays off in exactly the same way.

from functools import lru_cache

@lru_cache(maxsize=None)
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(5))   # 8

The eight ways for five stairs, if you want to check by hand, are 1 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 2 2, 2 1 2, and 2 2 1. Recognising the recursive shape, then adding memoisation, is a combination you will use again and again.

Summary

• Recursion is a function that solves a problem by calling itself on a smaller version of the same problem.
• Every recursion needs a base case to stop at, and every recursive call must move toward it.
• The call stack holds the pile of paused calls; each call gets a stack frame of its own.
• Recursion goes down to the base case, then comes back up carrying answers.
• Tree recursion (like naive Fibonacci) repeats work and can be exponential.
• Memoisation — by hand or with @lru_cache — remembers answers and brings that cost back down to O(n).

Practice

Work these in order — they climb from remembering to building.

Recall. In one sentence each: what is a base case, what does the call stack store, and what does LRU stand for?

Trace. Predict the output of this before running it, then check:

def fun(n):
    if n == 0:
        return
    print("A", n)
    fun(n - 1)
    print("B", n)

fun(3)

Build. Write a recursive power(x, n) so that power(2, 5) returns 32. Start from the checklist: the smallest case is power(x, 0) = 1.

Then test your understanding on the unfamiliar cases below.