Factorial (Recursive)

factorial(0) = 1, otherwise factorial(n) = n * factorial(n - 1). The smallest example of recursion with a single base case.

Algorithm

Canonical input n = 5 descends through six call frames and unwinds through five multiplications. Final result 120.

Basic Implementation

basic.cpp

#include <iostream>

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);
    std::cout << result << std::endl;
    return 0;
}

Complexity

Time: O(n)
Space: O(n) call stack

Implementation notes

C++: same recursive shape as the other languages, with int factorial(int n) documenting the integer contract.
The replay treats the call stack as a vertical list of frames; descent pushes, unwind pops with the computed multiplication shown.

base case `if (n == 0) return 1;`

recursive call `return n * factorial(n - 1);`