Bash recursion examples - part 1

Created:15 Jan 2017 16:58:45 , in  Maths

Some recursive functions written in BASH

Dealing with misbehaving recursive code in Bash

Below is a chunk of code that stops recursive function. Better stop it than be sorry.

declare -i recursion_level=1
declare -i exit_recursion_level=120
recursive(){
  local -i quiet=${quiet:-${1:-1}}
  (( $quiet )) || { echo "Recursion level is: $recursion_level"; }
  (( $recursion_level == $exit_recursion_level )) && { echo "Recursion level too hight. Exiting ...";exit 1; } 
  (( recursion_level++ ))
}  

And here is how you call the recursive() within the body of another function. Both, first and second argument to recursive are optional.

$ recursive 1 # quiet execution
$ recursive 0 # with recursion level echoed
$ recursive 0 10 # quiet + terminates after 10 calls to a function, recursive() is in the body of. 

If you want to test the function, perhaps this loop will help:

level=0
while [[ $level -lt 105 ]] ; do
  recursive 0
  ((level++))
  echo $level
done  

Once you are done with your recursive code you can remove call to recursive from it.

Recursion and BASH

# basic summation of positive integers from 1 to $1
summation() {
  recursive
  (( $1 < 0 )) && { echo "Argument error: Number of digits must be a non-negative integer"; exit 1; }
  local -i val=${val:-($1)}
  local -i count=$(( $1 - 1 ))
  if (( $count < 1 )); then
        echo $val
        return
  fi
  ((val += $1 - 1 )) 
  summation $(($1 - 1))
}

Run it:

$ summation 100

should echo 5050 in your text console.

# product recursive function
product(){
  recursive 0
  (( $1 < 0 )) && { echo "Argument error: Number of digits must be a non-negative integer"; exit 1; } 
  local -i val=${val:-($1)}
  local -i count=$(( $1 - 1 ))
  if (( $count < 1 )); then
        echo $val
        return
  fi
  ((val *= ($1 - 1) ))
  (( count-- )) 
  product $(( $1 - 1 ))
}

Call it:

product 10

Another example is a summation function that takes values within a given range and returns their total:

## summation for a range of integers, (excludes first value)
#( change <= to < to make it inclusive)
range_summation() {
  recursive
  local -i val=${val:-($2)}
  local -i count=$(( $2 - $1 ))
  if (( $count <= 1 )); then
        echo $val
        return
  fi
  ((val += ($2 - 1) ))
  (( count-- )) 
  range_summation $1 $(( $2-1 ))
}

Call it:

$ range_summation -5 5

Attributes are: $1 - start of the range, $2 - end of the range. $1 <= $2 for simplicity.

Factorial function comes up next. It uses product() internally.

factorial(){
  (( $1 == 0 )) && { echo 1; exit; }
  product $1
}

Call it:

$ factorial 5

to get 120

range_product function is similar to range_summation(). It finds a product of numbers within a range.

range_product() {
  recursive 1
  local -i val=${val:-($2)}
  local -i count=$(( $2 - $1 ))
  (( $count <= 1 )) && { echo $val; return; }
  ((val *= ($2 - 1) ))
  (( count-- )) 
  range_product $1 $(( $2-1 ))
}

$ range_product 2 5

BASH has means to find powers of numbers defined already: (( a ** b )), but it did not stop me to define my own power function:

# Raise number to a power
# power number power
power(){
  recursive
  local -i val=${val:-($1)}
  local -i count=$(( $2 ))

  (( $count == 0 )) && { echo 1; return; }
  (( $count < 0 )) && { echo "Error: Exponent less than 0"; exit 1; }
    
  (( $count <= 1 )) && { echo $val; return; }

  ((val *= $1 ))
  (( count-- )) 
  power $1 $(( $2 - 1 ))
}

call it:

$ power 2 7

to get 128. (Fraction based powers are not allowed in BASH ).

Fiboncci sequence:

fibonacci() {
  recursive
  (( $1 < 2 )) && { echo "Error: n is too small! It must be at least 2."; exit 1; }
  local -i val1=${val1:-${2:-(0)}}
  local -i val2=${val2:-${3:-(1)}}
  local -i val3=
  local -i count=$1
  
  (( $count <= 2 )) && { echo $val2; return; }
  
  val3=$(( $val1  + $val2 ))
  val1=$val2
  val2=$val3
  
  (( count-- )) 
  fibonacci $count
}

Two starting values for the function can be 0 and 1, 1 and 1 or perhaps something like 5 and 8. In any case, it should be two consecutive terms of fibonacci sequence.

The function can be called like this:

$ fibonacci 5

It will use 0 and 1 as its starting values and retrn the fifth term of fibonacci sentence (3).

$ fibonacci 5 1 1

It will use 1 and 1 as its starting values. However the output will be 5.

This post was updated on 06 Oct 2021 21:02:07

Tags:  BASH ,  recursion