Recursion and the Call Stack

What is recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. It is useful for problems which can be broken down into repeated steps, such as factorials or searching through folders.

A recursive function needs a base case, which tells it when to stop. Without this, it would keep calling itself until the computer ran out of stack space.

Example: factorial

A factorial means multiplying a positive whole number by every positive whole number below it. For example, 4! = 4 x 3 x 2 x 1 = 24. (And, no, 0 isn't a positive number)

This is a simple recursive function written in Python:

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

print(factorial(4))

First, factorial(4) asks for factorial(3). Then factorial(3) asks for factorial(2), and factorial(2) asks for factorial(1). Once the base case is reached, the answers are passed back up.

I drew the diagram below using basic SVG shapes directly in this HTML file.

The calls move from left to right, but the calculations finish in reverse order: 1, then 2, then 6, then 24.

What is the call stack?

The call stack is an area of memory which stores information about functions that are currently running. Each time a function calls another function, a new stack frame is added. The frame remembers information such as local variables and where to return afterwards.

Here is my diagram of the call stack just before factorial(1) returns:

Because the stack follows Last In, First Out (LIFO), factorial(1) finishes first, followed by factorial(2), factorial(3), and finally factorial(4). This explains why the program doesn't forget the multiplication it still needs to do.

Quick questions

Click each question to check your understanding.

What happens if a recursive function has no base case?

It keeps calling itself until it reaches the language's recursion limit or runs out of stack space.

Which function finishes first in factorial(4)?

factorial(1), because it is the base case and the last call added to the stack.

Why can a loop use less memory?

A loop can reuse its variables without creating a new stack frame for every repetition.