🎓 A1Learner
🔍
0 of 47 lessons completed

Bash Recursion

Recursion is when a function calls itself to solve a smaller piece of a job. A base case tells the function when to stop calling itself.

Count down with recursion

Each call prints its number and calls itself with one less. The base case prints Done when the number reaches zero.

countdown() {
  if [ "$1" -eq 0 ]
  then
    echo "Done"
    return
  fi
  echo "$1"
  countdown $(($1 - 1))
}
countdown 3

Add numbers with recursion

The function adds its number to the sum of all smaller numbers. The call for zero is the base case and echoes zero.

sum_to() {
  if [ "$1" -eq 0 ]
  then
    echo 0
    return
  fi
  prev=$(sum_to $(($1 - 1)))
  echo $(($1 + prev))
}
total=$(sum_to 4)
echo "The sum is $total"

Factorial with recursion

The factorial of a number multiplies it by the factorial of the number below it. The base case echoes one for an input of one or less.

factorial() {
  if [ "$1" -le 1 ]
  then
    echo 1
    return
  fi
  prev=$(factorial $(($1 - 1)))
  echo $(($1 * prev))
}
result=$(factorial 4)
echo "Factorial of 4 is $result"

Example

factorial() {
  if [ "$1" -le 1 ]
  then
    echo 1
    return
  fi
  prev=$(factorial $(($1 - 1)))
  echo $(($1 * prev))
}
result=$(factorial 5)
echo "Factorial of 5 is $result"

Key points

  • A recursive function calls itself inside its own body.
  • Each new call works on a smaller input than the last.
  • The base case is the test that stops the chain of calls.
  • Without a base case, the calls would never stop.
  • A recursive function can echo a result for $( ) to capture.
  • Recursion suits jobs built from repeated smaller steps.

In this example, factorial calls itself with a smaller number each time. The calls stop at one, which echoes the base value one. Each waiting call then multiplies its number as the results come back, giving 120.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why does a recursive function need a base case?