Recursion
In this page:
A Simple Recursive Function: Factorial
A recursive function needs a base case that returns directly without recursing (here, n <= 1) and a recursive case that calls itself with a smaller input (here, n - 1), combining the result with the current step. Without the base case, the function would keep calling itself indefinitely.
Example: A Simple Recursive Function: Factorial
#!/bin/bash
factorial() {
local n=$1
if (( n <= 1 )); then
echo 1
return
fi
local sub_result
sub_result=$(factorial $(( n - 1 )))
echo $(( n * sub_result ))
}
factorial 5
Login to try C/C++/Java/PHP code in the editor
Recursive Sum of a Range
This recursive function sums numbers from 1 up to n by adding n to the recursive result of summing 1 up to n - 1, stopping once n reaches 0. Each call uses local so its own copy of n and the subtotal doesn't interfere with other calls on the call stack.
Example: Recursive Sum of a Range
#!/bin/bash
sum_to() {
local n=$1
if (( n <= 0 )); then
echo 0
return
fi
local rest
rest=$(sum_to $(( n - 1 )))
echo $(( n + rest ))
}
result=$(sum_to 4)
echo "Sum from 1 to 4 is $result"
Login to try C/C++/Java/PHP code in the editor
Why local Matters More in Recursion
In a recursive function, every active call has its own independent set of local variables sitting on the call stack, which is essential since multiple calls to the same function are 'in flight' simultaneously. Without local, all those calls would share and stomp on a single global variable, producing wrong results.
Example: Why local Matters More in Recursion
#!/bin/bash
count_down() {
local n=$1
echo "At level: $n"
if (( n > 0 )); then
count_down $(( n - 1 ))
fi
echo "Back at level: $n"
}
count_down 3
Login to try C/C++/Java/PHP code in the editor
Recursion Depth Is Limited in Practice
Bash does not optimize tail calls the way some functional languages do, and each recursive call consumes stack space, so very deep recursion (thousands of levels) can hit resource limits and fail. For anything with a large, unbounded input size, an iterative loop is generally the safer and faster choice in Bash.
Warning: For loops that could run thousands of times, prefer an iterative while/for loop over recursion in Bash.
Example: Recursion Depth Is Limited in Practice
#!/bin/bash
countdown_safe() {
local n=$1
if (( n <= 0 )); then
echo "Done"
return
fi
countdown_safe $(( n - 1 ))
}
countdown_safe 10
Login to try C/C++/Java/PHP code in the editor
- Forgetting a base case (a stopping condition), which causes the function to call itself forever until Bash hits its maximum function nesting depth and errors out.
- Assuming recursive Bash functions are fast or efficient for deep recursion; each call adds real overhead, and Bash is not optimized for recursion the way some languages are, so it's best kept shallow.
- Forgetting to use
localfor the function's own working variables in a recursive function; without it, each recursive call would clobber the same global variable instead of each call having its own value.
- Every recursive function needs a base case that stops the recursion, and a recursive case that calls itself with a smaller/simpler input.
- Bash enforces a maximum function nesting depth (
FUNCNEST, unlimited by default but bounded by system stack limits in practice); runaway recursion eventually errors out rather than hanging forever. - Local variables are especially important in recursive functions since each call needs its own independent copy of working variables.
- Recursive functions typically return their result via
echoand command substitution, just like any other function returning data.
Chapter Quiz — Complete all 11 topics to unlock
0/11 topics done
Complete these topics first: