programmingconcepts

§ 1.4 · Foundations

Recursion

A function that solves a problem by calling itself on a smaller version of the same problem.

Recursion is when a function solves a problem by calling itself on a smaller version of it. Every recursive function needs a base case that answers directly, and a recursive case that shrinks the problem. Each call waits on the call stack until the one it made returns, so deep recursion uses memory and can overflow the stack.

Needs
A base case
Space
One frame per active call
Alternative
A loop and a stack
Requires
Functions
def factorial(n):
    if n <= 1:
        return 1
    rest = factorial(n - 1)
    return n * rest

Call factorial(4). It gets its own frame on the call stack.

step 0 / 0runningwaitingreturning

Fig. 1.4. Each box is a frame on the call stack, newest at the top. The outlined frame is running, grey frames are waiting for an answer, and black frames are returning one.

Intuition

Stand in a queue and want to know your position. You can’t see the front, so you ask the person ahead of you, who asks the person ahead of them. The person at the front knows they’re first and says “1.” Each person adds one to the answer they get back and passes it on.

That’s recursion: each call hands a smaller question to the next and waits. The base case (the person at the front) answers without asking. The answers then come back in the reverse order the questions went out.

How it works

factorial(n) is n × (n − 1) × … × 1. Written recursively:

  1. Base case: if n is 1 or less, return 1.
  2. Recursive case: otherwise, call factorial(n - 1) and multiply the result by n.

Every call gets its own frame on the call stack, holding its own n. A frame can’t finish until the call it made returns, so frames pile up until the base case. Then each frame returns to the one below it.

The cost

Each waiting frame uses memory, so factorial(n) needs n frames at its deepest: O(n) space, even though a loop would need O(1). Languages limit the stack’s size, so very deep recursion crashes:

Language What happens when the stack runs out
Python RecursionError after about 1,000 calls by default
JavaScript RangeError: Maximum call stack size exceeded
Java StackOverflowError
C Usually a crash; the behaviour is undefined
Go Stacks grow as needed, up to 1 GB on 64-bit systems
Rust The program aborts with a stack overflow

Common mistakes

  1. No base case, or one that is never reached (for example n == 0 when n can start negative).
  2. Not shrinking the problem. Calling f(n) from f(n) recurses forever.
  3. Repeating work. A naive recursive Fibonacci recomputes the same values exponentially many times; store results (memoization) or use a loop.
  4. Recursing where a loop is simpler. Factorial is a teaching example; in production a loop does it in constant space.

When to use it

When the problem is naturally self-similar: trees and nested data, divide and conquer (merge sort, quicksort), and backtracking searches. The recursive version is often far shorter and clearer than managing a stack by hand.

Check yourself

Check yourself

At its deepest, how many frames are on the call stack while computing factorial(5)?

Check yourself

What happens if you remove the if n <= 1 base case?

Sources

  • Harold Abelson and Gerald Jay Sussman, Structure and Interpretation of Computer Programs, section 1.2.1.
  • Python documentation, sys.getrecursionlimit().

Newsletter

One new concept each week, by email.

Signup opens soon.