-
Notifications
You must be signed in to change notification settings - Fork 0
/
ch05s03.html
28 lines (28 loc) · 18 KB
/
ch05s03.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>3. 递归</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch05.html" title="第 5 章 深入理解函数" /><link rel="prev" href="ch05s02.html" title="2. 增量式开发" /><link rel="next" href="ch06.html" title="第 6 章 循环语句" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">3. 递归</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch05s02.html">上一页</a> </td><th width="60%" align="center">第 5 章 深入理解函数</th><td width="20%" align="right"> <a accesskey="n" href="ch06.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2722951"></a>3. 递归</h2></div></div></div><p>如果定义一个概念需要用到这个概念本身，我们称它的定义是递归的（Recursive）<a id="id2722964" class="indexterm"></a>。例如：</p><div class="variablelist"><dl><dt><span class="term">frabjuous</span></dt><dd><p>an adjective used to describe something that is frabjuous.</p></dd></dl></div><p>这只是一个玩笑，如果你在字典上看到这么一个词条肯定要怒了。然而数学上确实有很多概念是用它自己来定义的，比如n的阶乘（Factorial）<a id="id2722991" class="indexterm"></a>是这样定义的：n的阶乘等于n乘以n-1的阶乘。如果这样就算定义完了，恐怕跟上面那个词条有异曲同工之妙了：n-1的阶乘是什么？是n-1乘以n-2的阶乘。那n-2的阶乘又是什么？这样下去永远也没完。因此需要定义一个最关键的基础条件（Base Case）<a id="id2723009" class="indexterm"></a>：0的阶乘等于1。</p><div class="literallayout"><p>0! = 1<br />
n! = n · (n-1)!</p></div><p>因此，3!=3*2!，2!=2*1!，1!=1*0!=1*1=1，正因为有了Base Case，才不会永远没完地数下去，知道了1!=1我们再反过来算回去，2!=2*1!=2*1=2，3!=3*2!=3*2=6。下面用程序来完成这一计算过程，我们要写一个计算阶乘的函数<code class="literal">factorial</code>，先把Base Case这种最简单的情况写进去：</p><pre class="programlisting">int factorial(int n)
{
if (n == 0)
return 1;
}</pre><p>如果参数<code class="literal">n</code>不是0应该<code class="literal">return</code>什么呢？根据定义，应该<code class="literal">return n*factorial(n-1);</code>，为了下面的分析方便，我们引入几个临时变量把这个语句拆分一下：</p><pre class="programlisting">int factorial(int n)
{
if (n == 0)
return 1;
else {
int recurse = factorial(n-1);
int result = n * recurse;
return result;
}
}</pre><p><code class="literal">factorial</code>这个函数居然可以自己调用自己？是的。自己直接或间接调用自己的函数称为递归函数。这里的<code class="literal">factorial</code>是直接调用自己，有些时候函数A调用函数B，函数B又调用函数A，也就是函数A间接调用自己，这也是递归函数。如果你觉得迷惑，可以把<code class="literal">factorial(n-1)</code>这一步看成是在调用另一个函数－－另一个有着相同函数名和相同代码的函数，调用它就是跳到它的代码里执行，然后再返回<code class="literal">factorial(n-1)</code>这个调用的下一步继续执行。我们以<code class="literal">factorial(3)</code>为例分析整个调用过程，如下图所示：</p><div class="figure"><a id="id2723116"></a><p class="title"><b>图 5.2. factorial(3)的调用过程</b></p><div class="figure-contents"><div><img src="images/func2.factorial.png" alt="factorial(3)的调用过程" /></div></div></div><br class="figure-break" /><p>图中用实线箭头表示调用，用虚线箭头表示返回，右侧的框表示在调用和返回过程中各层函数调用的存储空间变化情况。</p><div class="orderedlist"><ol type="1"><li><p><code class="literal">main()</code>有一个局部变量<code class="literal">result</code>，用一个框表示。</p></li><li><p>调用<code class="literal">factorial(3)</code>时要分配参数和局部变量的存储空间，于是在<code class="literal">main()</code>的下面又多了一个框表示<code class="literal">factorial(3)</code>的参数和局部变量，其中<code class="literal">n</code>已初始化为3。</p></li><li><p><code class="literal">factorial(3)</code>又调用<code class="literal">factorial(2)</code>，又要分配<code class="literal">factorial(2)</code>的参数和局部变量，于是在<code class="literal">main()</code>和<code class="literal">factorial(3)</code>下面又多了一个框。<a class="xref" href="ch03s04.html#func.localvar">第 4 节 “全局变量、局部变量和作用域”</a>讲过，每次调用函数时分配参数和局部变量的存储空间，退出函数时释放它们的存储空间。<code class="literal">factorial(3)</code>和<code class="literal">factorial(2)</code>是两次不同的调用，<code class="literal">factorial(3)</code>的参数<code class="literal">n</code>和<code class="literal">factorial(2)</code>的参数<code class="literal">n</code>各有各的存储单元，虽然我们写代码时只写了一次参数<code class="literal">n</code>，但运行时却是两个不同的参数<code class="literal">n</code>。并且由于调用<code class="literal">factorial(2)</code>时<code class="literal">factorial(3)</code>还没退出，所以两个函数调用的参数<code class="literal">n</code>同时存在，所以在原来的基础上多画一个框。</p></li><li><p>依此类推，请读者对照着图自己分析整个调用过程。读者会发现这个过程和前面我们用数学公式计算3!的过程是一样的，都是先一步步展开然后再一步步收回去。</p></li></ol></div><p>我们看上图右侧存储空间的变化过程，随着函数调用的层层深入，存储空间的一端逐渐增长，然后随着函数调用的层层返回，存储空间的这一端又逐渐缩短，并且每次访问参数和局部变量时只能访问这一端的存储单元，而不能访问内部的存储单元，比如当<code class="literal">factorial(2)</code>的存储空间位于末端时，只能访问它的参数和局部变量，而不能访问<code class="literal">factorial(3)</code>和<code class="literal">main()</code>的参数和局部变量。具有这种性质的数据结构称为堆栈或栈（Stack）<a id="id2723347" class="indexterm"></a>，随着函数调用和返回而不断变化的这一端称为栈顶，每个函数调用的参数和局部变量的存储空间（上图的每个小方框）称为一个栈帧（Stack Frame）<a id="id2723357" class="indexterm"></a>。操作系统为程序的运行预留了一块栈空间，函数调用时就在这个栈空间里分配栈帧，函数返回时就释放栈帧。</p><p>在写一个递归函数时，你如何证明它是正确的？像上面那样跟踪函数的调用和返回过程算是一种办法，但只是<code class="literal">factorial(3)</code>就已经这么麻烦了，如果是<code class="literal">factorial(100)</code>呢？虽然我们已经证明了<code class="literal">factorial(3)</code>是正确的，因为它跟我们用数学公式计算的过程一样，结果也一样，但这不能代替<code class="literal">factorial(100)</code>的证明，你怎么办？别的函数你可以跟踪它的调用过程去证明它的正确性，因为每个函数只调用一次就返回了，但是对于递归函数，这么跟下去只会跟得你头都大了。事实上并不是每个函数调用都需要钻进去看的。我们在调用<code class="literal">printf</code>时没有钻进去看它是怎么打印的，我们只是<span class="emphasis"><em>相信</em></span>它能打印，能正确完成它的工作，然后就继续写下面的代码了。在上一节中，我们写了<code class="literal">distance</code>和<code class="literal">area</code>函数，然后立刻测试证明了这两个函数是正确的，然后我们写<code class="literal">area_point</code>时调用了这两个函数：</p><pre class="programlisting">return area(distance(x1, y1, x2, y2));</pre><p>在写这一句的时候，我们需要钻进<code class="literal">distance</code>和<code class="literal">area</code>函数中去走一趟才知道我们调用得是否正确吗？不需要，因为我们已经<span class="emphasis"><em>相信</em></span>这两个函数能正确工作了，也就是相信把座标传给<code class="literal">distance</code>它就能返回正确的距离，把半径传给<code class="literal">area</code>它就能返回正确的面积，因此调用它们去完成另外一件工作也应该是正确的。这种“<span class="quote">相信</span>”称为Leap of Faith<a id="id2723481" class="indexterm"></a>，首先相信一些结论，然后再用它们去证明另外一些结论。</p><p>在写<code class="literal">factorial(n)</code>的代码时写到这个地方：</p><pre class="programlisting">...
int recurse = factorial(n-1);
int result = n * recurse;
...</pre><p>这时，如果我们相信<code class="literal">factorial(n-1)</code>是正确的，也就是相信传给它<code class="literal">n-1</code>它就能返回(n-1)!，那么<code class="literal">recurse</code>就是(n-1)!，那么<code class="literal">result</code>就是n*(n-1)!，也就是n!，这正是我们要返回的<code class="literal">factorial(n)</code>的结果。当然这有点奇怪：我们还没写完<code class="literal">factorial</code>这个函数，凭什么要相信<code class="literal">factorial(n-1)</code>是正确的？可Leap of Faith本身就是Leap（跳跃）的，不是吗？<span class="emphasis"><em>如果你相信你正在写的递归函数是正确的，并调用它，然后在此基础上写完这个递归函数，那么它就会是正确的，从而值得你相信它正确。</em></span></p><p>这么说好像有点儿玄，我们从数学上严格证明一下<code class="literal">factorial</code>函数的正确性。刚才说了，<code class="literal">factorial(n)</code>的正确性依赖于<code class="literal">factorial(n-1)</code>的正确性，只要后者正确，在后者的结果上乘个<code class="literal">n</code>返回这一步显然也没有疑问，那么我们的函数实现就是正确的。因此要证明<code class="literal">factorial(n)</code>的正确性就是要证明<code class="literal">factorial(n-1)</code>的正确性，同理，要证明<code class="literal">factorial(n-1)</code>的正确性就是要证明<code class="literal">factorial(n-2)</code>的正确性，依此类推下去，最后是：要证明<code class="literal">factorial(1)</code>的正确性就是要证明<code class="literal">factorial(0)</code>的正确性。而<code class="literal">factorial(0)</code>的正确性不依赖于别的函数调用，它就是程序中的一个小的分支<code class="literal">return 1;</code>，这个1是我们根据阶乘的定义写的，肯定是正确的，因此<code class="literal">factorial(1)</code>的实现是正确的，因此<code class="literal">factorial(2)</code>也正确，依此类推，最后<code class="literal">factorial(n)</code>也是正确的。其实这就是在中学时学的数学归纳法（Mathematical Induction）<a id="id2723665" class="indexterm"></a>，用数学归纳法来证明只需要证明两点：Base Case正确，递推关系正确。<span class="emphasis"><em>写递归函数时一定要记得写Base Case</em></span>，否则即使递推关系正确，整个函数也不正确。如果<code class="literal">factorial</code>函数漏掉了Base Case：</p><pre class="programlisting">int factorial(int n)
{
int recurse = factorial(n-1);
int result = n * recurse;
return result;
}</pre><p>那么这个函数就会永远调用下去，直到操作系统为程序预留的栈空间耗尽程序崩溃（段错误）为止，这称为无穷递归（Infinite recursion）<a id="id2723697" class="indexterm"></a>。</p><p>到目前为止我们只学习了全部C语法的一个小的子集，但是现在应该告诉你：这个子集是完备的，它本身就可以作为一门编程语言了，以后还要学习很多C语言特性，但全部都可以用已经学过的这些特性来代替。也就是说，以后要学的C语言特性会使代码写起来更加方便，但不是必不可少的，现在学的这些已经完全覆盖了<a class="xref" href="intro.program.html" title="1. 程序和编程语言">第 1 节 “程序和编程语言”</a>讲的五种基本指令了。有的读者会说循环还没讲到呢，是的，循环在下一章才讲，但有一个重要的结论就是<span class="emphasis"><em>递归和循环是等价的</em></span>，用循环能做的事用递归都能做，反之亦然，事实上有的编程语言（比如某些LISP实现）只有递归而没有循环。计算机指令能做的所有事情就是数据存取、运算、测试和分支、循环（或递归），在计算机上运行高级语言写的程序最终也要翻译成指令，指令做不到的事情高级语言写的程序肯定也做不到，虽然高级语言有丰富的语法特性，但也只是比指令写起来更方便而已，能做的事情是一样多的。那么，为什么计算机要设计成这样？在设计时怎么想到计算机应该具备这几样功能，而不是更多或更少的功能？这些要归功于早期的计算机科学家，例如Alan Turing，他们在计算机还没有诞生的年代就从数学理论上为计算机的设计指明了方向。有兴趣的读者可以参考有关计算理论的教材，例如<a class="xref" href="bi01.html#bibli.iatlc" title="Introduction to Automata Theory, Languages, and Computation">[<abbr class="abbrev">IATLC</abbr>]</a>。</p><p>递归绝不只是为解决一些奇技淫巧的数学题<sup>[<a id="id2723765" href="#ftn.id2723765" class="footnote">8</a>]</sup>而想出来的招，它是计算机的精髓所在，也是编程语言的精髓所在。我们学习在C的语法时已经看到很多递归定义了，例如在<a class="xref" href="ch03s01.html#func.mathfunc">第 1 节 “数学函数”</a>讲过的语法规则中，“<span class="quote">表达式</span>”就是递归定义的：</p><div class="literallayout"><p><span class="emphasis"><em>表达式</em></span> → <span class="emphasis"><em>表达式</em></span>(参数列表)<br />
参数列表 → <span class="emphasis"><em>表达式</em></span>, <span class="emphasis"><em>表达式</em></span>, ...</p></div><p>再比如在<a class="xref" href="ch04s01.html#cond.if">第 1 节 “if语句”</a>讲过的语规则中，“<span class="quote">语句</span>”也是递归定义的：</p><div class="literallayout"><p><span class="emphasis"><em>语句</em></span> → if (控制表达式) <span class="emphasis"><em>语句</em></span></p></div><p>可见编译器在解析我们写的程序时一定也用了大量的递归，有关编译器的实现原理可参考<a class="xref" href="bi01.html#bibli.dragonbook" title="Compilers: Principles, Techniques, & Tools">[<abbr class="abbrev">Dragon Book</abbr>]</a>。</p><div class="simplesect" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h3 class="title"><a id="id2723842"></a>习题</h3></div></div></div><p>1、编写递归函数求两个正整数<code class="literal">a</code>和<code class="literal">b</code>的最大公约数（GCD，Greatest Common Divisor）<a id="id2723863" class="indexterm"></a>，使用Euclid算法：</p><div class="orderedlist"><ol type="1"><li><p>如果<code class="literal">a</code>除以<code class="literal">b</code>能整除，则最大公约数是<code class="literal">b</code>。</p></li><li><p>否则，最大公约数等于<code class="literal">b</code>和<code class="literal">a%b</code>的最大公约数。</p></li></ol></div><p>Euclid算法是很容易证明的，请读者自己证明一下为什么这么算就能算出最大公约数。最后，修改你的程序使之适用于所有整数，而不仅仅是正整数。</p><p>2、编写递归函数求Fibonacci数列的第<code class="literal">n</code>项，这个数列是这样定义的：</p><div class="literallayout"><p>fib(0)=1<br />
fib(1)=1<br />
fib(n)=fib(n-1)+fib(n-2)</p></div><p>上面两个看似毫不相干的问题之间却有一个有意思的联系：</p><div class="variablelist"><dl><dt><span class="term">Lamé定理</span></dt><dd><p>如果Euclid算法需要k步来计算两个数的GCD，那么这两个数之中较小的一个必然大于等于Fibonacci数列的第k项。</p></dd></dl></div><p>感兴趣的读者可以参考<a class="xref" href="bi01.html#bibli.sicp" title="Structure and Interpretation of Computer Programs">[<abbr class="abbrev">SICP</abbr>]</a>第1.2节的简略证明。</p></div><div class="footnotes"><br /><hr width="100" align="left" /><div class="footnote"><p><sup>[<a id="ftn.id2723765" href="#id2723765" class="para">8</a>] </sup>例如很多编程书都会举例的汉诺塔问题，本书不打算再重复这个题目了。</p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch05s02.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch05.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch06.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">2. 增量式开发 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 第 6 章 循环语句</td></tr></table></div></body></html>