Recursion in C++

Analogy categoryAnalogies

1. Intro

Recursion occurs when a function calls itself, either directly or indirectly, in order to solve a problem by breaking it down into smaller instances of the same problem. Every recursive function needs a base case — a condition under which it stops calling itself and returns a value directly — to prevent it from calling itself forever.

🏏

Cricket analogy: A commentator explaining a super over says "if scores are still tied after this super over, play another super over" — the rule calls itself, but it must stop once a winner emerges, just as recursion needs a base case to stop calling itself.

2. Syntax

cpp

returnType recursiveFunction(parameters) {
    if (baseCondition) {
        return baseValue;      // base case: stops the recursion
    }
    return recursiveFunction(smallerProblem);  // recursive case
}

3. Explanation

A recursive function has two essential parts: the base case, which handles the simplest version of the problem directly without further recursive calls, and the recursive case, which calls the function again with a smaller or simpler input, moving it closer to the base case. The classic example is factorial: n! = n * (n-1)!, with the base case 0! = 1. Another classic example is the Fibonacci sequence, where fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1. Each recursive call adds a new stack frame to the call stack, storing that call's local variables and return address. If a recursive function never reaches its base case, it keeps calling itself indefinitely, consuming stack memory with every call until the program crashes with a stack overflow.

🏏

Cricket analogy: The base case is when a bowler has one over left and just bowls it directly; the recursive case is "bowl this over, then face the remaining overs the same way" — like matches(n) = 1over + matches(n-1), ending in a stack of overs bowled, until a captain who never declares racks up so many overs the innings collapses like a stack overflow.

Recursion without a correctly reachable base case causes unbounded recursive calls, exhausting the call stack and crashing the program with a stack overflow. Always verify that every recursive call moves the input measurably closer to the base case.

4. Example

cpp

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) {          // base case
        return 1;
    }
    return n * factorial(n - 1);  // recursive case
}

int main() {
    cout << "5! = " << factorial(5) << endl;
    return 0;
}

5. Output

text

5! = 120

6. Key Takeaways

Recursion is when a function calls itself to solve smaller instances of the same problem.
Every recursive function needs a base case that stops further recursive calls.
Factorial and Fibonacci are classic examples of recursive problems.
Missing or unreachable base cases cause unbounded recursion and stack overflow.