Working with Functions: Towers of Hanoi
For this article, I thought it would be beneficial to go back to some basics of shell scripting and look at how functions work. Most script writers probably eschew using functions because it's a bit antithetical to how scripts tend to evolve, as a sequence of commands on the command line that are captured in a file.
As with general programming, however, if you have a block of even a few lines that are invoked multiple times, in multiple locations in a script, turning that into a function makes a lot more sense.
The general syntax is thus:
MyFunction() {
commands to execute
}
Within the main script—or any other functions, or the function itself—a function is invoked by simply referencing its name:
echo "before call to MyFunction"
MyFunction
echo "after call to MyFunction"
Easy enough. Positional parameters are given to the function in a manner exactly analogous to how command flags are handed to the script overall, as $1, $2, $3 and so on.
This means that within a function, I could write:
if [ n "$1" ] ; then
echo "I was given $1 as my first parameter"
fi
Well, that's a bit lazy of me, testing $#
would be a better way to
ascertain if positional parameters were handed to the function, so
let's rewrite that as:
if [ $# gt 0 ] ; then
echo "I was given $# parameters"
fi
The biggest limitation with shell functions is that they can return an integer value only of 0–127, where a typical script actually utilizes the 0 = false or failure, 1 = true or success. Or, a lot of scripters just ignore return values entirely and use a global variable to pass back values, particularly if they're string values, which otherwise are impossible to deal with in a function.
Functions manipulating global variables is a bit sloppy compared to best practices in Ruby, Java or C++, but you've got to work with what you've got, right?
Towers of Hanoi
To make this column more interesting, I'm going to brush off a classic recursion program and see how to make it work as a shell script. The program is called Towers of Hanoi, and you've probably seen a kid's toy for this. It's a set of different sized disks and three pegs, with the goal being to move all the disks from one peg to another while never violating the rule that bigger disks should never be atop smaller ones. If the pegs are labeled 0, 1 and 2, the simplest case of one disk is to simply move it from peg 0 to peg 2. For two, the first (smaller) disk moves from 0 to 1; the second disk moves from 0 to 2, and the first then moves atop it from 1 to 2.
There's an iterative solution that's succinct:
#!/bin/sh
/bin/echo n "Towers of Hanoi. How many disks? "
read disk
for (( x=1; x < (1 << $disk ); x++ )) ; do
i=$((($x & $x  1 ) % 3))
j=$(((($x  $x  1 ) + 1 ) % 3))
echo "Move from tower $i to tower $j"
done
When run, this delightfully short script produces the result I desire, a stepbystep solution to the Towers of Hanoi problem:
Towers of Hanoi. How many disks? 4
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1
Move from tower 0 to tower 2
Move from tower 1 to tower 0
Move from tower 1 to tower 2
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1
Move from tower 2 to tower 0
Move from tower 1 to tower 0
Move from tower 2 to tower 1
Move from tower 0 to tower 2
Move from tower 0 to tower 1
Move from tower 2 to tower 1
It turns out that the solution to n disks is 2**n + 1 steps mathematically. Put succinctly, 20 disks would take a staggering 1,048,577 moves. That's a lot more patience than I would have with a puzzle game; I don't know about you.
Recursion in Shell Script Functions
The point of introducing the Towers of Hanoi puzzle, however, was to demonstrate a neat recursion trick within a shell script, so let's have a look at how that might work too.
The basic algorithm has three steps:

Move the topmost disks from Source to Temp.

Move the next largest disk from Source to Destination.

Move the topmost disks from Temp to Destination.
There are various Web sites with illustrations of how this works, but it just might be easier to present my script so you can see what I'm talking about:
moves=0 # start with no moves
hanoi()
{
if [ $1 gt 0 ] ; then
hanoi "$(($11))" $2 $4 $3
echo move $2 ">" $3
moves=$(( $moves + 1 ))
hanoi "$(($11))" $4 $3 $2
fi
}
/bin/echo n "Towers of Hanoi. How many disks? "
read disks
hanoi $disks 1 2 3
echo "It took $moves moves to solve Towers for $disks disks."
Notice that there are four parameters that you must give to the recursive Towers of Hanoi function and that you have to "prime the pump" with the initial invocation of:
hanoi $disks 1 3 2
The parameters, in order, are the number of disks and the identity of each of the three pegs you'll be using. For four disks and three pegs, the solution:
Towers of Hanoi. How many disks? 4
move 1 > 3
move 1 > 2
move 3 > 2
move 1 > 3
move 2 > 1
move 2 > 3
move 1 > 3
move 1 > 2
move 3 > 2
move 3 > 1
move 2 > 1
move 3 > 2
move 1 > 3
move 1 > 2
move 3 > 2
It took 15 moves to solve Towers of Hanoi for four disks. Look closely at the code, and you'll realize you actually can use mnemonic names for the pegs by changing the initial invocation near the bottom of the script, which makes the output considerably more understandable as a solution, this time for just three disks:
Towers of Hanoi. How many disks? 3
move source > temp
move source > destination
move temp > destination
move source > temp
move destination > source
move destination > temp
move source > temp
It took 7 moves to solve Towers of Hanoi for 3 disks.
Although you might not encounter situations where you need to create recursive functions in a shell script, the more general function creation and usage definitely can make your scripts more efficient and easier to understand. And, as for Towers of Hanoi? Well, do you have a better algorithm? It's a staple of computer science education, so I bet a lot of you have tackled this one in the past.
Credit to Kamaraj Subramanian for his iterative Hanoi script and phoxis for his recursive Hanoi script—they proved to be good starting points for my own creations this month.
Dave Taylor has been hacking shell scripts for over thirty years. Really. He's the author of the popular "Wicked Cool Shell Scripts" and can be found on Twitter as @DaveTaylor and more generally at www.DaveTaylorOnline.com.
Trending Topics
Nativ Disc  Sep 23, 2016 
Android Browser SecurityWhat You Haven't Been Told  Sep 22, 2016 
The Many Paths to a Solution  Sep 21, 2016 
Synopsys' Coverity  Sep 20, 2016 
Naztech's Roadstar 5 Car Charger  Sep 16, 2016 
RPiPowered pitopCEED Makes the Case as a LowCost Modular Learning Desktop  Sep 15, 2016 
 Download "Linux Management with Red Hat Satellite: Measuring Business Impact and ROI"
 Android Browser SecurityWhat You Haven't Been Told
 Nativ Disc
 The Many Paths to a Solution
 Naztech's Roadstar 5 Car Charger
 Synopsys' Coverity
 Securing the Programmer
 RPiPowered pitopCEED Makes the Case as a LowCost Modular Learning Desktop
 NordVPN for Android
 Glass Padding
Geek Guides
With all the industry talk about the benefits of Linux on Power and all the performance advantages offered by its open architecture, you may be considering a move in that direction. If you are thinking about analytics, big data and cloud computing, you would be right to evaluate Power. The idea of using commodity x86 hardware and replacing it every three years is an outdated cost model. It doesn’t consider the total cost of ownership, and it doesn’t consider the advantage of real processing power, highavailability and multithreading like a demon.
This ebook takes a look at some of the practical applications of the Linux on Power platform and ways you might bring all the performance power of this open architecture to bear for your organization. There are no smoke and mirrors here—just hard, cold, empirical evidence provided by independent sources. I also consider some innovative ways Linux on Power will be used in the future.
Get the Guide