Deeper into Function Complexities with Shell Scripting – Part VII

My previous article on 「Understanding and Writing functions in Shell Scripts」 might have given you a basic idea on how to write functions under shell scripts. Now it is time to get deeper into functional features like the usage of local variables and recursion.

Function Complexities with Shell Scripting Local Variables

What makes a variable local? It depends on that particular block where the variable is declared. A variable declared as local will be accessible from that block of code where it appears i.e. its scope is local. In order to explain this thing let’s look into one example below.

#!/bin/bash 

func( ) { 
	local i=10 
	j=20 
	echo "i from func = $i" 
	echo "j from func = $j" 
} 

echo "i outside func = $i" 
echo "j outside func = $j" 

func 

echo "i outside func = $i" 
echo "j outside func = $j" 

exit 0

On executing the above script the output will be.

i outside func = 
j outside func = 
i from func = 10 
j from func = 20 
i outside func = 
j outside func = 20

This is because the function func has not yet called while the first 2 echo statements were executed. After calling the function func the same 2 echo statements produce a different result. Now the variable j, which was declared inside func and not local, could be accessed afterwards.

Thus value for j becomes 20. What about the local variable i? Since its scope was inside the function func, value 10 could not be accessed from outside. Note that the variable j normally declared inside func is global by default.

Now you are familiar with local variables and how to use them inside function blocks. Let us move on to the most interesting section under functions, the recursion.

What is Recursion?

A function calling itself is generally termed as the recursion procedure. Or it can be defined as expressing an algorithm by using a simpler version of that same algorithm. Consider the example of finding factorial of a number. We know that n! = 1 x 2 x 3 x … x (n-1) x n. Thus we can write a recurrence relation as:

n! = (n-1)! x n

So its easy for us to recursively call the same function and use the return value from each call to multiply with the previous result, i.e.

5! = 4! x 5
4! = 3! x 4
3! = 2! x 3
2! = 1! x 2
1! = 0! x 1

Recursion using Local Variables

Here we try to write a script for finding factorial of a number using local variables and recursion.

#!/bin/bash 

fact( ) { 
	local num=$1 
	if [ $num -eq 0 ]; then 
		ret=1 
	else 
		temp=$((num-1)) 
		fact $temp 
		ret=$((num*$?)) 
	fi 
	return $ret 
} 

fact 5 

echo "Factorial of 5 = $?" 

exit 0

num is a local variable used to store each n-1 value on each call. Here the base condition checks whether the number is equal to zero or not (since 0! = 1 and factorial is not defined for negative numbers). On arriving this base condition it returns the value 1 to its caller. Now num = 1 and ret = 1 x 1.

At this instant it returns 1 to its caller. Now num = 2 and ret = 2 x 1 and so on. Finally when num = 5 return value will be 24 and final result is ret = 5 x 24. The final result 120 is passed down to the initial caller statement and is displayed.

There is one problem in the above script. As I explained in the previous article, functions cannot return large integers. So its left to users to find a solution for the above issue.

Q. Can we perform recursion without using local variables? Answer is Yes.

Recursion without Local Variables

Look at the following example for displaying the Fibonacci series using recursion. The basic recurrence relation is:

fib(0) = 0 
fib(1) = 1 
else 
	fib(n) = fib(n-1) + fib(n-2)

Fibonacci series using recursion

#!/bin/bash 

fib( ) { 
	a=$1 
	if [ $a -lt 2 ]; then 
		echo $a 
	else 
		((--a)) 
		b=$(fib $a) 

		((--a)) 
		c=$(fib $a) 

		echo $((b+c)) 
	fi 
} 

for i in $(seq 0 15) 
do 
	out=$(fib $i) 
	echo $out 
done 

exit 0

No local variables are used in the above script. I hope you can understand the flow of script during execution.

Here the value 15 represents the number of terms in the Fibonacci series to be displayed. Did you notice anything special regarding the execution of above script. It takes a while, doesn’t it? Recursion in a script is slower than a recursion in programming languages like C.

With this article, I plan to conclude the functions part in shell scripting. Stay updated with Tecmint to have the upcoming articles on arrays and much more…