23.3. Recursion Without Local Variables

   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)