Introduction to Recursion

Part of the Logic & Flow section of Coddy's C++ journey — lesson 45 of 56.

Recursion is a programming technique where a function calls itself to solve a problem. Instead of using loops, recursive functions break down complex problems into smaller, similar subproblems until they reach a simple case that can be solved directly.

Every recursive function must have two essential components. The base case is a condition that stops the recursion - without it, the function would call itself forever. The recursive step is where the function calls itself with modified parameters, moving closer to the base case with each call.

Here's a simple countdown example that demonstrates recursion:

void countdown(int n) {
    if (n <= 0) {           // Base case: stop when n reaches 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Recursive step: call with n-1
}

When you call countdown(3), it prints 3, then calls countdown(2), which prints 2, then calls countdown(1), and so on until it reaches the base case. Each function call waits for the next one to complete before finishing, creating a chain of calls that eventually unwinds back to the original caller.

Cheat sheet

Recursion is when a function calls itself to solve a problem by breaking it into smaller subproblems.

Every recursive function needs:

Base case: condition that stops the recursion
Recursive step: function calls itself with modified parameters

Example countdown function:

void countdown(int n) {
    if (n <= 0) {           // Base case
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Recursive step
}

Try it yourself

This lesson doesn't include a code challenge.