📄 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 + -