Recursion Problems & Patterns

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem becomes small enough to answer directly. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem down and calls itself. Get the base case wrong and the function never stops — it recurses until the call stack overflows.

The two parts of every recursion

Think of recursion as a promise: "if you give me a smaller version of this problem, I will solve it." The recursive case keeps shrinking the input and trusting that promise. The base case is where the shrinking stops and a direct answer is returned. Without a base case, or with one the recursion never reaches, the function loops forever.

#include <iostream>
using namespace std;

// factorial(n) = n * (n-1) * ... * 1
long long factorial(int n) {
    if (n <= 1) {          // BASE CASE: factorial of 0 or 1 is 1
        return 1;
    }
    return n * factorial(n - 1); // RECURSIVE CASE: shrink n by one
}

int main() {
    cout << factorial(5) << endl; // 120
    return 0;
}

Tracing factorial(5): it waits for factorial(4), which waits for factorial(3), down to factorial(1) which returns 1. Then the calls resolve back up: 1, 2, 6, 24, 120. That stacking and unwinding is the call stack at work.

How recursion uses the call stack

Each recursive call pushes a frame onto the system call stack holding its parameters and where to return. The deepest call resolves first, and the stack unwinds in reverse — pure LIFO behaviour, the same as a stack data structure. This is why very deep recursion can crash with a stack overflow: there is only so much stack space.

Common recursion patterns

A few shapes appear again and again:

• Linear recursion — one recursive call per step, like factorial or summing a list.
• Binary recursion — two calls per step, like computing Fibonacci numbers or traversing a binary tree.
• Divide and conquer — split the problem in half, solve each half, combine. Merge sort and binary search follow this.
• Backtracking — try a choice, recurse, and undo it if it leads nowhere. Used for puzzles, permutations, and maze solving.

Here is a divide-and-conquer example that recursively reverses a string:

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

// Reverse the substring between indices left and right, in place.
void reverse(string& s, int left, int right) {
    if (left >= right) {      // BASE CASE: pointers met or crossed
        return;
    }
    swap(s[left], s[right]);  // fix the outermost pair
    reverse(s, left + 1, right - 1); // RECURSIVE CASE: shrink the window
}

int main() {
    string word = "jalgaon";
    reverse(word, 0, word.size() - 1);
    cout << word << endl; // noaglaj
    return 0;
}

Each call handles one pair of characters and hands the smaller middle to the next call. The base case fires when the window is empty.

Recursion versus iteration

Anything you can write recursively, you can write with a loop, and vice versa. Recursion often reads more naturally for problems that are themselves recursive — trees, divide-and-conquer, backtracking. Loops avoid the call-stack overhead and never overflow. The cost of recursion is the extra stack frames; the benefit is clarity. Choose for readability when performance allows, and convert to iteration when recursion depth threatens the stack.

Common mistakes

• Missing or unreachable base case. This is the number one bug. If the recursion never hits its stopping condition, it overflows the stack and crashes.
• Not shrinking the problem. The recursive call must move toward the base case. Calling factorial(n) instead of factorial(n - 1) loops forever.
• Redundant recomputation. Naive binary recursion (like plain Fibonacci) recomputes the same values exponentially many times. Caching results (memoisation) fixes this.
• Ignoring stack depth. Deep recursion on large inputs can exhaust the stack. For very deep cases, an iterative version with an explicit stack is safer.
• Confusing the wind-up and unwind phases. Work done before the recursive call happens on the way down; work after it happens on the way back up. Mixing these produces wrong output.

FAQ

Why does my recursion crash with a stack overflow? Almost always a base-case problem: it is missing, wrong, or never reached because the input is not shrinking toward it.

Is recursion slower than a loop? It can be, because of the per-call stack overhead. For simple linear cases a loop is usually faster, but for naturally recursive problems the clarity often outweighs the cost.

Keep learning

Understand the stack that powers recursion, see divide-and-conquer in action in Merge Sort, and browse the full DSA hub.

Want to drill recursion patterns with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.