Recursion in programming is when a piece of code (usually a function) calls itself. If there is no exit case, the program will go on forever. We will be discussing recursion in a bash script with examples and discussing some peculiarities of the bash shell, such as local variables.
Setup
Let’s make a shell script. In your favourite editor type
#!/bin/bash
And save it somewhere as recurse.sh. Now we need to make it executable as follows:
[ahmed@amayem ~]$ chmod +x ./recurse.sh
[ahmed@amayem ~]$ ./recurse.sh
Looks good so far.
Building a recursive function
Calling yourself
To make a function recursive you just have to call the name of the function.
recurse()
{
recurse
}
recurse
This function is pretty useless, it will simply keep calling itself till the shell runs out of memory for that script. Let’s give it a try anyways:
[ahmed@amayem ~]$ ./recurse.sh
Segmentation fault: 11
The segmentation fault indicates that we ran out of space. If we add an echo hello before the recurse command in the function then we would see a huge number of hellos outputted before we see the segmentation fault. To stop the segmentation fault we need to add a base case, which can also be called an exit case.
Adding a base/exit case with a global variable
We need to make a case that will stop the recursion:
declare -i count=0
recurse()
{
if [ $count -lt 5 ]
then
echo $count
recurse
fi
}
recurse
We added a declare -i count=0 in the beginning to decide the base case. We limit the recursion by wrapping the command recurse in the function with an if statement. The condition of the if statement is $count -lt 5. So as long as the count is less than 5 then the function will recurse. Let’s run it and see:
[ahmed@amayem ~]$ ./recurse.sh
0
0
… (truncated output)
Segmentation fault: 11
Looks like something went wrong. Clearly count isn’t increasing. We forgot to increment count. To ensure that count is increasing we have to add ((count++)), but where should we put it.
Incrementing count after the recurse command
declare -i count=0
recurse()
{
if [ $count -lt 5 ]
then
echo $count
recurse
((count++))
fi
((count++))
}
recurse
We put ((count++)) after the recurse command, which means that the shell will never reach that command because it would keep recursing before it reached the incrementation. The shell would never exit the recursion because count is never increased. The resulting output is the same as before. Instead let’s try to increment before the recurse command
Incrementing count before the recurse command
declare -i count=0
recurse()
{
((count++))
if [ $count -lt 5 ]
then
echo $count
recurse
fi
}
recurse
This is much better. Let’s try it out:
[ahmed@amayem ~]$ ./recurse.sh
1
2
3
4
Voila we have success.
Adding a base/exit case with a passed parameter
Let’s remove the declaration of count and simply pass a parameter into the function.
recurse()
{
if [ $1 -lt 5 ]
then
echo $1
recurse $(($1 + 1))
fi
}
recurse 1
$1 indicates the first parameter passed to the function. Let’s run it and see what we get:
[ahmed@amayem ~]$ ./recurse.sh
1
2
3
4
Looks good.
Recursion and local variables
bash has interesting behaviour with regards to local variables. The man bash pages mention the following about local:
When local is used within a function, it causes the variable name to have a visible scope restricted to that function and its children.
This raises an interesting question, when a function calls itself, are the local variables available to it, and are they overwritten? Let’s experiment:
recurse()
{
echo $x
local x=$1
if [ $1 -lt 5 ]
then
echo $1
recurse $(($1 + 1))
fi
}
recurse 1
When run it gives us the following:
[ahmed@amayem ~]$ ./recurse.sh
1
2
3
4
The output means that the variable is indeed available to the called recursive function. However, does that mean that when we declare a variable local in the called function then it affects the variable in the calling function. Let’s experiment by adding an echo $x after the recurse command to see what x is after the recursion:
recurse()
{
echo $x
local x=$1
if [ $1 -lt 5 ]
then
echo $1
recurse $(($1 + 1))
echo $x
fi
}
recurse 1
It would give us the following:
[ahmed@amayem ~]$ ./recurse.sh
1
2
3
4
4
3
2
1
The output indicates that once a variable is declared local in a function then it hides variables of the same name for it and the functions it calls.
References
man bashpages- tldp page on recursion and local variables
