C++ Recursion Advanced Programming

Algorithm Design

C++ Recursion: Complete Guide with Examples

Master C++ recursion: understand recursion vs iteration, recursive algorithms, stack management, optimization techniques, and when to use recursion effectively.

Recursion Basics

Base Case & Recursive Case

vs Iteration

Comparison & Trade-offs

Recursion Stack

Stack Frames & Memory

Optimization

Tail Recursion & Memoization

C++ Tutorial · Recursion

Recursion solves problems by reducing them to smaller subproblems. Learn when recursion fits, how the call stack works, and how to avoid stack overflow and redundant work.

C++ recursion infographic: base case and recursive case, call stack visualization, factorial and Fibonacci recursive examples — **C++ recursion visual guide** — base case, recursive calls, call stack growth, and classic factorial/Fibonacci patterns for interviews.

What you will learn

Write correct base and recursive cases
Trace call stack depth and complexity
Solve classic recursive problems step by step
Compare recursion with iterative alternatives
Apply memoization for overlapping subproblems

Why this topic matters

Tree/graph DFS, divide-and-conquer, and backtracking rely on recursion. Interviewers love factorial, Fibonacci, and tower-of-Hanoi variants.

Key terms & indexing

C++ recursion recursive function C++ base case recursion call stack C++

Introduction to Recursion

Recursion is a programming technique where a function calls itself to solve a problem. It breaks down complex problems into simpler, similar subproblems until a base case is reached.

Why Use Recursion?

Elegant solution for certain problems
Natural fit for tree/graph traversal
Simplifies divide-and-conquer algorithms
Easier to understand for some problems
Useful for backtracking problems
Natural for mathematical definitions

Recursion Components

Base Case: Stopping condition
Recursive Case: Calls itself
Recursive Call: Function calling itself
Stack Frames: Memory for each call
Return Values: Propagate back up

Recursive Function Execution Flow

Initial Call: Function called with initial parameters

Check Base Case: Test if problem is simple enough

Recursive Case: Break problem, call function with simpler parameters

Stack Build-up: Each call creates new stack frame

Base Case Reached: Return simple solution

Stack Unwinding: Combine results back up the stack

Iteration vs Recursion: Comprehensive Comparison

The following table provides a detailed comparison between iteration and recursion in C++:

Aspect	Iteration (Loops)	Recursion (Self-calling)
Definition	Repeats block of code using loops (for, while, do-while)	Function calls itself to solve smaller instances of same problem
Basic Structure	for(int i=0; i while(condition) { }	type func(params) { if(baseCase) return value; return func(modifiedParams); }
Memory Usage	Low memory Uses constant stack space	High memory Each call creates stack frame Risk of stack overflow
Performance	Generally faster No function call overhead Better cache locality	Slower Function call overhead Stack manipulation costs
Code Readability	Simple for linear problems Easy to debug Straightforward flow	Elegant for certain problems Matches problem definition Can be harder to understand
When to Use	• Simple repetition • Sequential processing • Performance-critical code • Known number of iterations	• Tree/graph traversal • Divide and conquer • Backtracking problems • Mathematical definitions
Termination	Loop condition becomes false Explicit break statement	Base case reached Must be carefully defined
Debugging	Easier to debug Linear execution flow Can use loop variables	Harder to debug Multiple stack frames Complex call hierarchy
Examples	• Array processing • Counting/summing • Searching arrays • Matrix operations	• Factorial calculation • Fibonacci sequence • Tree traversal • Tower of Hanoi
Risk Factors	• Infinite loops • Off-by-one errors • Incorrect loop conditions	• Stack overflow • Infinite recursion • Missing base case • Exponential time complexity

Key Insight: Iteration vs Recursion

Any recursive algorithm can be converted to iteration (using stacks), and most iterative algorithms can be converted to recursion. The choice depends on problem nature, readability, and performance requirements.

1. Basic Recursion Examples: Factorial & Fibonacci

These classic examples demonstrate the fundamental pattern of recursion: breaking down problems into smaller subproblems.

Recursive Pattern Template

return_type recursiveFunction(parameters) {
    // 1. BASE CASE (stopping condition)
    if (simple_case_condition) {
        return base_value;
    }
    
    // 2. RECURSIVE CASE (break down problem)
    // Modify parameters to make problem smaller
    return combine(recursiveFunction(smaller_problem), current_value);
}

Factorial Examples

1. Iterative factorial

long long fact(int n) {
    long long r = 1;
    for (int i = 2; i <= n; i++)
        r *= i;
    return r;
}

2. Recursive factorial

long long fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

3. Base case 0!

if (n == 0)
    return 1;  // 0! = 1

4. Call fact(5)

cout << fact(5);
// 5*4*3*2*1 = 120

5. Negative guard

if (n < 0)
    throw invalid_argument("n");
return fact(n);

6. Loop vs recursion

cout << factLoop(6);
cout << factRec(6);
// both print 720

Fibonacci Examples

1. Naive recursive

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

2. Iterative fib

int a=0, b=1;
for (int i=2; i<=n; i++) {
    int t = a+b; a=b; b=t;
}
return b;

3. fib(0) and fib(1)

cout << fib(0); // 0
cout << fib(1); // 1

4. Memoization cache

if (memo[n] != -1)
    return memo[n];
memo[n] = fib(n-1)+fib(n-2);
return memo[n];

5. Bottom-up DP

dp[0]=0; dp[1]=1;
for (int i=2; i<=n; i++)
    dp[i]=dp[i-1]+dp[i-2];
return dp[n];

6. First six terms

// 0,1,1,2,3,5
for (int i=0; i<6; i++)
    cout << fib(i) << " ";

Iterative Factorial

Time: O(n)
Space: O(1)
Uses simple loop
No stack overhead
Best for performance

Recursive Factorial

Time: O(n)
Space: O(n) for stack
Elegant mathematical definition
Risk of stack overflow for large n
Slower due to function calls

Fibonacci Insights

Naive recursion: O(2ⁿ) - exponential!
Iterative/DP: O(n) - linear
Memoization: O(n) with recursion
Demonstrates importance of optimization
Classic example of overlapping subproblems

2. Recursion Stack Visualization

Understanding the call stack is crucial for debugging recursive functions. Each recursive call creates a new stack frame with its own parameters and local variables.

Stack Frame Anatomy for factorialRecursive(5)

Stack Frame #6: factorialRecursive(1)

n = 1

Base case reached!

Returns: 1

Frame destroyed after return

Stack Frame #5: factorialRecursive(2)

n = 2

Waiting for: factorialRecursive(1)

Will calculate: 2 * [result from frame #6]

Stack Frame #4: factorialRecursive(3)

n = 3

Waiting for: factorialRecursive(2)

Will calculate: 3 * [result from frame #5]

Stack Frame #3: factorialRecursive(4)

n = 4

Waiting for: factorialRecursive(3)

Will calculate: 4 * [result from frame #4]

Stack Frame #2: factorialRecursive(5) ← CURRENTLY EXECUTING

n = 5

Waiting for: factorialRecursive(4)

Will calculate: 5 * [result from frame #3]

Stack Frame #1: main()

Called: factorialRecursive(5)

Waiting for final result

Will print: 120

↑ Stack grows downward ↑ | Current execution marked

Stack Trace Examples

1. Depth parameter

long long fact(int n, int d=0) {
    // d tracks stack depth
    return n <= 1 ? 1 : n*fact(n-1,d+1);
}

2. Indent helper

void indent(int d) {
    for (int i=0; i<d; i++)
        cout << "|  ";
}

3. Log entry call

indent(d);
cout << "-> fact(" << n << ")\n";

4. Log base return

if (n <= 1) {
    indent(d);
    cout << "<- return 1\n";
    return 1;
}

5. fact(3) stack depth

// frames: fact(3), fact(2),
// fact(1) then unwind

6. fib(4) duplicate work

// fib(2) computed twice
// in naive fib(4) tree

Stack Overflow Dangers:

Each recursive call uses stack memory (typically 1-8 MB total)
Deep recursion can exhaust stack space
Common with: No base case, incorrect base case, too deep recursion
Symptoms: Program crashes with segmentation fault
Solutions: Use iteration, increase stack size, optimize recursion

3. When to Use Recursion vs Iteration: Decision Guide

Choosing between recursion and iteration depends on problem characteristics, performance requirements, and code clarity.

Problem Type	Use Iteration When...	Use Recursion When...
Tree/Graph Traversal	Not ideal Requires explicit stack/queue More complex implementation	Excellent fit DFS naturally recursive Clean, readable code Examples: Binary tree traversal
Mathematical Calculations	Usually better Factorial, Fibonacci (iterative) Better performance No stack overflow risk	Sometimes useful Matches mathematical definition Readable for simple cases Risk for large inputs
Divide and Conquer	Challenging Merge sort (iterative is complex) Quick sort (needs explicit stack)	Natural fit Merge sort (clean recursive) Quick sort (elegant recursive) Binary search (recursive)
Backtracking Problems	Very complex N-Queens (hard with iteration) Sudoku solver (messy iterative)	Perfect match N-Queens (clean recursive) Sudoku solver (elegant) Maze solving (natural)
Dynamic Programming	Usually preferred Bottom-up DP (iterative) Better space optimization No recursion overhead	Top-down approach Memoization (recursive + cache) Easier to implement initially Can be optimized later
File System Navigation	Complex Need explicit stack Harder to read/maintain	Ideal solution Directory traversal Clean, readable code Matches hierarchical structure
Performance Critical	Always better No function call overhead Better cache performance Predictable performance	Avoid if possible Function call overhead Stack memory usage Possible cache misses
Code Readability	Simpler for linear problems Easier for beginners Direct control flow	Elegant for certain problems Expresses problem nature Can be more declarative

Approach Examples

1. In-order tree walk

void inorder(TreeNode* n) {
    if (!n) return;
    inorder(n->left);
    cout << n->val << " ";
    inorder(n->right);
}

2. Iterative in-order

stack<TreeNode*> st;
while (cur || !st.empty()) {
    while (cur) { st.push(cur); cur=cur->left; }
    cur = st.top(); st.pop();
    cout << cur->val; cur=cur->right;
}

3. Binary search (recursive)

int bs(vector<int>& a, int lo, int hi, int x) {
    if (lo > hi) return -1;
    int m = lo + (hi-lo)/2;
    if (a[m]==x) return m;
    return a[m]<x ? bs(a,m+1,hi,x) : bs(a,lo,m-1,x);
}

4. Merge sort split

void mergeSort(vector<int>& v, int l, int r) {
    if (l >= r) return;
    int m = l + (r-l)/2;
    mergeSort(v,l,m); mergeSort(v,m+1,r);
}

5. Sum array (iterative)

int sum = 0;
for (int x : nums) sum += x;
cout << sum;

6. Sum array (recursive)

int sumRec(vector<int>& a, int i) {
    if (i >= (int)a.size()) return 0;
    return a[i] + sumRec(a, i+1);
}

4. Tail Recursion Optimization

Tail recursion occurs when the recursive call is the last operation in the function. Compilers can optimize tail recursion to avoid stack growth, making it as efficient as iteration.

Tail Recursion Pattern

// REGULAR RECURSION (not tail)
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // Multiplication AFTER call
}

// TAIL RECURSION (can be optimized)
int factorialTail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator); // Call is LAST operation
}

Tail Recursion Examples

1. Not tail: factorial

return n * fact(n-1);
// multiply AFTER call returns

2. Tail factorial

long long factT(int n, long long acc=1) {
    if (n <= 1) return acc;
    return factT(n-1, n*acc);
}

3. Tail sum 1..n

int sumT(int n, int acc=0) {
    if (n <= 0) return acc;
    return sumT(n-1, acc+n);
}

4. GCD (Euclid)

int gcd(int a, int b) {
    if (b==0) return a;
    return gcd(b, a % b);
}

5. Tail fibonacci

int fibT(int n,int a=0,int b=1) {
    if (n==0) return a;
    return fibT(n-1,b,a+b);
}

6. Regular sum (not tail)

return n + sum(n-1);
// addition after recursive return

Tail Recursion Rules:

Recursive call must be the LAST operation in the function
No operations should happen after the recursive call
Use accumulator parameters to carry results forward
Modern C++ compilers (GCC, Clang) optimize tail recursion with -O2 or -O3
MSVC may not optimize all tail recursion cases
Always check if your compiler optimizes tail recursion

5. Best Practices and Common Mistakes

Recursion Best Practices

Always define a base case first
Ensure progress toward base case
Use tail recursion when possible
Consider memoization for overlapping subproblems
Test with edge cases (0, 1, negative, large values)
Document recursion depth expectations
Consider iterative alternatives for performance

Common Recursion Mistakes

Missing base case (infinite recursion)
Base case never reached (incorrect progress)
Forgetting return statement in recursive case
Stack overflow with deep recursion
Exponential time complexity (Fibonacci naive)
Using recursion where iteration is better
Not considering memoization for repeated calculations

Good vs Bad Examples

1. BAD: no base case

int bad(int n) {
    return n * bad(n-1); // never stops
}

2. BAD: no progress

int stuck(int n) {
    if (n==0) return 0;
    return stuck(n); // same n
}

3. GOOD: base + step

int fact(int n) {
    if (n<=1) return 1;
    return n*fact(n-1);
}

4. GOOD: memo fib

if (memo.count(n)) return memo[n];
memo[n]=fib(n-1)+fib(n-2);
return memo[n];

5. GOOD: sum digits

int sumDig(int n) {
    if (n<10) return n;
    return n%10 + sumDig(n/10);
}

6. GOOD: tree traversal

void walk(FileNode* f, int d=0) {
    cout << string(d*2,' ') << f->name;
    for (auto* c : f->kids) walk(c,d+1);
}

Frequently asked questions

What happens if there is no base case?

Infinite recursion until stack overflow—program crashes.

Is recursion always slower?

Often due to call overhead, but clarity wins for tree problems; iteration can be faster for linear work.

What is tail recursion?

Recursive call is the last operation; compilers may optimize to iteration (not guaranteed in C++).