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

use strict; use warnings;

sub factorial {
	my ($n) = @_;
	if ($n == 0) {
		return 1;
	}
	return $n * factorial($n - 1);
}

my $result = factorial(5);
print "$result\n";

Complexity

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

Implementation notes

Perl: same recursive shape as the other languages, with sub factorial { my ($n) = @_; ... } documenting the integer contract by convention (Perl is duck-typed; the lesson contract relies on caller hygiene).
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)`