Recursive Bash Functions

Analogy categoryAnalogies

How Recursion Works in Bash

Because Bash functions are just named command sequences, nothing stops a function from calling itself, and each call gets its own set of local variables and positional parameters pushed onto a call stack, exactly like recursive calls in any language. A recursive function needs a base case that stops the recursion and a recursive case that makes measurable progress toward that base case on every call; without both, the function recurses until it hits Bash's function nesting limit and errors out with 'maximum function nesting level exceeded.'

🏏

Cricket analogy: A cricket tournament's knockout bracket is inherently recursive: each round calls the same 'play a match, advance winner' logic on a smaller bracket, until the base case of a single final match remains.

Writing a Correct Base Case

The base case must be checked before the recursive call, and it must be reachable — meaning every recursive call passes an argument that is strictly closer to satisfying the base case, such as a decrementing counter or a shrinking directory path. A classic factorial or directory-walking function should return immediately (via return, printing to stdout as needed) once the base condition is met, rather than falling through into another recursive call.

🏏

Cricket analogy: A DRS review process has a hard stop: once the third umpire confirms the on-field decision or overturns it, the review ends — there's no infinite chain of re-reviews, exactly like a required base case.

bash

#!/usr/bin/env bash
set -euo pipefail

# Recursive directory size walker with an explicit base case
count_files() {
    local dir=$1
    local count=0

    # Base case: not a directory, nothing to recurse into
    if [[ ! -d "$dir" ]]; then
        echo 0
        return 0
    fi

    local entry
    for entry in "$dir"/*; do
        [[ -e "$entry" ]] || continue
        if [[ -d "$entry" ]]; then
            local sub
            sub=$(count_files "$entry")   # recursive call, smaller subtree
            count=$(( count + sub ))
        else
            count=$(( count + 1 ))
        fi
    done

    echo "$count"
}

total=$(count_files "/etc")
echo "Files under /etc: $total"

Stack Limits and When to Avoid Recursion

Bash enforces FUNCNEST (default unset, but the shell has an internal nesting ceiling, commonly around 1000-8000 depending on build and ulimit -s) and will abort with 'maximum function nesting level exceeded' if exceeded. Because each recursive call in Bash also spawns subshells for command substitution (as in the count_files example), deep recursion is both slower and more memory-hungry than an equivalent loop. For anything with genuinely unbounded depth — like traversing an arbitrarily deep filesystem tree — prefer an explicit stack (an array used as a LIFO) with a while loop, or delegate to find, which is implemented natively and doesn't hit shell recursion limits at all.

🏏

Cricket analogy: A never-ending Super Over rule in a T20 match (before boards added tie-breaker rules) would be like unbounded recursion — the format needs an explicit cutoff, or the match literally cannot end.

For directory traversal specifically, prefer find /path -type f | wc -l over a hand-written recursive Bash function. find is implemented in C, walks the tree natively without spawning a subshell per directory, and has no risk of hitting Bash's function nesting limit on deep trees.

Each recursive call that uses $(recursive_func ...) for its return value spawns a new subshell, meaning any local state and even variables set with declare inside that subshell are invisible to the parent after it returns except through the captured stdout. This makes deep recursive command substitution both slow and easy to get wrong — verify with a small ulimit -s test before trusting a recursive function on genuinely large inputs.

Bash functions can call themselves; each call gets its own local variables and positional parameters.
Every recursive function needs a reachable base case checked before the recursive call.
Bash enforces a function nesting limit and errors with 'maximum function nesting level exceeded' if exceeded.
Recursive calls using $(...) spawn subshells, adding overhead beyond just the call stack.
For genuinely unbounded depth (e.g. deep directory trees), prefer an explicit array-based stack with a while loop.
find and similar native tools avoid Bash's recursion limits entirely for filesystem traversal.
Always test recursive functions against worst-case input depth before relying on them in production.