Recursion

A recursive function calls itself to solve a smaller version of the same problem. Recursion is elegant for problems that have a naturally self-similar structure — trees, divide-and-conquer algorithms, and mathematical sequences. Every recursive function needs a base case (when to stop) and a recursive case (how to reduce the problem).

Anatomy of a Recursive Function

cpp

#include <iostream>
using namespace std;

int factorial(int n) {
    // BASE CASE — stops the recursion
    if (n <= 1) return 1;

    // RECURSIVE CASE — calls itself with a smaller input
    return n * factorial(n - 1);
}

int main() {
    cout << factorial(5) << "\n";   // 120
    cout << factorial(0) << "\n";   // 1
    return 0;
}

Call stack for factorial(5):

factorial(5) = 5 * factorial(4)
                     4 * factorial(3)
                              3 * factorial(2)
                                       2 * factorial(1)
                                                1       ← base case
                                       2 * 1 = 2
                              3 * 2 = 6
                     4 * 6 = 24
factorial(5) = 5 * 24 = 120

Fibonacci Sequence

cpp

#include <iostream>
using namespace std;

// Naive recursive — O(2^n) — extremely slow for large n
int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// Memoised recursive — O(n)
#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];
}

int main() {
    for (int i = 0; i <= 10; i++) {
        cout << fibNaive(i) << " ";
    }
    cout << "\n";
    // Output: 0 1 1 2 3 5 8 13 21 34 55

    cout << fibMemo(50) << "\n";   // 12586269025

    return 0;
}

Warning: fibNaive(40) makes over a billion recursive calls. Always memoize or use iteration for Fibonacci in practice.

Binary Search (Recursive)

cpp

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

int binarySearch(const vector<int>& arr, int target, int low, int high) {
    // Base case — target not found
    if (low > high) return -1;

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

    if (arr[mid] == target) return mid;          // Found
    if (arr[mid] < target)                       // Search right half
        return binarySearch(arr, target, mid + 1, high);
    else                                          // Search left half
        return binarySearch(arr, target, low, mid - 1);
}

int main() {
    vector<int> sorted = {2, 5, 8, 12, 16, 23, 38, 45, 67, 90};

    cout << binarySearch(sorted, 23, 0, sorted.size() - 1) << "\n";  // 5
    cout << binarySearch(sorted, 99, 0, sorted.size() - 1) << "\n";  // -1

    return 0;
}

Tower of Hanoi

A classic recursion problem — move n disks from peg A to peg C using peg B:

cpp

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << "\n";
        return;
    }
    hanoi(n - 1, from, aux, to);   // Move n-1 disks: from → aux
    cout << "Move disk " << n << " from " << from << " to " << to << "\n";
    hanoi(n - 1, aux, to, from);   // Move n-1 disks: aux → to
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    // Move disk 1 from A to C
    // Move disk 2 from A to B
    // Move disk 1 from C to B
    // Move disk 3 from A to C
    // Move disk 1 from B to A
    // Move disk 2 from B to C
    // Move disk 1 from A to C
    return 0;
}

Minimum moves = 2^n - 1. For 3 disks: 7 moves. For 64 disks: 1.8 × 10^19 moves.

Directory Tree Traversal

Recursion is natural for hierarchical data like file systems:

cpp

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

struct FileNode {
    string name;
    bool   isDir;
    vector<FileNode> children;  // Only relevant for directories
};

void printTree(const FileNode& node, int depth = 0) {
    string indent(depth * 2, ' ');
    string icon = node.isDir ? "📁 " : "📄 ";
    cout << indent << icon << node.name << "\n";

    for (const auto& child : node.children) {
        printTree(child, depth + 1);   // Recursively print children
    }
}

int countFiles(const FileNode& node) {
    if (!node.isDir) return 1;
    int total = 0;
    for (const auto& child : node.children) {
        total += countFiles(child);   // Recursively count
    }
    return total;
}

int main() {
    FileNode root = {"project", true, {
        {"src", true, {
            {"main.cpp",  false, {}},
            {"utils.cpp", false, {}},
        }},
        {"include", true, {
            {"utils.h",   false, {}},
        }},
        {"CMakeLists.txt", false, {}},
        {"README.md",      false, {}},
    }};

    printTree(root);
    cout << "Total files: " << countFiles(root) << "\n";
    // 📁 project
    //   📁 src
    //     📄 main.cpp
    //     📄 utils.cpp
    //   📁 include
    //     📄 utils.h
    //   📄 CMakeLists.txt
    //   📄 README.md
    // Total files: 5

    return 0;
}

Tail Recursion

A function is tail-recursive when the recursive call is the very last operation — some compilers optimise this to a loop (tail call optimisation, TCO):

cpp

#include <iostream>
using namespace std;

// Regular recursion — accumulates a call stack
int factNormal(int n) {
    if (n <= 1) return 1;
    return n * factNormal(n - 1);  // Has to wait for result before multiplying
}

// Tail-recursive — accumulator carries the partial result
int factTail(int n, int accumulator = 1) {
    if (n <= 1) return accumulator;
    return factTail(n - 1, n * accumulator);  // Last operation IS the recursive call
}

int main() {
    cout << factNormal(10) << "\n";   // 3628800
    cout << factTail(10)   << "\n";   // 3628800
    return 0;
}

Note: C++ does not guarantee tail call optimisation (unlike Haskell or Scheme). For deep recursion in C++, convert to an iterative loop or use an explicit stack.

Recursion vs Iteration

Criterion	Recursion	Iteration
Code clarity	Often cleaner for trees/graphs	Often cleaner for sequences
Stack usage	O(depth) — can overflow	O(1) — no stack growth
Performance	Function call overhead	Generally faster
Debugging	Harder (multiple frames)	Easier
Best for	Trees, divide-and-conquer	Sequences, counting

Rule of thumb: Use recursion when the problem's structure is naturally hierarchical. Convert to iteration when the recursion depth could be large (> a few thousand levels).

Practical Example: Merge Sort

cpp

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

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else                   temp.push_back(arr[j++]);
    }
    while (i <= mid)   temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);

    for (int k = left; k <= right; k++) {
        arr[k] = temp[k - left];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;   // Base case: 0 or 1 element

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);        // Sort left half
    mergeSort(arr, mid + 1, right);   // Sort right half
    merge(arr, left, mid, right);     // Merge sorted halves
}

int main() {
    vector<int> data = {38, 27, 43, 3, 9, 82, 10};

    cout << "Before: ";
    for (int n : data) cout << n << " ";
    cout << "\n";

    mergeSort(data, 0, data.size() - 1);

    cout << "After:  ";
    for (int n : data) cout << n << " ";
    cout << "\n";
    // Before: 38 27 43 3 9 82 10
    // After:  3 9 10 27 38 43 82

    return 0;
}

Merge sort is O(n log n) — one of the most efficient general-purpose sorting algorithms. Its divide-and-conquer structure is a natural fit for recursion.

Summary

Every recursive function needs a base case (stops recursion) and a recursive case (reduces problem size)
Without a base case, recursion continues until the call stack overflows — a runtime crash
Classic recursive algorithms: factorial, Fibonacci, binary search, Tower of Hanoi, merge sort, tree traversal
Memoisation caches results to eliminate redundant recursive calls — transforms O(2^n) Fibonacci into O(n)
Tail recursion places the recursive call as the last operation — some compilers optimise it into a loop
For deep recursion, convert to an iterative solution with an explicit stack to avoid stack overflow
Recursion excels at hierarchical data (trees, file systems, JSON) where the structure mirrors the recursion

Next, we'll explore object-oriented programming — defining classes and creating objects in C++.