Recursion

Overview

Recursion occurs when a function calls itself. It requires a base case to stop. It's incredibly useful for traversing trees, graphs, and solving algorithmic problems like divide-and-conquer.

Syntax

cpp

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

Common Pitfalls

Missing the base case, resulting in an infinite loop and a Stack Overflow crash.
Recursive branching (like naive Fibonacci) results in exponential time complexity O(2^N). Use Dynamic Programming (memoization) to fix this.

Interview Tips

Know the difference between standard recursion and 'Tail Recursion'. Tail recursion (where the recursive call is the absolute last thing executed) can be optimized by the compiler to prevent Stack Overflow.

Real-World Example

Calculating the Nth Fibonacci number.

example

cpp

#include <iostream>
using namespace std;

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

int main() {
    cout << "Fibonacci(6): " << fibonacci(6) << endl; // Prints 8
    return 0;
}

Take C++ Quiz