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

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"

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.

Step 2 - Base value starts the unwind

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

Step 3 - Unwind returns 120

Each frame multiplies its n by the completed smaller 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`.