Recursive Functions

Intermediate~20 min read

Bash supports recursion, though iteration is usually preferred for performance. Still, recursion is handy for problems like factorial or walking directory trees.

Factorial

Define a base case for n <= 1 and recurse for n * factorial(n-1).

Directory Traversal

Walk a directory by listing entries and recursing into subdirectories.

Output

Click Run to execute your code

Watch out: Deep recursion can hit system limits. Prefer loops for large traversals.

Pro Tip: Memoization (caching results) can dramatically speed up recursive functions like Fibonacci.

Caution: Beware of globbing and unquoted variables in recursive walkers; always quote paths.

Common Mistakes

1) Missing base case

# Wrong
fact() { echo $(( $1 * $(fact $1) )); }

# Correct
fact() { local n=$1; (( n <= 1 )) && echo 1 || echo $(( n * $(fact $((n-1))) )); }

2) Unquoted paths in traversal

# Wrong
for f in $dir/*; do echo $f; done

# Correct
for f in "$dir"/*; do echo "$f"; done

Exercise: Recursive Fibonacci

Task: Implement fib that prints the nth Fibonacci number recursively.

Define fib(0)=0 and fib(1)=1.
Return non-zero on invalid input.

Output

Click Run to execute your code

Show Solution

fib() {
  local n=$1
  [[ $n =~ ^[0-9]+$ ]] || return 1
  if (( n <= 1 )); then echo "$n"; else echo $(( $(fib $((n-1))) + $(fib $((n-2))) )); fi
}

fib 8  # 21

Summary

Always include a clear base case.
Recursion is expressive but may be slower than loops in Bash.
Use recursion selectively for clarity or small problem sizes.

What's Next?

Up next: working with input and output in Reading Input.

Previous Function Scope

Next Reading Input