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

using System;

class Program {
	static int Factorial(int n) {
		if (n == 0) {
			return 1;
		}
		return n * Factorial(n - 1);
	}

	static void Main() {
		int result = Factorial(5);
		Console.WriteLine(result);
	}
}

Complexity

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

Implementation notes

C#: same recursive shape as the other languages, with static 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 `n * Factorial(n - 1)`