Recursion concepts

Most problems you have solved so far used loops: start at one end, walk to the other, accumulate a result. Recursion is a different shape. A recursive function solves a problem by solving a slightly smaller version of the same problem and combining the result. The function calls itself — and that is not a bug, it is the entire strategy.

The canonical example: factorial

The factorial of a non-negative integer n (written n!) is defined as:

• 0! = 1 (by definition)
• n! = n × (n-1)! for n > 0

That second line is recursive: "the factorial of n equals n times the factorial of n-1." In code:

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

Every correct recursive function has exactly two parts:

1. Base case — the condition where the function stops calling itself and returns a direct answer. Without a base case, the function recurses forever.
2. Recursive case — the condition where the function calls itself with a smaller argument, moving toward the base case.

The call stack: what actually happens

When Python calls a function, it creates a stack frame — a small block of memory that stores the function's local variables and the point to return to when the function finishes. Stack frames are stacked on top of each other, hence the name "call stack."

When factorial(3) runs:

1. factorial(3) is called. It can't return yet — it needs factorial(2).
2. factorial(2) is called. It needs factorial(1).
3. factorial(1) is called. It needs factorial(0).
4. factorial(0) hits the base case and returns 1.
5. factorial(1) gets 1 back and returns 1 × 1 = 1.
6. factorial(2) gets 1 back and returns 2 × 1 = 2.
7. factorial(3) gets 2 back and returns 3 × 2 = 6.

Each pending call waits on the stack until the one below it resolves. The stack grows as calls pile up, and shrinks as they return.

Stack overflow: what goes wrong without a base case

If you forget the base case — or write a recursive case that never gets smaller — the function calls itself indefinitely. The call stack fills up. Python detects this and raises a RecursionError: maximum recursion depth exceeded. In other languages this is called a stack overflow.

The mental check before writing any recursive function: "does every possible input eventually reach the base case?" If yes, the recursion terminates. If no, you have infinite recursion waiting to happen.

The mental model to carry forward

Recursion is not magic — it is structured delegation. When you write return n * factorial(n - 1) you are saying: "I will handle the multiplication by n; you (recursive call) handle the rest." The call stack keeps track of all the pending multiplications until the base case provides the first concrete value to hand back up the chain.

Where to go next

Next: recursion in Python — implementing factorial and Fibonacci with print traces so you can watch the call sequence unfold, and a note on Python's built-in recursion limit.