24.3. Recursion Without Local Variables

   1 #!/bin/bash
   2 # fibo.sh : Fibonacci sequence (recursive)
   3 # Author: M. Cooper
   4 # License: GPL3
   5 
   6 # ----------algorithm--------------
   7 # Fibo(0) = 0
   8 # Fibo(1) = 1
   9 # else
  10 #   Fibo(j) = Fibo(j-1) + Fibo(j-2)
  11 # ---------------------------------
  12 
  13 MAXTERM=15       # Number of terms (+1) to generate.
  14 MINIDX=2         # If idx is less than 2, then Fibo(idx) = idx.
  15 
  16 Fibonacci ()
  17 {
  18   idx=$1   # Doesn't need to be local. Why not?
  19   if [ "$idx" -lt "$MINIDX" ]
  20   then
  21     echo "$idx"  # First two terms are 0 1 ... see above.
  22   else
  23     (( --idx ))  # j-1
  24     term1=$( Fibonacci $idx )   #  Fibo(j-1)
  25 
  26     (( --idx ))  # j-2
  27     term2=$( Fibonacci $idx )   #  Fibo(j-2)
  28 
  29     echo $(( term1 + term2 ))
  30   fi
  31   #  An ugly, ugly kludge.
  32   #  The more elegant implementation of recursive fibo in C
  33   #+ is a straightforward translation of the algorithm in lines 7 - 10.
  34 }
  35 
  36 for i in $(seq 0 $MAXTERM)
  37 do  # Calculate $MAXTERM+1 terms.
  38   FIBO=$(Fibonacci $i)
  39   echo -n "$FIBO "
  40 done
  41 # 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
  42 # Takes a while, doesn't it? Recursion in a script is slow.
  43 
  44 echo
  45 
  46 exit 0

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