Recursion - Bash DSA

The textbook recursive factorial(n) = n * factorial(n - 1) with factorial(0) = 1. Shows the call stack growing and unwinding through six frames for n = 5.

Algorithm

Canonical input is factorial 5. The unwind multiplies 1 * 1, 2 * 1, 3 * 2, 4 * 6, 5 * 24 and prints 120.

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
factorial() {
	local n=$1
	if [ "$n" -eq 0 ]; then
		echo 1
		return
	fi
	local sub
	sub=$(factorial $((n - 1)))
	echo $((n * sub))
}

result=$(factorial 5)
echo "$result"

Complexity

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

Implementation notes

Bash: the recursive function echoes its return value because there is no native integer return channel; the caller reads it back with sub=$(factorial $((n - 1))). Each $(...) spawns a subshell, which is fine here because factorial reads no shared state.
local n=$1 shadows the recursive frames; without local, every recursive call would clobber the parent frame's n.
The replay shows the call stack as [f(5), f(4), ..., f(0)] on the descent and the multiplicative reduction on the unwind.

base case `factorial(0)` echoes `1`. Without it the recursion would never bottom out.

recursive step `factorial(n)` calls `factorial(n - 1)`, reads the result back through command substitution, and echoes `n * sub`.