![Bash recursion examples - part 1 Bash recursion examples - part 1](https://swww.com.pl/media/img/post/22_head.jpg)
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
Author, Copyright and citation
Author
![Sylwester Wojnowski](https://swww.com.pl/media/img/gravatar_110.png)
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, 2024 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://swww.com.pl//main/index/bash-recursion-examples-part-1
Add Comment