| 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 an old mathematical puzzle.
16 # There are three vertical posts set in a base.
17 # The first post has a set of annular rings stacked on it.
18 # These rings are flat disks with a hole drilled out of the center,
19 #+ so they can slip over the posts.
20 # The rings have different diameters, and they stack in descending
21 #+ order, according to size.
22 # The smallest ring is on top, and the largest on the bottom.
23 #
24 # The task is to transfer the stack of rings
25 #+ to one of the other posts.
26 # You can move only one ring at a time to another post.
27 # You are permitted to move rings back to the original post.
28 # You may place a smaller ring atop a larger one,
29 #+ but *not* vice versa.
30 # Again, it is forbidden to place a larger ring atop a smaller one.
31 #
32 # For a small number of rings, only a few moves are required.
33 #+ For each additional ring,
34 #+ the required number of moves approximately doubles,
35 #+ and the "strategy" becomes increasingly complicated.
36 #
37 # For more information, see http://hanoi.kernelthread.com.
38 #
39 #
40 # ... ... ...
41 # | | | | | |
42 # _|_|_ | | | |
43 # |_____| | | | |
44 # |_______| | | | |
45 # |_________| | | | |
46 # |___________| | | | |
47 # | | | | | |
48 # .--------------------------------------------------------------.
49 # |**************************************************************|
50 # #1 #2 #3
51 #
52 #=================================================================#
53
54
55 E_NOPARAM=66 # No parameter passed to script.
56 E_BADPARAM=67 # Illegal number of disks passed to script.
57 Moves= # Global variable holding number of moves.
58 # Modifications to original script.
59
60 dohanoi() { # Recursive function.
61 case $1 in
62 0)
63 ;;
64 *)
65 dohanoi "$(($1-1))" $2 $4 $3
66 echo move $2 "-->" $3
67 let "Moves += 1" # Modification to original script.
68 dohanoi "$(($1-1))" $4 $3 $2
69 ;;
70 esac
71 }
72
73 case $# in
74 1)
75 case $(($1>0)) in # Must have at least one disk.
76 1)
77 dohanoi $1 1 3 2
78 echo "Total moves = $Moves"
79 exit 0;
80 ;;
81 *)
82 echo "$0: illegal value for number of disks";
83 exit $E_BADPARAM;
84 ;;
85 esac
86 ;;
87 *)
88 echo "usage: $0 N"
89 echo " Where \"N\" is the number of disks."
90 exit $E_NOPARAM;
91 ;;
92 esac
93
94 # Exercises:
95 # ---------
96 # 1) Would commands beyond this point ever be executed?
97 # Why not? (Easy)
98 # 2) Explain the workings of the workings of the "dohanoi" function.
99 # (Difficult) |