📄 recurnolocvar.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><HTML><HEAD><TITLE>Recursion Without Local Variables</TITLE><METANAME="GENERATOR"CONTENT="Modular DocBook HTML Stylesheet Version 1.76b+"><LINKREL="HOME"TITLE="Advanced Bash-Scripting Guide"HREF="index.html"><LINKREL="UP"TITLE="Functions"HREF="functions.html"><LINKREL="PREVIOUS"TITLE="Local Variables"HREF="localvar.html"><LINKREL="NEXT"TITLE="Aliases"HREF="aliases.html"><METAHTTP-EQUIV="Content-Style-Type"CONTENT="text/css"><LINKREL="stylesheet"HREF="common/kde-common.css"TYPE="text/css"><METAHTTP-EQUIV="Content-Type"CONTENT="text/html; charset=iso-8859-1"><METAHTTP-EQUIV="Content-Language"CONTENT="en"><LINKREL="stylesheet"HREF="common/kde-localised.css"TYPE="text/css"TITLE="KDE-English"><LINKREL="stylesheet"HREF="common/kde-default.css"TYPE="text/css"TITLE="KDE-Default"></HEAD><BODYCLASS="SECT1"BGCOLOR="#FFFFFF"TEXT="#000000"LINK="#AA0000"VLINK="#AA0055"ALINK="#AA0000"STYLE="font-family: sans-serif;"><DIVCLASS="NAVHEADER"><TABLESUMMARY="Header navigation table"WIDTH="100%"BORDER="0"CELLPADDING="0"CELLSPACING="0"><TR><THCOLSPAN="3"ALIGN="center">Advanced Bash-Scripting Guide: An in-depth exploration of the art of shell scripting</TH></TR><TR><TDWIDTH="10%"ALIGN="left"VALIGN="bottom"><AHREF="localvar.html"ACCESSKEY="P">Prev</A></TD><TDWIDTH="80%"ALIGN="center"VALIGN="bottom">Chapter 23. Functions</TD><TDWIDTH="10%"ALIGN="right"VALIGN="bottom"><AHREF="aliases.html"ACCESSKEY="N">Next</A></TD></TR></TABLE><HRALIGN="LEFT"WIDTH="100%"></DIV><DIVCLASS="SECT1"><H1CLASS="SECT1"><ANAME="RECURNOLOCVAR"></A>23.3. Recursion Without Local Variables</H1><P>A function may recursively call itself even without use of local variables.</P><P><ANAME="FIBOREF"></A></P><DIVCLASS="EXAMPLE"><HR><ANAME="FIBO"></A><P><B>Example 23-15. <ICLASS="FIRSTTERM">The Fibonacci Sequence</I></B></P><TABLEBORDER="0"BGCOLOR="#E0E0E0"WIDTH="100%"><TR><TD><PRECLASS="PROGRAMLISTING"> 1 #!/bin/bash 2 # fibo.sh : Fibonacci sequence (recursive) 3 # Author: M. Cooper 4 # License: GPL3 5 6 # --------------------------------- 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</PRE></TD></TR></TABLE><HR></DIV><P><ANAME="HANOIREF"></A></P><DIVCLASS="EXAMPLE"><HR><ANAME="HANOI"></A><P><B>Example 23-16. <ICLASS="FIRSTTERM">The Towers of Hanoi</I></B></P><TABLEBORDER="0"BGCOLOR="#E0E0E0"WIDTH="100%"><TR><TD><PRECLASS="PROGRAMLISTING"> 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.)</PRE></TD></TR></TABLE><HR></DIV></DIV><DIVCLASS="NAVFOOTER"><HRALIGN="LEFT"WIDTH="100%"><TABLESUMMARY="Footer navigation table"WIDTH="100%"BORDER="0"CELLPADDING="0"CELLSPACING="0"><TR><TDWIDTH="33%"ALIGN="left"VALIGN="top"><AHREF="localvar.html"ACCESSKEY="P">Prev</A></TD><TDWIDTH="34%"ALIGN="center"VALIGN="top"><AHREF="index.html"ACCESSKEY="H">Home</A></TD><TDWIDTH="33%"ALIGN="right"VALIGN="top"><AHREF="aliases.html"ACCESSKEY="N">Next</A></TD></TR><TR><TDWIDTH="33%"ALIGN="left"VALIGN="top">Local Variables</TD><TDWIDTH="34%"ALIGN="center"VALIGN="top"><AHREF="functions.html"ACCESSKEY="U">Up</A></TD><TDWIDTH="33%"ALIGN="right"VALIGN="top">Aliases</TD></TR></TABLE></DIV></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -