Recursion and Dynamic Programming

Factorial (Recursive)

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

Algorithm

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;
}

The pinned run is factorial(5). The diagrams separate the descent, the base case, and the return values so the stack does not feel invisible.

Step 1 - Descend to the base case

Each call waits for one smaller call until f(0) returns 1.

Call tree for factorial(5): f(5) waits on f(4), down to f(0).f(5)waitsf(4)waitsf(3)waitsf(2)waitsf(1)waitsf(0)base = 1

Step 2 - Base value starts the unwind

The first finished frame is f(0) = 1; f(1) can now compute 1 * 1.

Call stack just before unwind begins.top -> bottomknown returnf(0)1f(1)waitingf(2)waitingf(3)waitingf(4)waitingf(5)waiting

Step 3 - Unwind returns 120

Each frame multiplies its n by the completed smaller result.

Return chain for factorial(5).framecalculationreturnsf(0)base1f(1)1 * 11f(2)2 * 12f(3)3 * 26f(4)4 * 624f(5)5 * 24120

Complexity

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

Implementation notes

  • In C++, the function is int factorial(int n), so each recursive call receives its own copied int parameter and returns an int result.
  • The only base case in the checked source is if (n == 0) return 1;; there is no guard for negative inputs.
  • return n * factorial(n - 1); builds normal stack frames for f(5), f(4), f(3), f(2), f(1), and f(0) before the base case returns.
  • The trace shows the unwind values exactly: 1 * 1 = 1, 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24, and 5 * 24 = 120.
  • main stores factorial(5) in int result and prints it with std::cout << result << std::endl, producing 120.
  • Visible memory use is the call-stack frames only; there are no pointer or reference parameters and no heap container mutation. Larger inputs can exceed the range of C++ int, and this source does not add overflow handling.
base case `if (n == 0) return 1;`
recursive call `return n * factorial(n - 1);`