?? c43.htm
字號:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<title> 遞歸 </title>
<script language="javascript">
var prePage="http://www.nec.sjtu.edu.cn/support/Course/C/c/c4/c/c4/c42.htm";
var nextPage="c/c4/c44.htm";
</script>
<link rel="stylesheet" href="../cstyle.css" type="text/css">
<bgsound src="../voice/c43.au" loop="1">
</head>
<body background="../img/mainback.jpg" bgproperties="fixed">
<font SIZE="3">
<h2 align="center"></font><font face="楷體_GB2312"><a name="_top"></a>4.3 遞歸</font></h2>
<div align="center"><center>
<table border="0" width="100%" cellspacing="0" cellpadding="0">
<tr>
<td width="33%" align="center"><a href="c43.htm#c431.html#c431">引言</a></td>
<td width="33%" align="center"><a href="c43.htm#c432.html#c432"><font FACE="宋體" SIZE="3">遞歸和迭代</font></a></td>
<td width="34%" align="center"><a href="c43.htm#c433.html#c433"><font FACE="宋體" SIZE="3">實例</font></a></td>
</tr>
</table>
</center></div>
<hr>
<h3><a name="c431"></a>1.引言</h3>
<blockquote>
<font FACE="宋體" SIZE="3"><p ALIGN="JUSTIFY"></font><font face="宋體">C
語言中的函數可以直接或間接地調用其本身,
這和其它語言不同。它為程序員帶來了極大的靈活性。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">最顯然的情況是直接遞歸，即在函數中直接顯式地調用它本身。我們來看一個簡單的關于遞歸的例子:</font></p>
<p ALIGN="JUSTIFY"><font face="宋體"><font color="#000080">f(int n)<br>
{<br>
...<br>
</font><font color="#FF0000">f(n/2);</font><font color="#000080"><br>
...<br>
}</font></font></p>
<p ALIGN="JUSTIFY"><font face="宋體">另外的情形是,
一個函數調用另一個函數,
它又返過來調用第一個函數。這種情形稱為間接遞歸。例如:</font></p>
<table border="0" width="84%">
<tr>
<td width="50%"><font face="宋體"><font color="#000080">a(int n) <br>
{ <br>
... <br>
</font><font color="#FF0000">b(n/3);</font><font
color="#000080"><br>
... <br>
}</font></font></td>
<td width="50%"><font face="宋體"><font color="#000080">b(int n)<br>
{<br>
... <br>
</font><font color="#FF0000">a(n/2);</font><font
color="#000080"><br>
...<br>
}</font></font></td>
</tr>
</table>
<p ALIGN="JUSTIFY"><font face="宋體">對于不熟悉遞歸的用戶,
它看起來似乎是錯誤定義的和危險的循環。有人認為這種程序可能在永不終止的函數調用序列中循環。當然,
這是可能的, 但這只是在函數定義不正確時才會發生。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">對程序而言,
遞歸函數的目的是執行一系列調用, 一直到達某一點, 序列終止。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">為了保證遞歸函數是正常執行的,
你應該遵守下面的規則: </font></p>
<p ALIGN="JUSTIFY"><font face="宋體"> 1.
每次當一個遞歸函數被調用時,
程序首先應該檢查其些基本的條件是否滿足了,
例如某個參數的值等于零, 如果是這種情形, 函數應停止遞歸。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體"> 2.
每次當函數被遞歸調用時, 傳遞給函數一個或多個參數,
應該以某種方式變得"更簡單"。即,
這些參數應該逐漸靠近上述基本條件。例如,
一個正整數在每次遞歸調用時會逐漸變小, 以至最終其值能到達零。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">下面, 我們將用一個廣為人知的例子----階乘函數來說明這些規則。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">階乘函數是按照遞推關系式來定義的: <br>
f(0) = 1<br>
f(n) = n * f(n-1) (n>0)</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">這個定義很快說明了如何用 C
語言來編寫一個能滿足這兩個條件的階乘函數。</font></p>
<p ALIGN="JUSTIFY"><font color="#000080" face="宋體">int f(int n)<br>
{<br>
if (n==0)<br>
return(1);<br>
else<br>
return(n * f(n-1));<br>
}</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">注意這個程序是如何遵循上面兩條規則的。</font></p>
<p ALIGN="JUSTIFY"><font face="宋體">如果基本條件, 即參數等于零滿足的話,
遞歸就終止了。<br>
如果這個條件不滿足,
函數每次遞歸傳送一個比上一次更小的參數給被調用函數。最終參數值將為零,
正好滿足終止條件。</font></p>
<p><font face="宋體">讓我們看一下 n=3 時階乘函數執行的情況。</font><font
FACE="宋體" SIZE="3"></p>
<p align="center"><!-- Aftershock c431.swf 3=400 4=300 19 40 -->
<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000"
codebase="http://active.macromedia.com/flash2/cabs/swflash.cab#version=3,0,0,0" ID="c431"
WIDTH="400" HEIGHT="300">
<param name="movie" value="../movie/c431.swf">
<param name="quality" value="autohigh">
<param name="menu" value="false">
<param name="bgcolor" value="#E6E6E6"><embed SRC="../movie/c431.swf" swLiveConnect="FALSE" WIDTH="400" HEIGHT="300"
QUALITY="autohigh" MENU="false" BGCOLOR="#E6E6E6" TYPE="application/x-shockwave-flash"
PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash">
</object>
<!-- EndAftershock c431.swf --> </p>
<p align="right"><a href="c43.htm#_top.html#_top">返回頁首</a></p>
</blockquote>
<hr>
<h3><a name="c432"></a><font FACE="宋體" SIZE="3">2.遞歸和迭代</font></h3>
<blockquote>
<p ALIGN="JUSTIFY">盡管階乘函數是說明遞歸過程的一個很好的例子,
但實際上用非遞歸的過程迭代來解決會更好些。迭代只是一個代碼塊的重復執行,
而執行的次數則由塊中的局部變量來控制。</p>
<p ALIGN="JUSTIFY">C語言提供了 for, while, 和 do
這些構造來實現迭代循環的結構。當然, 帶標號的 goto 語句也可以用,
但實際上通常不怎么用它, 因為它是非結構化的,
而且它會使控制流變得難以理解。</p>
<p ALIGN="JUSTIFY">為了把一個遞歸方法轉換為一個迭代方法,
通常要求引入一個或多個的局部變量,
用來計數或者控制這個過程。請再來看一看階乘函數的例子:</p>
<table border="5" width="85%" bgcolor="#CCFFFF" bordercolor="#FF9933" cellspacing="0"
cellpadding="0">
<tr>
<th width="50%">遞歸方法</th>
<th width="50%">迭代方法</th>
</tr>
<tr>
<td width="50%">f(n) = n * f(n-1) <br>
f(0) = 1</td>
<td width="50%">f(n) = n * (n-1) * ... * 1<br>
f(0) = 1</td>
</tr>
</table>
<p ALIGN="JUSTIFY">遞歸方法:<br>
int f(int n)<br>
{<br>
if (n==0)<br>
return(1);<br>
else<br>
return(n*f(n-1));<br>
}</p>
<p ALIGN="JUSTIFY">迭代方法:<br>
int f_it(int n)<br>
{<br>
int count, result; <font
color="#FF0000"><strong><em><---引進兩個局部變量 count 和 result</em></strong></font><br>
for (count=result=1; count<=n; ++count)
<font color="#FF0000"><strong><em><---迭代循環</em></strong></font><br>
result *= count;<br>
return(result);
<font color="#FF0000"><strong><em><---返回到調用程序</em></strong></font><font
FACE="宋體" SIZE="3"><br>
}</p>
<p ALIGN="JUSTIFY">迭代方法比遞歸方法快,
因為迭代避免了一系列函數調用和返回中所涉及到的參數傳遞和返回值的額外開銷。</p>
<p ALIGN="JUSTIFY">遞歸和迭代之間的選擇。一般情況下,
當迭代方法比較容易找到時,
你應該避免使用遞歸。這在問題可以按照一個遞推關系式來描述時,
是時常遇到的, 比如階乘問題就是這種情況。 反過來,
當很難建立一個迭代方法時, 遞歸就是很好的方法。實際上,
在某些情形下, 遞歸方法總是顯而易見的,
而迭代方法卻相當難找到。當某些問題的底層數據結構本身就是遞歸時,
則遞歸也就是最好的方法了。</p>
<p ALIGN="right"></font><a href="c43.htm#_top.html#_top">返回頁首</a></p>
</blockquote>
<hr>
<h3><a name="c433"></a>3.<font FACE="宋體" SIZE="3">實例</font></h3>
<blockquote>
<font FACE="宋體" SIZE="3"><p ALIGN="center"></font></font><font FACE="宋體"
color="#0000FF" size="5">漢諾塔</font><font FACE="宋體" SIZE="3"></p>
<p ALIGN="JUSTIFY">這是個著名難題, 雖然說起來簡單, 如果不用遞歸,
就很難解決。</p>
<p ALIGN="JUSTIFY">題目介紹: 有三個塔, 每個都堆放 n 個盤子。開始時,
所有盤子均在塔A上,并且,盤從上到下,
按直徑增大的次序放置。此難題的目的是設計一個盤子移動的序列。使得塔
A 上的所有盤子借助于塔 B 移動到塔 C 上。<br>
有兩個限制: 1. 一次只能搬動一個盤子。2.
任何時候不能把盤子放在比它小的盤子的上面。</p>
<p ALIGN="JUSTIFY">對于缺乏遞歸思維能力的人來說,
這個問題會令人迷惑不解。另一方面, 遞歸方法卻是那樣簡單,
簡直象有魔力一樣。</p>
<p ALIGN="JUSTIFY">解題方法如下進行. 若你只有一個盤子, 則是直接從 A
移到 C。若你有一個以上的盤子(設為 n 個), 則考慮三個步驟。</p>
<p ALIGN="JUSTIFY">第一步, 把 n-1 個盤子從塔 A 搬到塔 B。第一步不違反說明的第一條限制(一次只能搬動一個盤子);
所有 n-1 個盤子不能作為一個整體一起搬動,
而是符合要求地從一個塔移到另一個塔上。注意盡管最終目標是把盤子從
A 搬到 C, 但是你可以用相同的算法把盤子從一個塔移到另一個塔上,
只要把源塔和目塔的名字改變一下即可。</p>
<p ALIGN="JUSTIFY">第二步: 將剩下的一只盤 (也就是最大的一只) 直接從 A
塔搬到那個仍然空著的塔 C 。</p>
<p ALIGN="JUSTIFY">第三步: 用第一步所說的方法, 再次將 B 塔上的盤搬到
C 塔。和第一步一樣.
這一步實際上是由一序列更小的一次僅搬一個盤的操作組成。這一步是沒有問題的,
因為 C 塔上僅有的一只盤是最大的盤。</p>
<p ALIGN="JUSTIFY">這個算法達到了預期的目標, 即在 C
塔上按正確的順序堆放了所有的盤。</p>
<p ALIGN="JUSTIFY">注意:
前面的討論是按照遞歸算法的標準形式表達的。顯而易見的情形 (一只盤的情況)能夠直接了當地解決。而其它情況,
將用一個"變簡單"的參數(即減少一只盤)去調用函數。最終,
將到達僅有一個盤的情形, 這時, 遞歸就終止了。</p>
<p ALIGN="JUSTIFY">這個例子的 C 語言程序如下。<br>
main()<br>
{<br>
int disks;<br>
void towers(int,char,char,char);<br>
printf("Number of disks: ");<br>
scanf("%d",&disks);<br>
towers(disks,'A','B','C');<br>
}</p>
<p ALIGN="JUSTIFY">void move_disk(char src, char dst)<br>
{<br>
printf("%c ====> %c",src,dst);<br>
}</p>
<p ALIGN="JUSTIFY">void towers(int n, char src, char mid, char dst)<br>
{<br>
void move_disk(char,char);<br>
if (n==1)<br>
{<br>
move_disk(src,dst);<br>
return;<br>
}<br>
towers(n-1,src,dst,mid);<br>
move_disk(src,dst);<br>
towers(n-1,mid,src,dst);<br>
}</p>
<p ALIGN="JUSTIFY">說明:<br>
函數 main() 讀入要搬動的盤的個數, 然后開始第一次調用 tower 函數。<br>
函數 towers() 完成遞歸算法。<br>
函數 move_disk() 打印盤從一個塔到另一個塔的搬動情形。<br>
</p>
<p ALIGN="JUSTIFY">讓我們看一看, 當盤數是 3 時, towers() 的執行情況。</p>
<p align="center"><!-- Aftershock c432.swf 3=600 4=400 19 40 -->
<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000"
codebase="http://active.macromedia.com/flash2/cabs/swflash.cab#version=3,0,0,0" ID="c432"
WIDTH="600" HEIGHT="400">
<param name="movie" value="../movie/c432.swf">
<param name="quality" value="autohigh">
<param name="menu" value="false">
<param name="bgcolor" value="#E6E6E6"><embed SRC="../movie/c432.swf" swLiveConnect="FALSE" WIDTH="600" HEIGHT="400"
QUALITY="autohigh" MENU="false" BGCOLOR="#E6E6E6" TYPE="application/x-shockwave-flash"
PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash">
</object>
<!-- EndAftershock c432.swf --> </p>
<p align="right"><a href="c43.htm#_top.html#_top">返回頁首</a></p>
</blockquote>
</font>
<p align="center"><a href="http://www.nec.sjtu.edu.cn/support/Course/C/c/c4/c44.htm"><img src="../img/next.gif" width="145" height="30"
alt="next.gif (3633 bytes)" border="0"></a></p>
</body>
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -