COMP 210: Data Structures

Recursive Functions

A recursive function is a function that calls itself to solve a problem. It works by breaking down a larger problem into smaller, identical subproblems until it reaches a base case, which is a condition where the function can return a value without making another recursive call. Think of it like a set of Russian nesting dolls; you keep opening a doll to find a smaller one inside until you get to the smallest doll, which you can’t open anymore.

How it Works

Every recursive function must have two main parts:

  1. The Recursive Step: This is where the function calls itself with a modified input that brings it closer to the base case. The function performs some operation, simple or complex, to get the modified input it will pass to the recursive call, and may also perform some operation on the return value from the recursive call before it, itself, returns.

  2. The Base Case: This is a condition where the function knows, or can calculate, what to return without further recursion. It is absolutely essential to have a base case, otherwise the function would call itself indefinitely, leading to infinite recursion. Some functions may have more than one base case, as in the fibonacci example below.

Since the base case is what eventually stops the recursion, it is important to check for the base case before potentially going on to the recursive step.

Each recursive call requires space in memory to hold its parameters and local variables. This area of memory is called the call stack, or just the stack. An erroneous program that gets into an infinitely recursive state will eventually fill up this area of memory, resulting in a stack overflow error.

An Illustrative Example

A classic example of recursion is the factorial function, which calculates the product of all non-negative integers up to a given number.

The factorial of a non-negative number n (denoted as n!) can be defined as:

0! = 1
n! = n * (n − 1)!

For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Here’s a simple Python code example for a recursive factorial function:

def factorial(n):   # Pre-condition: n >= 0
    # Base Case: When n is 0, we can stop the recursion.
    if n == 0:
        return 1
    # Recursive Step: Call the function with n-1.
    else:
        return n * factorial(n - 1)

print(factorial(5)) # Output: 120

Let’s trace the call for factorial(5):

Once the program reaches the base case, the values are returned back up the chain:

When to Use Recursion

Some problems, like factorial, naturally lend themselves to a recursive solution. Recursion is also frequently a good fit for operations on recursive data structures, such as traversing tree data structures or searching through file systems. While many recursive problems can also be solved efficiently with an iterative (loop-based) approach, the recursive solution can sometimes be more elegant, readable, and easier to understand.

When Not to Use Recursion

Recursion is elegant for certain problems, but it’s not always the best choice for performance. Each time a function is called, a record of its state (called a stack frame) is pushed onto the call stack, and for a recursive function, this happens with every single recursive call. An iterative (loop-based) solution, on the other hand, typically reuses the same memory space, making it more memory-efficient.

For example, the factorial function can also be implemented iteratively.

n! = n * (n − 1) * (n − 2) * ... * 1 = 1 * 2 * 3 * ... * (n − 1) * n

def iterative_factorial(n):   # Pre-condition: n >= 0
    # 1 is the base case (0! = 1) as well as the multiplicative identity.
    result = 1
    # Calculate n! = 1 * 2 * 3 * ... * n
    for i in range(1, n + 1):
        result = result * i
    return result

Some recursive solutions also lead to high time complexity due to redundant computations. A classic example this is a naive implementation of the Fibonacci sequence, whose mathematical definition is:

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n − 1) + Fib(n − 2)

A straight-forward, but very inefficient, translation into a recursive function looks like this:

def fibonacci(n):   # Pre-condition: n >= 0
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

The issue with this approach is that it recalculates the same values over and over again. For instance, to compute fibonacci(5), the function calls are:

fibonacci(5) = fibonacci(4) + fibonocci(3)

As you can see, fibonacci(3) results in 4 recursive calls to the fibonacci function, fibonacci(4) results in 8 recursive calls, and fibonacci(5) results in 14 recursive calls. The number of calls grows exponentially with n, specifically with a time complexity of O(2n).

Summary

In summary, recursive solutions can be simple, intuitive, and elegant, but can also be inefficient. The trade-off is often between the elegance of recursion and the performance of iteration.

Author: Google Gemini, with significant additions and editing by Alyce Brady, Kalamazoo College.
Date: 14 October 2025