Bash recursion examples - part 1

Bash recursion examples - part 1

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

Recursion in computer science is a technique based on two cases. One is non-recursive terminating case, the other, recursive. The former finds you the final solution, the latter reduces problem to the termination case. This is I guess the most important bit, one should remember about recursion in general.

One can also describe recursion in in layman's terms, perhaps like this: Imagine, you would like to have an orange. You take one, and peel a bit of its skin off, you look at it, it's not quiet ready to have yet, so you remove another bit, posibly repeating the activity a couple of times before you notice, that only one, small, bit of skin is still left over on the orange. You've just arrived at your terminating case. You peel off the bit and have your orange. You've just completed recursive task.

As far as BASH, but also many other programming languages are concerned, it is mostly functions that are used for soliving recursive problems on the computer.

These functions are very much like loops. You defined an exit condition in one, then you add a chunk of code that reduces the whole case to something a step simpler, once that is done, you call the function again from within to repeat the step. Eventually you reach the terminating case and you are done, ... or you get into infinite execution of the function, which quickly results in unresponsive terminal.

Sooner rather than later the whole box is choking as your processor cannot deal with the amount of operations you have just burdened it with. You see the same when you enter an infinite loop. Recursion with functions is faster at rendering your computer unresponsive. Hence, unless your are extremely careful when programming (personally I don't know a single person who tried to write a recursive program and hasn't gone into an infinite program execution in their attempts at least once) you shoule be prepared to handle this sort of self-conjured abuse.

Dealing with misbehaving recursive code in Bash

Below is a chunk of code that stops recursive functions going rogue.


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 in Bash examples

In Maths there are many functions that rely on recursion. Below I define some of them recursively using BASH. At this point it is important to know that BASH is not for floating-point arithmetics. It is good only at integer arithmetics. If you need floats, you'll be better of writing your pogram in a language like Python.


# 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))
}

The above code will find sum of first n numbers from 1 to $1. In the body of the function there is a call to recursive(), that's how you would use it.

As it was said earlier, the call will prevent summation() looping endlessly should there be an error. If you want it not to show all the info about number of calls set $1 to 1. You can also change number of allowed calls by setting $2 to some large number - 150 perhaps.


$ summation 100

should echo 5050 in your text console.

Your terminal condition is $count < 1. $count is based on the difference between $1 and 1, which is 99 in the above case. Recursive step is resolved gradually by calling summation() repeatedly, each time with $1 less 1 ( at the bottom of the function ). Eventually you get to the case where $1 is 0, which is the call that the behind-termination-condition piece of code will handle. In that piece function will be finally allowed to output a total from all the calls and return.

Here is recursively defined product function:


# 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 ))
}

and you call it like this:


product 10

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


## 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.

Next up is resursively defined factorial. It uses product() internally. After all, factorial (n!) is a product of positive integers up to n with empty product (n!) being 1.


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 ).

A lot of other maths functions can be defined like this, or perhaps more concisely using loops.

No article on the subject of recursion can be considered complete unless it contains a function that computes a term of fiboncci sequence. Below is one such function I have coded:


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.

Recursion in BASH - part 2

I hope you've found this article informative and enjoyable. In the second part on recursive functions I'll focus more on recursive functions beyond Maths.

This post was updated on 25 May 2017 16:16:11

Tags:  BASH ,  recursion 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2019 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

Post navigation

Previous:
  Env and BASH declare

Next:
  Essential WordPress plugin hooks