Bash recursion examples - part 1

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 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.

Copyrights

©Copyright, 2022 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Bash recursion examples - part 1." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/bash-recursion-examples-part-1

Add Comment

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]


I constent to processing my data given through this form for purposes of a reply by the administrator of this website.

Recent Comments

Nobody has commented on this post yet. Be first!

Post navigation

Previous:
  Env and BASH declare

Next:
  Essential WordPress plugin hooks