C++ Recursion: Call Stack Mechanics, Invariants & Tail Optimization

Recursion is an algorithmic technique where a function calls itself to solve smaller instances of the same problem. Every properly constructed recursive function must have two components: a Base Case (which terminates the recursion) and a Recursive Step.

Tail-Recursive Factorial with $O(1)$ Stack Optimization

#include <iostream>

// Standard non-tail recursion (Builds up call stack O(N))
unsigned long long factNormal(int n) {
    if (n <= 1) return 1;
    return n * factNormal(n - 1); // Multiplication happens AFTER return!
}

// Tail-recursive version (Accumulator passes state forward)
unsigned long long factTail(int n, unsigned long long accumulator = 1) {
    if (n <= 1) return accumulator;
    return factTail(n - 1, n * accumulator); // Tail call! Compiler optimizes to loop!
}

int main() {
    std::cout << "10! = " << factTail(10) << std::endl; // 3628800
    return 0;
}