Recursion: Functions That Call Themselves

A function that calls itself

Recursion confuses people at first, and then suddenly stops confusing them. The trick is to stop trying to trace every level in your head.

Recursion is solving a problem by solving a smaller version of the same problem.

Think about counting the students in a long queue where you can only talk to the person in front of you. You ask them "how many people are ahead of you?" They ask the person in front of them the same question. Eventually someone at the very front says "zero". Then each answer comes back down the line, each person adding one.

Nobody counted the whole queue. Each person did one tiny piece of work and trusted the next person to handle the rest. That is recursion.

The two parts

Every correct recursive function has exactly two parts:

Base case. The smallest version of the problem, which you answer directly without recursing. This is where the chain stops.

Recursive case. Reduce the problem slightly, call yourself on the smaller version, and combine.

Miss the base case and the function calls itself forever. Fail to actually shrink the problem and you get the same thing.

def countdown(n):
    if n == 0:                 # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)           # recursive case, on a smaller n

countdown(5)

countdown(5) prints 5 and calls countdown(4), which prints 4 and calls countdown(3), and so on. countdown(0) prints "Liftoff!" and returns without calling anything, and the whole chain unwinds.

Factorial

n! = n (n-1) (n-2) ... 1, and 0! = 1.

Notice that 5! = 5 * 4!. The definition is already recursive.

def factorial(n):
    if n <= 1:                 # base case: 0! and 1! are both 1
        return 1
    return n * factorial(n - 1)

for i in range(6):
    print(i, "! =", factorial(i))

print()
print("10! =", factorial(10))

Do not try to picture all five levels at once. Instead check two things:

1. Is the base case correct? factorial(1) returns 1. Yes.
2. Assuming factorial(n-1) is correct, is n * factorial(n-1) correct? Yes, by the definition.

If both hold, the function is correct for every n. That is all the verification you need, and it is far easier than mental tracing.

The call stack

Recursion is not free. Every call needs its own copy of the parameters and local variables, so the computer keeps a stack frame for each one.

factorial(4) called
  frame: n=4, waiting on factorial(3)
    frame: n=3, waiting on factorial(2)
      frame: n=2, waiting on factorial(1)
        frame: n=1, returns 1        <- base case reached
      returns 2 * 1 = 2
    returns 3 * 2 = 6
  returns 4 * 6 = 24

The frames pile up going down and unwind coming back up. This is a stack in exactly the sense from the stacks tutorial — last in, first out.

Two consequences:

Recursion uses O(depth) memory. A recursion 1,000 levels deep holds 1,000 frames.

There is a depth limit. Python stops at about 1,000 frames and raises RecursionError. That limit exists to catch runaway recursion before it exhausts memory.

Fibonacci, and why the obvious version is slow

The Fibonacci sequence: each number is the sum of the previous two. 0, 1, 1, 2, 3, 5, 8, 13, and so on.

The recursive definition writes itself:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

Two base cases here, because the recursive case reaches back two steps.

calls = 0

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [5, 10, 20, 25]:
    calls = 0
    result = fib(n)
    print("fib(", n, ") =", result, "| function calls made:", calls)

Look at the call counts. fib(25) is a small number, but computing it takes over two lakh function calls.

The reason is repeated work. To compute fib(5), you compute fib(4) and fib(3). But fib(4) also computes fib(3). That subtree gets rebuilt from scratch every time it appears.

                fib(5)
              /        \
        fib(4)          fib(3)      <- fib(3) computed twice
        /    \          /    \
   fib(3)  fib(2)  fib(2)  fib(1)   <- fib(2) computed three times

The number of calls roughly doubles for each increase in n, so this is O(2^n) — exponential. fib(50) this way would take days.

Fixing it: remember what you computed

The problem is not recursion. It is recomputation. Store each answer the first time and reuse it. This is called memoisation.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

def fib_loop(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

for n in [10, 30, 50, 80]:
    print("n =", n, "| memoised:", fib_memo(n), "| iterative:", fib_loop(n))

Both run instantly for n = 80, where the naive version would still be running next week. Memoisation turns O(2^n) into O(n) by making sure each value is computed exactly once — a dictionary lookup replacing an entire subtree of work.

The iterative version is O(n) time and O(1) space, since it only keeps two variables. It is the best of the three here.

Recursion versus iteration

Anything you can write recursively you can write with a loop, and the other way round. The choice is about clarity.

Prefer recursion when the problem is naturally self-similar: tree traversal, exploring directories inside directories, merge sort and quick sort, backtracking problems like N-Queens or Sudoku. The recursive code for these is dramatically shorter and clearer than the loop version.

Prefer iteration when the problem is a straightforward repetition — summing a list, searching linearly, computing Fibonacci. A loop avoids stack frames and cannot overflow.

If you find yourself building a stack by hand to solve a problem, that is a sign recursion wants to do it for you.

Common mistakes

No base case, or an unreachable one. factorial(-1) with a base case of n == 0 recurses forever, because n never reaches 0. Using n <= 1 handles it safely.

Not shrinking the problem. Calling f(n) instead of f(n - 1) gives infinite recursion even with a correct base case.

Forgetting to return the recursive call. Writing factorial(n - 1) instead of return n * factorial(n - 1) makes the function return None, and you get a confusing TypeError about NoneType.

Using a mutable default argument. def f(n, memo={}) shares one dictionary across all calls, including separate top-level calls. Use memo=None and create the dict inside, as above.

Assuming recursion is inherently slow. Naive Fibonacci is slow because of repeated work, not because it recurses. Merge sort is recursive and fast.

Recursing deeply on large inputs. A recursive scan of a 10,000-element list will hit Python's depth limit. Use a loop for linear work.

Practice

Try the recursion exercises on the practice page — write the base case first, every time.