Recursion in C++

What is recursion?

Recursion is when a function calls itself. Instead of a loop, the function solves a big problem by handing a slightly smaller version of it to another copy of itself — until the problem is small enough to answer directly.

The base case

Every recursion needs a base case — the simplest input, answered without calling again. It is what stops the chain. The other part, the recursive case, calls the function on a smaller input.

Example: factorial

Factorial: 5! = 5 × 4 × 3 × 2 × 1. Notice n! = n × (n-1)! — that is the recursion.

#include <iostream>
using namespace std;

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

int main() {
    cout << factorial(5) << "\n";
    return 0;
}

Tracing the calls

It helps to see how the calls stack up and then unwind:

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))
             = 24

The calls go down to the base case, then the answers multiply back up.

Example: Fibonacci

Each Fibonacci number is the sum of the previous two, with two base cases:

int fib(int n) {
    if (n < 2) return n;             // base: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);  // recursive case
}
// fib(6) → 8

Recursion vs iteration

Anything recursive can be written with a loop, and vice versa — pick whichever reads more clearly for the problem.

Common mistakes

• Forgetting the base case, causing infinite recursion and a stack overflow.
• A recursive call that does not move toward the base case.
• Using naive recursion for Fibonacci on large n (very slow).
• Forgetting to return the recursive call's result.

Summary

• Recursion is a function calling itself on a smaller input.
• Every recursion needs a base case to stop, plus a recursive case.
• Factorial and Fibonacci are classic examples.
• Recursion uses stack memory; a missing base case causes stack overflow.
• Use recursion for naturally recursive problems; loops for simple repetition.