Introduction to Recursion

Functions That Call Themselves

Imagine you have a set of Russian nesting dolls. You open the biggest doll, and inside you find a slightly smaller, identical doll. You open that one, and there's another one inside. You keep repeating this process until you reach the smallest, solid doll that can't be opened.

Recursion in programming is a lot like that. It's a technique where a function solves a problem by calling itself to solve smaller versions of the same problem. Just like with the dolls, you keep going until you hit a version of the problem that's so simple it can be solved directly. This stopping point is essential.

Recursion breaks a large problem into smaller, repeatable sub-problems.

The Two Rules of Recursion

Every recursive function must follow two fundamental rules. If you miss one, your program will likely crash or run forever.

Base Case

noun

The condition under which the function stops calling itself and returns a value directly. This is the smallest, solvable version of the problem.

The base case is your exit strategy. It's the solid, innermost nesting doll. It tells the function, "Okay, we're done here. No more calls needed."

Second, every recursive function needs a way to change its state to eventually meet the base case. This is often called the recursive step.

The recursive step is where the function calls itself, but with an input that is somehow closer to the base case.

Let's think about counting down from 3 to launch a rocket. The problem is "count down from 3".

To count down from 3, you first need to count down from 2.
To count down from 2, you first need to count down from 1.
To count down from 1, you just say "1".

Counting down from 1 is the simplest problem. That's our base case. Each step before that gets us closer to 1.

Recursion in Action

Let's see how these rules apply in C code. A classic example is calculating a factorial.

n! = n \times (n-1) \times (n-2) \times \dots \times 1

For example, $5!$ is $5 \times 4 \times 3 \times 2 \times 1$ , which equals 120. Notice the pattern? The factorial of any number is that number multiplied by the factorial of the number just below it. So, $5! = 5 \times 4!$ . This is a perfect setup for recursion.

int factorial(int n) {
    // Base case: factorial of 1 (or 0) is 1
    if (n <= 1) {
        return 1;
    }
    // Recursive step: n * factorial of (n-1)
    else {
        return n * factorial(n - 1);
    }
}

In this function, the base case is if (n <= 1). If the input n is 1 or less, the function stops recursing and just returns 1. The recursive step is return n * factorial(n - 1);, where the function calls itself with a smaller value, n - 1, moving closer to the base case.

Another common example is the Fibonacci sequence. This is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Mathematically, the rule is $F(n) = F(n-1) + F(n-2)$ . You can see the recursive relationship right in the definition. To find the 5th number, you need the 4th and 3rd. To find the 4th, you need the 3rd and 2nd, and so on.

int fibonacci(int n) {
    // Base cases
    if (n <= 1) {
        return n;
    }
    // Recursive step
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

This function has two base cases: if n is 0, it returns 0, and if n is 1, it returns 1. The recursive step adds the results of two separate recursive calls. While elegant, this specific implementation is very inefficient for larger numbers because it re-calculates the same values many times. But it's a perfect illustration of how a problem can be defined in terms of itself.

Let's test what you've learned about recursion.

Quiz Questions 1/5

What are the two essential components that every recursive function must have to work correctly?

Quiz Questions 2/5

What is the primary purpose of a 'base case' in a recursive function?

Recursion is a powerful tool for solving problems that can be broken down into smaller, similar pieces. The key is to always define a base case to ensure the function eventually stops.

Recursion and Void Types in C