Recursion in C++

Table of Contents

1. •Introduction
2. •How Recursion Works
3. •Base Case and Recursive Case
4. •The Call Stack
5. •Classic Recursive Problems
6. •Recursion vs Iteration
7. •Tail Recursion
8. •Common Pitfalls
9. •Best Practices

---

Introduction

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It's a powerful tool for problems with self-similar structure.

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

When to Use Recursion

• •Tree/graph traversal
• •Divide and conquer algorithms
• •Problems with natural recursive definition (factorial, Fibonacci)
• •Backtracking (puzzles, permutations)

---

How Recursion Works

The Three Requirements

Every recursive function needs:

1. •Base case: Condition that stops recursion
2. •Recursive case: Function calls itself with smaller/simpler input
3. •Progress toward base case: Each call must move closer to termination

void countdown(int n) {
    if (n <= 0) {           // 1. Base case
        cout << "Liftoff!" << endl;
        return;
    }
    cout << n << "..." << endl;
    countdown(n - 1);       // 2. Recursive case (n gets smaller = progress)
}

Visualization

countdown(3)
├── prints "3..."
└── countdown(2)
    ├── prints "2..."
    └── countdown(1)
        ├── prints "1..."
        └── countdown(0)
            └── prints "Liftoff!" (base case)

---

Base Case and Recursive Case

Identifying Base Cases

Ask: "What's the simplest case that I can solve directly?"

Multiple Base Cases

Sometimes you need more than one:

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

Recursive Case Design

The recursive call should:

• •Reduce problem size
• •Eventually reach base case
• •Combine results correctly

int sumArray(const int* arr, int size) {
    if (size == 0) return 0;                    // Base
    return arr[0] + sumArray(arr + 1, size - 1); // Reduce size by 1
}

---

The Call Stack

Each recursive call creates a new stack frame with its own:

• •Parameters
• •Local variables
• •Return address

Stack Visualization for factorial(4)

┌─────────────────────────────┐
│  factorial(1) → returns 1   │  ← Top (last called, first to return)
├─────────────────────────────┤
│  factorial(2) → returns 2×1 │
├─────────────────────────────┤
│  factorial(3) → returns 3×2 │
├─────────────────────────────┤
│  factorial(4) → returns 4×6 │  ← Bottom (first called, last to return)
└─────────────────────────────┘

Execution Flow

factorial(4) called
  → factorial(3) called
    → factorial(2) called
      → factorial(1) called
      ← returns 1
    ← returns 2 * 1 = 2
  ← returns 3 * 2 = 6
← returns 4 * 6 = 24

Stack Overflow

Too many recursive calls exhaust the stack:

void infinite() {
    infinite();  // Stack overflow!
}

Typical stack limit: ~1MB (varies by system)

• •Approximately 10,000-100,000 recursive calls

---

Classic Recursive Problems

1. Factorial

long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
// factorial(5) = 5 × 4 × 3 × 2 × 1 = 120

2. Fibonacci

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
// fibonacci(6) = 8  (0, 1, 1, 2, 3, 5, 8)

3. Sum of Digits

int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10);
}
// sumDigits(1234) = 1 + 2 + 3 + 4 = 10

4. Power

double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) return 1.0 / power(base, -exp);
    return base * power(base, exp - 1);
}

5. GCD (Euclidean Algorithm)

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
// gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6

6. Binary Search

int binarySearch(const vector<int>& arr, int target, int low, int high) {
    if (low > high) return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearch(arr, target, low, mid - 1);
    return binarySearch(arr, target, mid + 1, high);
}

7. Reverse String

string reverse(const string& s) {
    if (s.length() <= 1) return s;
    return reverse(s.substr(1)) + s[0];
}
// reverse("hello") = reverse("ello") + 'h'
//                  = reverse("llo") + 'e' + 'h'
//                  = ... = "olleh"

---

Recursion vs Iteration

Most recursive functions can be written iteratively:

Factorial Comparison

// Recursive
long long factorialRec(int n) {
    if (n <= 1) return 1;
    return n * factorialRec(n - 1);
}

// Iterative
long long factorialIter(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Trade-offs

When to Choose Each

Use Recursion:

• •Tree traversal
• •Divide and conquer (merge sort, quick sort)
• •Backtracking problems
• •When recursive solution is much cleaner

Use Iteration:

• •Simple accumulation (sum, factorial)
• •Performance-critical code
• •Very deep recursion possible

---

Tail Recursion

A function is tail recursive if the recursive call is the last operation:

Non-Tail Recursive

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Must multiply AFTER recursive call returns
}

Tail Recursive

int factorialTail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator);  // Last operation is the call
}

Why It Matters

• •Tail recursive functions can be optimized by compilers
• •Stack frame can be reused (no stack growth)
• •Some compilers (with -O2) convert to iteration

Enabling Tail Call Optimization

g++ -O2 -foptimize-sibling-calls program.cpp

---

Common Pitfalls

1. Missing Base Case

// WRONG - infinite recursion!
int sum(int n) {
    return n + sum(n - 1);  // No base case
}

2. Base Case Never Reached

// WRONG - doesn't progress toward base
int broken(int n) {
    if (n == 0) return 0;
    return broken(n);  // n never changes!
}

3. Wrong Direction

// WRONG - n grows instead of shrinking
int broken(int n) {
    if (n > 100) return n;
    return broken(n + 1);  // Works but counterintuitive
}

4. Exponential Time Complexity

// Naive Fibonacci - O(2^n) time!
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Many repeated calculations
}

// fib(5) calls fib(4) + fib(3)
// fib(4) calls fib(3) + fib(2)  ← fib(3) calculated twice!

5. Stack Overflow

// For large n, this will crash
void deep(int n) {
    if (n == 0) return;
    deep(n - 1);
}
deep(1000000);  // Stack overflow!

---

Best Practices

1. Always Start with Base Case

int solve(int n) {
    // Handle base case(s) first
    if (n <= 0) return 0;

    // Then recursive case
    return /* ... */;
}

2. Use Memoization for Overlapping Subproblems

#include <unordered_map>

unordered_map<int, long long> memo;

long long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];

    memo[n] = fibMemo(n-1) + fibMemo(n-2);
    return memo[n];
}

3. Consider Converting to Iteration

// When depth could be large, use iteration
int sumIterative(const vector<int>& arr) {
    int total = 0;
    for (int n : arr) total += n;
    return total;
}

4. Helper Functions with Accumulators

// Public interface
vector<int> reversed(const vector<int>& v) {
    return reverseHelper(v, v.size() - 1, {});
}

// Private recursive helper
vector<int> reverseHelper(const vector<int>& v, int idx, vector<int> acc) {
    if (idx < 0) return acc;
    acc.push_back(v[idx]);
    return reverseHelper(v, idx - 1, acc);
}

5. Test Edge Cases

• •Empty input
• •Single element
• •Maximum expected depth
• •Negative numbers (if applicable)

---

Quick Reference

// Basic structure
ReturnType recursiveFunc(params) {
    if (/* base case */) {
        return baseValue;
    }
    return /* combine with */ recursiveFunc(smallerParams);
}

// Common patterns
// Linear: f(n) = f(n-1) + something
// Binary: f(n) = f(n/2) + something
// Tree: f(n) = f(left) + f(right)
// Multiple: f(n) = f(n-1) + f(n-2)

---

Compile & Run

g++ -std=c++17 -Wall -Wextra examples.cpp -o examples
./examples