Introduction to Recursion

What is Recursion?

Imagine you have a set of Russian nesting dolls. You open the largest doll to find a slightly smaller doll inside. You open that one, and there's another, even smaller doll. You continue this until you reach the smallest doll, which can't be opened. This process of repeating the same action—opening a doll—on a smaller version of the item is the core idea behind recursion.

In programming, recursion is a method where a function calls itself to solve a problem.

Instead of tackling a large, complex problem all at once, a recursive function breaks it down into smaller, identical subproblems. It solves the smallest version of the problem first and then works its way back up, combining the solutions to solve the original, larger problem.

The Base Case

A function that only calls itself will run forever, like an endless loop. This is called infinite recursion, and it will eventually crash your program by using up all the available memory. To prevent this, every recursive function needs a stopping point.

base case

noun

A condition within a recursive function that stops the recursion. It's the simplest version of the problem that can be solved directly without making another recursive call.

Think back to the nesting dolls. The base case is the smallest doll that won't open. Once you reach it, the process of opening dolls stops.

A recursive function typically has two main parts:

The Base Case: The condition under which the function stops calling itself.
The Recursive Case: The part of the function where it calls itself, but with a modified argument that moves it closer to the base case.

A Countdown Example

Let's see recursion in action with a simple C function that counts down from a given number to 1.

#include <stdio.h>

// A recursive function to count down
void countdown(int n) {
    // Base Case: Stop when n is 0 or less.
    if (n <= 0) {
        printf("Go!\n");
        return; // Stop the recursion
    }

    // Recursive Case: Print the number and call itself with n-1.
    printf("%d...\n", n);
    countdown(n - 1); // Recursive call
}

int main() {
    countdown(3);
    return 0;
}

When we call countdown(3), here’s what happens:

countdown(3) is called. 3 is not <= 0, so it prints 3... and calls countdown(2).
countdown(2) is called. 2 is not <= 0, so it prints 2... and calls countdown(1).
countdown(1) is called. 1 is not <= 0, so it prints 1... and calls countdown(0).
countdown(0) is called. Now, n is <= 0. The base case is met. It prints Go! and returns, ending that function call.
Control returns to countdown(1), which has nothing left to do, so it finishes. This continues up the chain until the original countdown(3) call is complete.

The key is that each recursive call gets one step closer to the base case, ensuring the process will eventually terminate.

Factorial Calculation

Another classic example is calculating the factorial of a number. The factorial of a non-negative integer $n$ , denoted by $n!$ , is the product of all positive integers less than or equal to $n$ . For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ .

We can define this recursively. Notice that $5! = 5 \times 4!$ , and $4! = 4 \times 3!$ , and so on. In general, $n! = n \times (n-1)!$ . This gives us our recursive case. What's the base case? The factorial of 0, which is defined as 1. So, when $n$ is 0, we should just return 1.

#include <stdio.h>

// Recursive function to find factorial
int factorial(int n) {
    // Base Case: Factorial of 0 is 1.
    if (n == 0) {
        return 1;
    }

    // Recursive Case: n * factorial of (n-1)
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

This function breaks down the problem of finding factorial(5) into finding factorial(4), which breaks down into finding factorial(3), and so on, until it hits the base case factorial(0). Then, the results are multiplied back up the call stack to get the final answer.

Recursion is a powerful way to think about and solve problems that can be broken down into smaller, self-similar pieces. Getting comfortable with identifying the base case and the recursive step is the key to mastering it.

Recursion in C Programming