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.java

public class Basic {
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println(result);
    }

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

Complexity

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

Implementation notes

Java: same recursive shape as the other languages.
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);`