Recursive function

• A recursive function is a function that repeatedly calls itself.
• No limit is placed on the number of recursive calls.
• Create a shell script called fact.sh:

#!/bin/bash
# fact.sh - Shell script to to find factorial of given command line arg
factorial(){
  local i=$1
  local f
  declare -i i
  declare -i f
 
  # factorial() is called until the value of $f is returned and is it is <= 2
  # This is called the recursion
  [ $i -le 2 ] && echo $i || { f=$(( i - 1)); f=$(factorial $f); f=$(( f * i )); echo $f; }
}
 
 
# display usage
[ $# -eq 0 ] && { echo "Usage: $0 number"; exit 1; }
 
# call factorial
factorial $1

Save and close the file. Run it as follows:

chmod +x fact.sh
./fact.sh
./fact.sh 2
./fact.sh 5

Sample outputs:

2
120

• You can debug the script as follows:

bash -x ./fact.sh 5

Sample outputs:

+ '[' 1 -eq 0 ']'
+ factorial 5
+ local i=5
+ local f
+ declare -i i
+ declare -i f
+ [[ 5 -le 2 ]]
+ f=4
++ factorial 4
++ local i=4
++ local f
++ declare -i i
++ declare -i f
++ [[ 4 -le 2 ]]
++ f=3
+++ factorial 3
+++ local i=3
+++ local f
+++ declare -i i
+++ declare -i f
+++ [[ 3 -le 2 ]]
+++ f=2
++++ factorial 2
++++ local i=2
++++ local f
++++ declare -i i
++++ declare -i f
++++ [[ 2 -le 2 ]]
++++ echo 2
+++ f=2
+++ f=6
+++ echo 6
++ f=6
++ f=24
++ echo 24
+ f=24
+ f=120
+ echo 120
120

• Recursive functions are slow under bash.
• Avoid using recursive functions if possible.
• For serious number crunching take a look at the GNU C/C++/Fortran Compiler Collection (GCC).

External links

• Wikipedia:Recursion (computer science)
• GNU C/C++/Fortran Compiler Collection.