C++ Recursion

Recursion is a technique where a function solves a problem by calling itself with a smaller version of the same problem, until it reaches a case simple enough to answer directly. It matters because many problems — searching a sorted list, walking a tree, computing combinations, parsing nested data — are naturally defined in terms of themselves, and recursion lets you express that definition directly in code instead of simulating it with manual loops and stacks.

Overview: How Recursion Works

A recursive function is just a function that, somewhere in its body, calls itself. What makes this work — instead of looping forever — is that every recursive function needs two ingredients:

  • Base case: a condition simple enough to answer without another recursive call. This is what stops the recursion.
  • Recursive case: the function calls itself with an argument that is closer to the base case (smaller, shorter, simpler), and combines that result with some local work to produce the answer for the current call.

Under the hood, every function call in C++ — recursive or not — creates a new stack frame on the program’s call stack. A stack frame holds that call’s parameters, local variables, and the address to return to when the call finishes. When factorial(4) calls factorial(3), the computer does not overwrite the memory for factorial(4); it pushes a brand-new frame on top of the stack for factorial(3), with its own independent copy of n. Each nested call pushes another frame, and each return pops the top frame off the stack and hands its result back to the frame below it. This is why recursion can compute correct answers even though the "same" function is technically running multiple times at once — each call has its own private set of variables living in its own frame.

This also explains the danger of recursion without a base case (or one that’s never reached): the stack keeps growing, frame after frame, until it runs out of the memory reserved for it — typically a fixed region of a few megabytes. When that happens the program crashes with a stack overflow. Unlike a loop that just runs a long time, runaway recursion can crash the whole program almost immediately, because stack space is much smaller than heap space and each frame consumes some of it.

It’s worth knowing that some languages guarantee tail call optimization — rewriting a recursive call that is the very last operation in a function into a loop, reusing the same stack frame. C++ compilers may do this as an optimization at higher optimization levels (like -O2), but the C++ standard does not require it. Don’t rely on deep tail recursion being safe in C++; if you need to process millions of elements, prefer an explicit loop or verify your compiler’s behavior.

Syntax

There’s no special keyword for recursion — any ordinary function becomes recursive the moment it calls itself. The general shape looks like this:

ReturnType functionName(Parameters) {
    if (baseCondition) {
        return baseValue;          // stops the recursion
    }
    // do some work, then call the function again
    // with arguments that move toward the base case
    return functionName(smallerArguments);
}
Part Purpose
baseCondition Checked first on every call; when true, the function returns immediately without recursing further.
baseValue The known, directly computable answer for the simplest input (e.g. 0! or 1!).
functionName(smallerArguments) The recursive call. The arguments must shrink or move toward the base case, or the recursion never ends.
Combining work Code that uses the result of the recursive call (e.g. multiplying it by n) to build the answer for the current call.

Examples

Example 1: Factorial

The factorial of n (written n!) is the product of all positive integers up to n. It’s a classic first recursion example because its mathematical definition is already recursive: n! = n × (n-1)!, with 0! = 1 and 1! = 1 as the base case.

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

Output:

Factorial of 5 is 120

Each call to factorial either returns 1 immediately (base case) or returns n multiplied by whatever factorial(n - 1) eventually computes. The multiplications don’t actually happen until the recursion unwinds: the deepest call returns first, and each frame above it multiplies that result by its own n as control returns up the chain.

Example 2: Fibonacci Numbers

The Fibonacci sequence is defined recursively: fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for larger n. Notice this function has two recursive calls, not one.

#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() {
    for (int i = 0; i < 10; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
    return 0;
}

Output:

0 1 1 2 3 5 8 13 21 34

Because fibonacci calls itself twice, the number of calls grows exponentially with n — fibonacci(30) alone makes well over a million calls, many of them recomputing the same smaller Fibonacci numbers over and over. This is a good illustration of both the elegance and the cost of naive recursion; the Best Practices section below explains how to fix it with memoization.

Example 3: Recursive Binary Search

Binary search is a realistic, practical use of recursion: it repeatedly cuts a sorted range in half, which is exactly the kind of "solve a smaller version of the same problem" structure recursion is built for.

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target, int low, int high) {
    if (low > high) {
        return -1; // not found
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearch(arr, target, mid + 1, high);
    } else {
        return binarySearch(arr, target, low, mid - 1);
    }
}

int main() {
    vector<int> numbers = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
    int target = 23;
    int result = binarySearch(numbers, target, 0, numbers.size() - 1);
    if (result != -1) {
        cout << "Found " << target << " at index " << result << endl;
    } else {
        cout << target << " not found" << endl;
    }
    return 0;
}

Output:

Found 23 at index 5

Each call narrows [low, high] by discarding half the remaining range, so the recursion depth is only about log⊆(n) even for huge arrays — a good example of recursion being both natural and efficient when the problem size shrinks quickly.

Under the Hood: Tracing the Call Stack

To see the stack frames in action, trace factorial(4) step by step:

  • Call factorial(4): not base case, so it calls factorial(3) and waits.
  • Call factorial(3): not base case, so it calls factorial(2) and waits.
  • Call factorial(2): not base case, so it calls factorial(1) and waits.
  • Call factorial(1): base case reached — returns 1 immediately, popping its frame.
  • factorial(2) resumes, computes 2 * 1 = 2, returns 2, pops its frame.
  • factorial(3) resumes, computes 3 * 2 = 6, returns 6, pops its frame.
  • factorial(4) resumes, computes 4 * 6 = 24, returns 24, pops its frame.

At the deepest point, four stack frames exist simultaneously (for n = 4, 3, 2, 1), each with its own copy of n. Nothing is actually multiplied until the base case returns and the calls start unwinding back down to main. This push-then-unwind pattern is true of every recursive function: work often happens on the way back up the stack, not on the way down.

Common Mistakes

Mistake 1: Forgetting the Base Case

Without a base case, a recursive function never stops calling itself, and the program crashes with a stack overflow as soon as it runs out of stack memory:

// BUG: no base case -- this never stops recursing
int countDown(int n) {
    cout << n << endl;
    return countDown(n - 1);
}

Every call keeps decreasing n and calling itself again — forever (it will even keep going through negative numbers). The fix is to add a condition that stops the recursion and returns without calling the function again:

#include <iostream>
using namespace std;

void countDown(int n) {
    if (n <= 0) {           // base case stops the recursion
        cout << "Liftoff!" << endl;
        return;
    }
    cout << n << endl;
    countDown(n - 1);
}

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

Output:

5
4
3
2
1
Liftoff!

Mistake 2: A Wrong (Not Missing) Base Case

A base case that exists but returns the wrong value is a subtler bug — the program doesn’t crash, it just quietly produces a wrong answer:

#include <iostream>
using namespace std;

long long factorialWrong(int n) {
    if (n == 0) {
        return 0;  // BUG: should be 1, the multiplicative identity
    }
    return n * factorialWrong(n - 1);
}

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

Output:

5! = 0

Because every chain of multiplications eventually reaches factorialWrong(0), and that returns 0, the whole product collapses to zero no matter what n was. The fix is to use the correct identity value for the base case:

#include <iostream>
using namespace std;

long long factorialCorrect(int n) {
    if (n <= 1) {
        return 1;  // FIX: base case returns 1, the multiplicative identity
    }
    return n * factorialCorrect(n - 1);
}

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

Output:

5! = 120

This kind of mistake is a good reminder to always double-check base cases against the identity element of whatever operation you’re combining results with — 1 for multiplication, 0 for addition, an empty container for concatenation, and so on.

Best Practices

  • Always write the base case first and make sure it’s actually reachable from every recursive path.
  • Guarantee that each recursive call moves strictly closer to the base case (a smaller number, a shorter string, a narrower range) — otherwise you risk infinite recursion.
  • Watch recursion depth for large inputs; C++ stack space is limited (often just a few megabytes), and deep recursion can overflow it even when the logic is correct.
  • Don’t assume C++ will optimize tail calls into loops — it’s not guaranteed by the standard, so prefer an explicit loop for very deep, simple repetition.
  • When a recursive function recomputes the same subproblems repeatedly (like naive Fibonacci), add memoization — cache results in a vector or map keyed by the input — or switch to an iterative dynamic-programming approach.
  • Reach for recursion when the problem is naturally recursive — trees, graphs, divide-and-conquer algorithms, backtracking — and prefer plain loops for simple linear repetition.
  • Test edge cases explicitly: zero, negative numbers, empty containers, and the smallest valid input, since these are exactly where base-case bugs hide.

Practice Exercises

  • Write a recursive function long long power(int base, int exponent) that computes base raised to a non-negative integer exponent (hint: the base case is exponent == 0, which should return 1).
  • Write a recursive function bool isPalindrome(const string& s, int left, int right) that returns true if s reads the same forwards and backwards (hint: the base case is when left >= right).
  • Write a recursive function int sumDigits(int n) that returns the sum of the digits of a positive integer n (for example, sumDigits(1234) should return 10).

Summary

  • A recursive function calls itself to solve a smaller instance of the same problem.
  • Every recursive function needs a reachable base case and a recursive case that moves toward it.
  • Each call gets its own stack frame with independent parameters and locals; frames are pushed on call and popped on return, and combining work often happens as calls unwind.
  • Missing or incorrect base cases are the most common recursion bugs — missing ones crash with a stack overflow, wrong ones silently produce incorrect results.
  • C++ does not guarantee tail-call optimization, so deep recursion can still overflow the stack even when logically correct.
  • Use memoization or an iterative rewrite when a recursive solution recomputes the same subproblems repeatedly.