359 lines
7.1 KiB
HTML
359 lines
7.1 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
|
|
<HTML
|
|
><HEAD
|
|
><TITLE
|
|
>Recursion Without Local Variables</TITLE
|
|
><META
|
|
NAME="GENERATOR"
|
|
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
|
|
REL="HOME"
|
|
TITLE="Advanced Bash-Scripting Guide"
|
|
HREF="index.html"><LINK
|
|
REL="UP"
|
|
TITLE="Functions"
|
|
HREF="functions.html"><LINK
|
|
REL="PREVIOUS"
|
|
TITLE="Local Variables"
|
|
HREF="localvar.html"><LINK
|
|
REL="NEXT"
|
|
TITLE="Aliases"
|
|
HREF="aliases.html"></HEAD
|
|
><BODY
|
|
CLASS="SECT1"
|
|
BGCOLOR="#FFFFFF"
|
|
TEXT="#000000"
|
|
LINK="#0000FF"
|
|
VLINK="#840084"
|
|
ALINK="#0000FF"
|
|
><DIV
|
|
CLASS="NAVHEADER"
|
|
><TABLE
|
|
SUMMARY="Header navigation table"
|
|
WIDTH="100%"
|
|
BORDER="0"
|
|
CELLPADDING="0"
|
|
CELLSPACING="0"
|
|
><TR
|
|
><TH
|
|
COLSPAN="3"
|
|
ALIGN="center"
|
|
>Advanced Bash-Scripting Guide: </TH
|
|
></TR
|
|
><TR
|
|
><TD
|
|
WIDTH="10%"
|
|
ALIGN="left"
|
|
VALIGN="bottom"
|
|
><A
|
|
HREF="localvar.html"
|
|
ACCESSKEY="P"
|
|
>Prev</A
|
|
></TD
|
|
><TD
|
|
WIDTH="80%"
|
|
ALIGN="center"
|
|
VALIGN="bottom"
|
|
>Chapter 24. Functions</TD
|
|
><TD
|
|
WIDTH="10%"
|
|
ALIGN="right"
|
|
VALIGN="bottom"
|
|
><A
|
|
HREF="aliases.html"
|
|
ACCESSKEY="N"
|
|
>Next</A
|
|
></TD
|
|
></TR
|
|
></TABLE
|
|
><HR
|
|
ALIGN="LEFT"
|
|
WIDTH="100%"></DIV
|
|
><DIV
|
|
CLASS="SECT1"
|
|
><H1
|
|
CLASS="SECT1"
|
|
><A
|
|
NAME="RECURNOLOCVAR"
|
|
></A
|
|
>24.3. Recursion Without Local Variables</H1
|
|
><P
|
|
>A function may recursively call itself even without use of
|
|
local variables.</P
|
|
><P
|
|
><A
|
|
NAME="FIBOREF"
|
|
></A
|
|
></P
|
|
><DIV
|
|
CLASS="EXAMPLE"
|
|
><A
|
|
NAME="FIBO"
|
|
></A
|
|
><P
|
|
><B
|
|
>Example 24-16. <I
|
|
CLASS="FIRSTTERM"
|
|
>The Fibonacci Sequence</I
|
|
></B
|
|
></P
|
|
><TABLE
|
|
BORDER="0"
|
|
BGCOLOR="#E0E0E0"
|
|
WIDTH="100%"
|
|
><TR
|
|
><TD
|
|
><FONT
|
|
COLOR="#000000"
|
|
><PRE
|
|
CLASS="PROGRAMLISTING"
|
|
>#!/bin/bash
|
|
# fibo.sh : Fibonacci sequence (recursive)
|
|
# Author: M. Cooper
|
|
# License: GPL3
|
|
|
|
# ----------algorithm--------------
|
|
# Fibo(0) = 0
|
|
# Fibo(1) = 1
|
|
# else
|
|
# Fibo(j) = Fibo(j-1) + Fibo(j-2)
|
|
# ---------------------------------
|
|
|
|
MAXTERM=15 # Number of terms (+1) to generate.
|
|
MINIDX=2 # If idx is less than 2, then Fibo(idx) = idx.
|
|
|
|
Fibonacci ()
|
|
{
|
|
idx=$1 # Doesn't need to be local. Why not?
|
|
if [ "$idx" -lt "$MINIDX" ]
|
|
then
|
|
echo "$idx" # First two terms are 0 1 ... see above.
|
|
else
|
|
(( --idx )) # j-1
|
|
term1=$( Fibonacci $idx ) # Fibo(j-1)
|
|
|
|
(( --idx )) # j-2
|
|
term2=$( Fibonacci $idx ) # Fibo(j-2)
|
|
|
|
echo $(( term1 + term2 ))
|
|
fi
|
|
# An ugly, ugly kludge.
|
|
# The more elegant implementation of recursive fibo in C
|
|
#+ is a straightforward translation of the algorithm in lines 7 - 10.
|
|
}
|
|
|
|
for i in $(seq 0 $MAXTERM)
|
|
do # Calculate $MAXTERM+1 terms.
|
|
FIBO=$(Fibonacci $i)
|
|
echo -n "$FIBO "
|
|
done
|
|
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
|
|
# Takes a while, doesn't it? Recursion in a script is slow.
|
|
|
|
echo
|
|
|
|
exit 0</PRE
|
|
></FONT
|
|
></TD
|
|
></TR
|
|
></TABLE
|
|
></DIV
|
|
><P
|
|
><A
|
|
NAME="HANOIREF"
|
|
></A
|
|
></P
|
|
><DIV
|
|
CLASS="EXAMPLE"
|
|
><A
|
|
NAME="HANOI"
|
|
></A
|
|
><P
|
|
><B
|
|
>Example 24-17. <I
|
|
CLASS="FIRSTTERM"
|
|
>The Towers of Hanoi</I
|
|
></B
|
|
></P
|
|
><TABLE
|
|
BORDER="0"
|
|
BGCOLOR="#E0E0E0"
|
|
WIDTH="100%"
|
|
><TR
|
|
><TD
|
|
><FONT
|
|
COLOR="#000000"
|
|
><PRE
|
|
CLASS="PROGRAMLISTING"
|
|
>#! /bin/bash
|
|
#
|
|
# The Towers Of Hanoi
|
|
# Bash script
|
|
# Copyright (C) 2000 Amit Singh. All Rights Reserved.
|
|
# http://hanoi.kernelthread.com
|
|
#
|
|
# Tested under Bash version 2.05b.0(13)-release.
|
|
# Also works under Bash version 3.x.
|
|
#
|
|
# Used in "Advanced Bash Scripting Guide"
|
|
#+ with permission of script author.
|
|
# Slightly modified and commented by ABS author.
|
|
|
|
#=================================================================#
|
|
# The Tower of Hanoi is a mathematical puzzle attributed to
|
|
#+ Edouard Lucas, a nineteenth-century French mathematician.
|
|
#
|
|
# There are three vertical posts set in a base.
|
|
# The first post has a set of annular rings stacked on it.
|
|
# These rings are disks with a hole drilled out of the center,
|
|
#+ so they can slip over the posts and rest flat.
|
|
# The rings have different diameters, and they stack in ascending
|
|
#+ order, according to size.
|
|
# The smallest ring is on top, and the largest on the bottom.
|
|
#
|
|
# The task is to transfer the stack of rings
|
|
#+ to one of the other posts.
|
|
# You can move only one ring at a time to another post.
|
|
# You are permitted to move rings back to the original post.
|
|
# You may place a smaller ring atop a larger one,
|
|
#+ but *not* vice versa.
|
|
# Again, it is forbidden to place a larger ring atop a smaller one.
|
|
#
|
|
# For a small number of rings, only a few moves are required.
|
|
#+ For each additional ring,
|
|
#+ the required number of moves approximately doubles,
|
|
#+ and the "strategy" becomes increasingly complicated.
|
|
#
|
|
# For more information, see http://hanoi.kernelthread.com
|
|
#+ or pp. 186-92 of _The Armchair Universe_ by A.K. Dewdney.
|
|
#
|
|
#
|
|
# ... ... ...
|
|
# | | | | | |
|
|
# _|_|_ | | | |
|
|
# |_____| | | | |
|
|
# |_______| | | | |
|
|
# |_________| | | | |
|
|
# |___________| | | | |
|
|
# | | | | | |
|
|
# .--------------------------------------------------------------.
|
|
# |**************************************************************|
|
|
# #1 #2 #3
|
|
#
|
|
#=================================================================#
|
|
|
|
|
|
E_NOPARAM=66 # No parameter passed to script.
|
|
E_BADPARAM=67 # Illegal number of disks passed to script.
|
|
Moves= # Global variable holding number of moves.
|
|
# Modification to original script.
|
|
|
|
dohanoi() { # Recursive function.
|
|
case $1 in
|
|
0)
|
|
;;
|
|
*)
|
|
dohanoi "$(($1-1))" $2 $4 $3
|
|
echo move $2 "-->" $3
|
|
((Moves++)) # Modification to original script.
|
|
dohanoi "$(($1-1))" $4 $3 $2
|
|
;;
|
|
esac
|
|
}
|
|
|
|
case $# in
|
|
1) case $(($1>0)) in # Must have at least one disk.
|
|
1) # Nested case statement.
|
|
dohanoi $1 1 3 2
|
|
echo "Total moves = $Moves" # 2^n - 1, where n = # of disks.
|
|
exit 0;
|
|
;;
|
|
*)
|
|
echo "$0: illegal value for number of disks";
|
|
exit $E_BADPARAM;
|
|
;;
|
|
esac
|
|
;;
|
|
*)
|
|
echo "usage: $0 N"
|
|
echo " Where \"N\" is the number of disks."
|
|
exit $E_NOPARAM;
|
|
;;
|
|
esac
|
|
|
|
# Exercises:
|
|
# ---------
|
|
# 1) Would commands beyond this point ever be executed?
|
|
# Why not? (Easy)
|
|
# 2) Explain the workings of the workings of the "dohanoi" function.
|
|
# (Difficult -- see the Dewdney reference, above.)</PRE
|
|
></FONT
|
|
></TD
|
|
></TR
|
|
></TABLE
|
|
></DIV
|
|
></DIV
|
|
><DIV
|
|
CLASS="NAVFOOTER"
|
|
><HR
|
|
ALIGN="LEFT"
|
|
WIDTH="100%"><TABLE
|
|
SUMMARY="Footer navigation table"
|
|
WIDTH="100%"
|
|
BORDER="0"
|
|
CELLPADDING="0"
|
|
CELLSPACING="0"
|
|
><TR
|
|
><TD
|
|
WIDTH="33%"
|
|
ALIGN="left"
|
|
VALIGN="top"
|
|
><A
|
|
HREF="localvar.html"
|
|
ACCESSKEY="P"
|
|
>Prev</A
|
|
></TD
|
|
><TD
|
|
WIDTH="34%"
|
|
ALIGN="center"
|
|
VALIGN="top"
|
|
><A
|
|
HREF="index.html"
|
|
ACCESSKEY="H"
|
|
>Home</A
|
|
></TD
|
|
><TD
|
|
WIDTH="33%"
|
|
ALIGN="right"
|
|
VALIGN="top"
|
|
><A
|
|
HREF="aliases.html"
|
|
ACCESSKEY="N"
|
|
>Next</A
|
|
></TD
|
|
></TR
|
|
><TR
|
|
><TD
|
|
WIDTH="33%"
|
|
ALIGN="left"
|
|
VALIGN="top"
|
|
>Local Variables</TD
|
|
><TD
|
|
WIDTH="34%"
|
|
ALIGN="center"
|
|
VALIGN="top"
|
|
><A
|
|
HREF="functions.html"
|
|
ACCESSKEY="U"
|
|
>Up</A
|
|
></TD
|
|
><TD
|
|
WIDTH="33%"
|
|
ALIGN="right"
|
|
VALIGN="top"
|
|
>Aliases</TD
|
|
></TR
|
|
></TABLE
|
|
></DIV
|
|
></BODY
|
|
></HTML
|
|
> |