Advanced Bash-Scripting Guide: An in-depth exploration of the art of shell scripting | ||
---|---|---|
Prev | Chapter 23. Functions | Next |
A function may recursively call itself even without use of local variables.
Example 23-14. The Towers of Hanoi
1 #! /bin/bash 2 # 3 # The Towers Of Hanoi 4 # Bash script 5 # Copyright (C) 2000 Amit Singh. All Rights Reserved. 6 # http://hanoi.kernelthread.com 7 # 8 # Last tested under bash version 2.05b.0(13)-release 9 # 10 # Used in "Advanced Bash Scripting Guide" 11 #+ with permission of script author. 12 # Slightly modified and commented by ABS author. 13 14 #=================================================================# 15 # The Tower of Hanoi is a mathematical puzzle attributed to 16 #+ Edouard Lucas, a nineteenth-century French mathematician. 17 # 18 # There are three vertical posts set in a base. 19 # The first post has a set of annular rings stacked on it. 20 # These rings are flat disks with a hole drilled out of the center, 21 #+ so they can slip over the posts. 22 # The rings have different diameters, and they stack in descending 23 #+ order, according to size. 24 # The smallest ring is on top, and the largest on the bottom. 25 # 26 # The task is to transfer the stack of rings 27 #+ to one of the other posts. 28 # You can move only one ring at a time to another post. 29 # You are permitted to move rings back to the original post. 30 # You may place a smaller ring atop a larger one, 31 #+ but *not* vice versa. 32 # Again, it is forbidden to place a larger ring atop a smaller one. 33 # 34 # For a small number of rings, only a few moves are required. 35 #+ For each additional ring, 36 #+ the required number of moves approximately doubles, 37 #+ and the "strategy" becomes increasingly complicated. 38 # 39 # For more information, see http://hanoi.kernelthread.com. 40 # 41 # 42 # ... ... ... 43 # | | | | | | 44 # _|_|_ | | | | 45 # |_____| | | | | 46 # |_______| | | | | 47 # |_________| | | | | 48 # |___________| | | | | 49 # | | | | | | 50 # .--------------------------------------------------------------. 51 # |**************************************************************| 52 # #1 #2 #3 53 # 54 #=================================================================# 55 56 57 E_NOPARAM=66 # No parameter passed to script. 58 E_BADPARAM=67 # Illegal number of disks passed to script. 59 Moves= # Global variable holding number of moves. 60 # Modifications to original script. 61 62 dohanoi() { # Recursive function. 63 case $1 in 64 0) 65 ;; 66 *) 67 dohanoi "$(($1-1))" $2 $4 $3 68 echo move $2 "-->" $3 69 let "Moves += 1" # Modification to original script. 70 dohanoi "$(($1-1))" $4 $3 $2 71 ;; 72 esac 73 } 74 75 case $# in 76 1) 77 case $(($1>0)) in # Must have at least one disk. 78 1) 79 dohanoi $1 1 3 2 80 echo "Total moves = $Moves" 81 exit 0; 82 ;; 83 *) 84 echo "$0: illegal value for number of disks"; 85 exit $E_BADPARAM; 86 ;; 87 esac 88 ;; 89 *) 90 echo "usage: $0 N" 91 echo " Where \"N\" is the number of disks." 92 exit $E_NOPARAM; 93 ;; 94 esac 95 96 # Exercises: 97 # --------- 98 # 1) Would commands beyond this point ever be executed? 99 # Why not? (Easy) 100 # 2) Explain the workings of the workings of the "dohanoi" function. 101 # (Difficult) |