Recursion in C++

Recursion is when a function calls itself to solve a smaller version of the same problem. It keeps calling itself until it reaches a simple case it can solve directly. Think of it like standing between two mirrors facing each other — you see a reflection of a reflection of a reflection, and eventually the images get too small to see. The "too small to see" point is where recursion stops.

Recursion is a powerful technique for problems that naturally break into smaller similar parts — like calculating factorials, traversing folder structures, or solving puzzles.

How Recursion Works

Every recursive function needs two essential parts:

• Base case — the condition where the function stops calling itself. Without this, the function would call itself forever (stack overflow).
• Recursive case — the part where the function calls itself with a smaller or simpler input.

Diagram: Recursive Call Flow

factorial(4)
  └─ 4 * factorial(3)
         └─ 3 * factorial(2)
                └─ 2 * factorial(1)
                       └─ BASE CASE: return 1
                ← returns 2 * 1 = 2
         ← returns 3 * 2 = 6
  ← returns 4 * 6 = 24

Simple Recursion Example: Countdown

#include <iostream>
using namespace std;

void countdown(int n) {
    if (n == 0) {           // base case
        cout << "Go!" << endl;
        return;
    }
    cout << n << "..." << endl;
    countdown(n - 1);       // recursive call
}

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

Output:

5...
4...
3...
2...
1...
Go!

Factorial Using Recursion

The factorial of a number n (written as n!) is the product of all integers from 1 to n. The factorial of 5 is 5 × 4 × 3 × 2 × 1 = 120.

#include <iostream>
using namespace std;

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

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

Output:

5! = 120
6! = 720

Sum of Digits Using Recursion

To find the sum of digits of a number (e.g., 1 + 2 + 3 for 123), you can peel off one digit at a time using recursion.

#include <iostream>
using namespace std;

int sumDigits(int n) {
    if (n == 0) {          // base case
        return 0;
    }
    return (n % 10) + sumDigits(n / 10);   // last digit + rest
}

int main() {
    cout << "Sum of digits of 456: " << sumDigits(456) << endl;
    return 0;
}

Output:

Sum of digits of 456: 15

How it runs:

sumDigits(456)
  → 6 + sumDigits(45)
        → 5 + sumDigits(4)
              → 4 + sumDigits(0)
                    → 0  (base case)
Result: 6 + 5 + 4 + 0 = 15

Fibonacci Series Using Recursion

The Fibonacci series is: 0, 1, 1, 2, 3, 5, 8, 13 ... Each number is the sum of the two before it.

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n == 0) return 0;    // base case
    if (n == 1) return 1;    // base case
    return fibonacci(n - 1) + fibonacci(n - 2);  // recursive case
}

int main() {
    for (int i = 0; i <= 7; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    return 0;
}

Output:

0 1 1 2 3 5 8 13

How the Call Stack Works

Every time a function is called, the computer stores its information on the call stack — a special area of memory. When a recursive function calls itself many times, many entries pile up on the stack.

Call Stack (growing down):
┌─────────────────────┐
│   factorial(1)      │  ← top (runs first, returns 1)
├─────────────────────┤
│   factorial(2)      │  ← waiting for factorial(1)
├─────────────────────┤
│   factorial(3)      │  ← waiting for factorial(2)
├─────────────────────┤
│   factorial(4)      │  ← waiting for factorial(3)
├─────────────────────┤
│   main()            │  ← bottom (started everything)
└─────────────────────┘

If recursion is too deep (no base case or too many calls), the stack runs out of space. This causes a stack overflow error and crashes the program.

Recursion vs Iteration

Most problems solvable with recursion can also be solved with loops (iteration). Choosing between them depends on clarity and performance.

Factorial with Loop (for comparison):

int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Both approaches produce the same answer. The loop version is faster; the recursive version is more elegant for certain problems.

Power Function Using Recursion

#include <iostream>
using namespace std;

int power(int base, int exp) {
    if (exp == 0) return 1;           // base case: anything^0 = 1
    return base * power(base, exp - 1);
}

int main() {
    cout << "2^10 = " << power(2, 10) << endl;
    return 0;
}

Output:

2^10 = 1024

Common Recursion Mistakes

Key Takeaways

• Recursion is a function calling itself to solve a smaller version of the same problem.
• Every recursive function must have a base case to stop the calls.
• The call stack stores each function call — deep recursion can overflow it.
• Recursion is elegant for problems with tree-like or self-similar structures.
• Iteration is generally faster and uses less memory than recursion.