23.3. Recursion Without Local Variables

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)