计算机系统概论十七章.doc

1、第十七章 递归17.1 绪论我们从描述一个你可能已经熟悉的递归程序开始这一章。假如我们想从一堆已经按字母顺序排列的试卷中查找到某个学生的成绩。我们将随机地从试卷堆的中间检查其姓名。如果这个被随机选中的成绩不是我们想要查找的，我们将用同样的方法查找适当的一半。也就是说，取决于我们要查找的名字比试卷中间点的名字小或大，我们将从前一半或者后一半里重复这样的查找。例如，假如我们要查找 Babe Ruth 的成绩，而在中间点，我们找到的是 Mickey Mantle 的成绩。我们将再次从初始堆中的后一半里重新查找。如果它存在于试卷堆中的话，很快地，我们将定位出 Babe Ruth 的成绩。这种查找一组已

2、被排过序的元素的方法是递归的。我们在越来越小的试卷堆中一直应用这一相同的查找算法。隐藏在递归之后的思想是简单的：一个递归的函数通过在一个更小的子任务中调用它本身来解决某个任务。正如我们即将看到的，递归是另一种表达重复程序结构的方法。递归的强大功能存在于它能够极好地捕获某些任务的控制流程。对于某些编程问题，递归的解决方法比使用相应的传统重复方法简单得多。在这一章，我们将通过五个不同的例子向你介绍递归的概念。我们检查递归函数是怎样在 LC-3 里实现的。运行时栈机制的好处就在于递归函数不需要特别的处理它们以与其他任何函数相同的方式执行。本章的主要目的是为你提供递归的初步但深入的研究，这样你就可以分

3、析和推理递归程序了。能够理解递归代码对于写递归代码是必要的因素，而且最终将使递归变成你解决编程问题的工具集中的一部分。17.2 什么是递归？调用它本身的函数就是递归函数，就像图 17.1 中的那个 RunningSum 函数那样。这个函数计算从 1 到输入的参数 n 之间的和。例如，RunningSum(4)计算 4+3+2+1。然而，它是递归计算的。注意 4 的连续和实际上是 4 加上 3 的连续和。同样 3 的连续和是 3加上 2 的连续和。这个递归定义是递归算法的基础。换句话说，RunningSum(n)=n+RunningSum(n-1)在数学上，我们用递归方程来表达这样的函数。前面那

4、个方程是一个 RunningSum 的递归方程。为了完成这个方程的计算，我们还必须提供一个初始条件。所以除了前面那个公式外，我们在彻底完成递归计算之前还必须规定RunningSum(1)=1我们进行如下计算：RunningSum(4)=4+RunningSum(3)=4+3+RunningSum(2)=4+3+2+RunningSum(1)=4+3+2+1RunningSum 的 C 版本以与递归方程相同的方法工作。在函数调用 RunningSum(4)的执行期间，RunningSum 使用变元 3（即，RunningSum(3) ）进行一次对它本身的函数调用。然而，在 RunningSum(

5、3)结束前，它调用 RunningSum(2)。在 RunningSum(2)结束前，它又调用 RunningSum(1)。然而， RunningSum(1)没有进行额外的递归调用，而是把数值 1 返回给 RunningSum(2)，这就让 RunningSum(2)可以结束，返回数值 2+1 给 RunningSum(3)。这又使 RunningSum(3)结束并把数值 3+2+1 传递给了 RunningSum(4)。图 17.2 图示了RunningSum(4)的执行是如何进行的。17.3 递归与重复很明显，我们也可以使用 for 循环写 RunningSum，而且代码可能要比对应的递归

6、更简明。这里我们提供了一个递归的版本是为了用一个易于理解的例子来演示一个递归调用。在编程中使用递归和传统的重复（如 for 和 while 循环）是相同的。所有的递归函数都可以用重复来写。但是对于某些程序设计问题，递归版本要比重复版本更简单、更好。一些特定问题的解决方案很自然地就是以递归的方式表达的，比如以递归方程表达的问题。所以，对于这些问题，递归是必不可少的程序设计技术。知道哪些问题需要递归，哪些问题用重复可以更好的解决是计算机程序设计艺术的一部分；随着经验的积累，你将会更擅长于什么时候该使用什么。递归很有用，但是要我们付出代价。做个实验，我们写一个 RunningSum 的重复版本，然后

7、对于很大的 n 的运行时间，与递归版本对比。为了实现这个对比，你可以使用库函数来获得函数开始和结束时的时间（比如，gettimeofday） 。对于不同的 n 的值，用图画出它们的运行时间，你将会注意到递归版本相对要慢（假设编译器没有优化递归） 。正如我们将在 17.5 节中看到的，递归函数在它上面进行函数的调用，而重复则不是这样。17.4 汉诺塔使用递归解决方案更简单的一个问题就是经典的汉诺塔的难题。这个难题包括一个有三个柱子的平台。其中一个柱子上放置了一些木盘，每一个都比它下面的小。目的是把所有的盘子从当前的柱子上移到另一根柱子上。但是，移动木盘有两个规则：一次只能移动一个木盘，并且大木盘

8、永远不能放在小木盘的上面。例如，图 17.3 显示了在柱子 1 上有五个盘子的问题。为了解决这个难题，这五个盘子必须在遵守这两个规则的前提下被移动到另一根柱子上。这个难题来自于一个传说，当世界初创时，印度教寺庙的僧侣们被分配了一个把 64 个盘子从一根柱子移动到另一根柱子的任务。当他们完成这项任务时，世界就终结了。现在我们怎样写一个计算机程序来解决这个问题？如果我们首先从最后来看这个问题，我们可以得出如下的观察：最后的移动顺序必须包括把最大的盘子从柱子 1 移动到目标柱子，比如柱子 3，然后再把其它的盘子移回它的上面。从概念上来说，我们需要把所有的n-1 个盘子从最大的盘子上面移到中间的柱子上

9、，然后把最大的盘子从它的柱子上移到目标柱子。最后，我们把所有的 n-1 个盘子从中间的柱子移动到目标柱子。这样我们就完成了。实际上，我们没这么快完成，因为一次移动 n-1 个盘子是不合法的。但是，我们已经以这种方法说明了这个问题，这样如果我们能够解决了它的两个子问题的话，我们就可以解决它了。一旦最大的盘子到了目标柱子上，我们不需要再处理它了。现在第（n-1）个盘子成了最大的盘子，子目的变成了将它移到目标柱子。因此我们可以将同样的技术应用在一个更小的子问题上。我们现在对这个问题有了一个递归的定义：为了把 n 个盘子移动到目标柱子上，我们将其象征性的表示为 Move(n, target)，我们首先

10、将 n-1 个盘子移动到中间的柱子上Move(n-1, intermediate)然后移动第 n 个盘子到目标上，最后把 n-1 个盘子从中间移动到目标上，或 Move(n-1, target)。所以为了 Move(n, target)，需要两次递归的调用来解决两个包括 n-1 个盘子的子问题。与数学上的递归方程一样，所有的递归定义都需要一个结束递归的基本条件。对于我们说明的问题，这种方法的基本条件包括移动最小的盘子（第 1 个盘子）。既然第 1 个盘子总是位于顶部，不需移动任何其它的盘子，就可以被直接从一根柱子移动到任意其它的柱子上，因此不需要移动其它的盘子。如果没有基本条件，递归函数将是一

11、个无限递归，类似于传统重复中的无限循环。用 C 代码实现我们的递归定义是很简单的。图 17.4 是这个算法的递归的 C 函数。让我们看看当我们玩一个有 3 个盘子的游戏时发生了什么。下面是对 MoveDisk 的一个最初的函数调用。我们开始于想把盘子 3（最大的盘子）从柱子 1 移动到柱子 3，使用柱子 2 作为中间存储的柱子。这就是说，我们想解决一个三个盘子的汉落塔问题。见图17.5。/*盘子：3；当前的柱子：1；目标柱子： 3；中间的柱子：2*/MoveDisk (3, 1, 3, 2)这个调用引起了另一个调用 MoveDisk，把盘子 1 和 2 从盘子 3 移走到柱子 2 上，使用柱子

12、 3 作为中间存储。这个调用被源代码中的 15 行所执行。/*盘子：2；当前的柱子：1；目标柱子： 2；中间的柱子：3*/MoveDisk (2, 1, 2, 3)为了把盘子 2 从柱子 1 移到柱子 2，我们必须先把盘子 1 从盘子 2 移到柱子 3 上（中间的柱子） 。所以这引起了另一个来自于 15 行中的对 MoveDisk 的调用。/*盘子：1；当前的柱子：1；目标柱子： 3；中间的柱子：2*/MoveDisk (1, 1, 3, 2)因为盘子 1 能够被直接移动，第二个 printf 语句被执行。见图 17.6。Move disk number 1 from post 1 to po

13、st 3.（将 1 号盘子从 1 号柱子移到 3 号柱子)现在，MoveDisk 的调用返回到它的调用者，即调用 MoveDisk (2, 1, 2, 3)。回忆我们在等所有在盘子 2 之上的盘子被移到柱子 3 上。既然这个现在已经完成了，我们现在就可以把盘子 2 从柱子 1 移到柱子 2。printf 是下一条被执行的语句，标志着另一个盘子被移走。见图 17.7。Move disk number 2 from post 1 to post 2.（将 2 号盘子从 1 号柱子移到 2 号柱子)下一步，进行一次调用，把在盘子 2 上的所有盘子移回到盘子 2。这发生在源代码的22 行的 MoveD

14、isk 的调用中。/*盘子：1；当前的柱子：3；目标柱子： 1；中间的柱子：1*/MoveDisk (1, 3, 2, 1)再次，既然没有盘子在盘子 1 之上，我们看到移动被打印出来。见图 17.8。Move disk number 1 from post 3 to post 2.（将 1 号盘子从 3 号柱子移到 2 号柱子)现在，控制返回到 MoveDisk(2, 1, 2, 3)的调用，而此次调用已经完成了将盘子 2（和它之上的所有盘子）从柱子 1 移动到柱子 2，返回到它的调用者。而调用者是MoveDisk(3,1,3,2)。现在，在盘子 3 上面的所有盘子都被移到了柱子 2 上。盘子

15、 3 可以从柱子 1 移动到柱子 3 上。printf 语句是下一条执行的语句。见图 17.9。Move disk number 3 from post 1 to post 3.（将 3 号盘子从 1 号柱子移到 3 号柱子)下一个还要完成的子任务是将盘子 2（和它上面的所有盘子）从柱子 2 移动到柱子 3上。我们可以使用柱子 1 作为中间存储。下面的调用发生于源文件的 22 行。/*盘子：2；当前的柱子：2；目标柱子： 3；中间的柱子：1*/MoveDisk (2, 2, 3, 1)要完成这个任务，我们首先必须将盘子 1 从柱子 2 移动到柱子 1 上。这个调用是由源代码中的 15 行的完成

16、的。/*盘子：1；当前的柱子：2；目标柱子： 1；中间的柱子：3*/MoveDisk (1, 2, 1, 3)这个移动不需要子移动。见图 17.10。Move disk number 1 from post 2 to post 1.（将 1 号盘子从 2 号柱子移到 1 号柱子)返回到调用者 MoveDisk(2, 2, 3, 1)，盘子 2 被移动到柱子 3 上。见图 17.11。Move disk number 2 from post 2 to post 3.（将 2 号盘子从 2 号柱子移到 3 号柱子)下面唯一要做的事情是把盘子 2 之上的所有盘子都移回盘子 2 上。/*盘子：1；起始

17、柱子 1；结束柱子 3；中间柱子 2*/MoveDisk (1, 1, 3, 2)这个移动立刻被实现。见图 17.12。Move disk number 1 from post 1 to post 3.（将 1 号盘子从 1 号柱子移到 3 号柱子)这个问题便被圆满解决了！让我们通过检查在解决这 3 个盘子的问题过程中发生的函数调用的顺序，总结递归的行为。考虑一下如何写一个程序的重复版本来解决这个问题，你就会欣赏递归版本的简单性。返回关于汉诺塔的传说：当和尚们完成了解决 64 个盘子的问题时，这个世界也将结束。如果每次移动需要 1 秒钟，和尚们解决这个难题需要花多长时间？17.5 斐波纳契数列

18、下面的递归方程生成了一个非常著名的数列叫斐波纳契数列，它有一些非常有趣的数学、几何学和自然界的特性。f(n)=f(n-1)+f(n-2)f(1)=1f(0)=1换句话说，第n个斐波纳契数是它前面两个数之和。这个数列是1，1，2，3，5，8，13，这个数列是大约公元1200年左右被意大利比萨城的数学家Leonardo首先用公式表示出来。他父亲的名字是Bonacci，因此他经常称自己为Fibonacci，就是filius Bonacci的缩写，即Bonacci的儿子。Fibonacci把这个数列用公式表示出来，作为估算兔子繁殖数量的一种方法，从那以后，我们发现这个数列以吸引人的方式模拟了其它一些自

19、然现象，比如螺旋贝壳的结构或者在一朵花的花瓣的组合。我们可以直接根据这个递归方程明确地写出一个递归函数来计算第n个斐波纳契数。Fibonacci (n)可以通过 Fibonacci(n-1)+Fibonacci(n-2)递归计算出来。递归的基本条件是非常简单的Fibonacci(1) 和Fibonacci(0)都等于1的事实。图17.13 给出了计算第n个斐波纳契数的递归代码。我们将使用这个例子，以计算系统的更低层的视角查看递归是如何工作的。特别的，我们将查看运行时栈的机制以及它是如何处理递归调用的。无论函数何时被调用，不管是被它本身调用还是被其他函数调用，活动记录的一个新的副本被压入运行时栈

20、中。也就是说，每一个函数的调用都会得到参数和局部变量的一份新的、私有副本，每一份副本不同于任何其他副本。为了递归的运行，必须如此，运行时栈使递归能够运行。如果函数的变量被静态的分配于存储单元中，每一次对 Fibonacci 的递归调用都会覆盖前次调用的值。现在让我们看看当以 3 为参数，调用 Fibonacci(3)时发生了什么。我们从运行时栈顶部的 Fibonacci(3)的活动记录开始。图 17.14 显示了当计算最初的函数调用时栈的发展过程。函数调用 Fibonacci(3)会计算 Fibonacci(3-1)，因为表达式 Fibonacci(n-1)+Fibonacci(n-2)的自左

21、向右计算的。因此，Fibonacci(2)首先被调用，它的活动记录被压入运行时栈（见图17.14，步骤 2） 。对于 Fibonacci(2)，参数 n 等于 2，不满足终止条件，因此调用 Fibonacci(1)（见图17.14， 步骤 3） 。这次调用是在计算 Fibonacci(2-1)+Fibonacci(2-2)期间进行的。Fibonacci(1)的调用不再产生递归调用，因为参数 n 满足终止条件。数值 1 返回给Fibonacci(2)，现在通过调用 Fibonacci(0)就可以完成 Fibonacci(1)+Fibonacci(0)的计算（见图17.14 步骤 4） 。调用 F

22、ibonacci(0)时立即返回一个 1。现在，调用Fibonacci(2) 能够完成 ，并且将其子计算（其值为2）返回给它的调用者Fibonacci(3)。已经完成表达式Fibonacci(2)+Fibonacci(1)左手边的部分，Fibonacci(3)调用Fibonacci(1)（如图 17.14，步骤 5） ，它立即返回数值1。现在 Fibonacci(3)已经完成它的结果为3（如图17.14，步骤6） 。.我们可以用代数式说明Fibonacci(3)的递归，如下所示：Fibonacci(3)=Fibonacci(2)+Fibonacci(1)=(Fibonacci(1)+Fibon

23、acci(0)+Fibonacci(1)=1+1+1=3在计算Fibonacci(3) 期间的函数调用的顺序如下：Fibonacci(3)Fibonacci(2)Fibonacci(1)Fibonacci(0)Fibonacci(1)遍历Fibonacci(4) 的执行，你会注意到 Fibonacci(3)的调用顺序是 Fibonacci(4)调用的一个子集。既然Fibonacci(4)=Fibonacci(3)+Fibonacci(2)，那就没什么可惊讶的了。相似的，Fibonacci(4)的 调用顺序是Fibonacci(5)调用的一个子集。在这一章的结尾有一个习题，要求计算在求Fibon

24、acci(n) 的值时进行的函数调用的次数。LC-3编译器为这个程序生成如下代码，列在图17.15中。注意，因为这个函数是递归的，所以不需要特别的处理。由于激活函数的运行时栈的机制，递归函数的处理与每种其他函数都一样。如果你仔细检查代码，你会注意到，为了恰当的翻译Fibonacci的24行，编译器生成了一个临时变量。在编译复杂的表达式时，大多数编译器都会生成那样的临时变量。那样的临时值被存储在活动记录顶部为程序声明的局部变量分配的空间中。17.6 二分法查找在本章的绪言里，我们描述了一种在按照字母表顺序排列的试卷堆中查寻一份指定的试卷的递归技术。这种技术叫做二分法查找，这是一个在一组有序元素中

25、寻找一个特定元素的快速方法。此时，我们已经理解了递归和数组，就可以用 C 语言定义一个递归函数来实现二分法查找。如果我们想要在一组按递增顺序排列的整数数组里查找某个整数值。这个函数应该返回这个整数的下标，如果这个整数不存在，则返回-1。为了实现这个任务，我们将使用如下的二分查找技术：对于一个数组和一个要查找的整数，我们将检查这个数组的中点，判定要查找的整数是否：(1)等于中点的数值，(2)小于中点的数值，(3)大于中点的数值。如果是相等的，我们就完成了。如果是小的，我们再次执行查找，只是这次只对数组的前一半查找。如果是大的，我们只对数组的后一半执行查找。注意，我们可以使用递归调用表示情况(2)

26、和(3)。但是如果我们要查找的数值不在这个数组中将发生什么？已知递归技术在越来越小的原始数组的子数组中执行查找，如果我们要查找的那个记录不存在，那么最后将在没有元素的数组（即，大小为 0）中执行查找。如果我们遇到这种情况，就返回-1。这将是递归的基本条件。图 17.16 是 C 语言的二分查找算法的递归实现。注意为了判断每一步的数组的大小，我们在每一次调用 BinarySearch 时都从子数组的起点遍历到终点。每次调用都重新定义变量 start 和 end 来查找原始数组 list 的越来越小的子数组。图17.17图示了在执行期间这段代码的表现。数组list包含11个元素，如图所示。对Bin

27、arySearch的第一次调用传递了我们要查找的数值（item）以及被查找的数组（回忆16章，这是数组的第一个元素的地址，或者基址）。与数组一起，我们还提供了数组的范围。也就是说，我们提供了要查找的数组部分的起点及终点。在随后的每一个对BinarySearch的递归调用中，这个范围被缩小，最终到达一点，在这一点上，我们要查找的数组的子集只有一个元素或根本没有元素。这两种情况是递归的基本条件。如果不求助于像二分法查找这样的技术，我们可以尝试一个更直接遍历数组的顺序查找。也就是说，我们可以检查list0，然后list1 ，再list2 ，如此继续，最终或者找到那个记录或者确定其不存在。然而，二分法

28、需要更少的比较，而且如果数组足够大的话可能执行得更快。在后面的计算课程中，你将分析二分法查找，推导出其运行时间与log 2n成比例，此处n为数组的大小。而另一方面，顺序查找是与n成正比的。17.7 从整数到 ASCII 码我们最后一个关于递归函数的例子是一个将任意一个整数数值转换为ASCII码字符串的函数。回忆第10章，为了在显示器上显示出一个整数的数值，数值的每一位都必须被单独取出，转换为ASCII码，然后显示于输出设备上。在第10章，我们使用一个简单的重复技术写了一个LC-3程序来实现。我们可以使用如下的递归公式来递归的完成这个任务：如果要显示的数字是一位的，我们就把它转换成ASCII码并

29、显示出来，这样我们就完成了。如果数字是多位的，我们对那个数字除了最低位（最右边的）进行一个递归调用，当递归调用返回时，我们输出最右边的一位。图 17.18 列出了 C 语言的这个递归函数。它读入一个正整数值，把这个值的每一位转化为 ASCII 码，并且将结果字符显示出来。递归函数 IntToAsii 按照如下方式工作：为了打印出一个数字，例如，假设是21,669（即，我们正在调用 IntToAsii（21669） ） ，函数会把这个问题分成两个部分。首先，通过一次对 IntToAsii 的递归调用，2166 必须被显示出来，并且一旦调用结束，9 也将被打印出来。函数通过将参数 num 除以 1

30、0 将其向右移动一位，从而移除它的最低位。对于这个新（也更小）的值，我们进行一次递归调用。如果输入的值 num 只有一位，它将被转化为ASCII 码，并且被显示在屏幕上这种情况不需要递归调用。一旦控制返回到每一次的调用，被移除的数位被转化为 ASCII 码并被显示。为了明确起见，我们列出最初的调用 IntToAsii（12345）中的调用顺序。17.8 总结在这一章，我们介绍了递归的概念。我们可以使用对一个更小的子问题调用它自身的函数来递归地解决一个问题。对于递归，我们假设用 f(n)来表示函数，而对于在 n 的更小的数值上的相同函数，假设用 f(n-1)来表示。比如斐波纳契数列，可以被递归地

31、表示为：Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2);为了使递归能够最终终止，递归调用需要一个基本条件。递归是一种强大的程序设计工具，当应用于正确的问题上时，可以使程序设计任务变得相当容易。例如，汉诺塔问题可以使用递归以简单的方法解决。而用重复来表示就要困难得多。在今后的课程中，你将查看包括指针的组织数据的方式（如树和图） ，而操作这些数据结构的最简单的技术就包括递归函数。从更低的层次看，递归函数的处理方式与其他任意函数调用的方式相同。运行时栈机制允许我们为每个函数调用在存储器中分配一个活动记录，这样就不会与任意其它调用的活动记录相冲突，从而使这点成为可

32、能。习题17.4 对于如下函数，count (20)产生什么结果？17.5 考虑如下 C 程序：a请给出以下各输入的输出：（1）4 9（2）27 5（3）-1 3bPower 函数计算了什么？c上图是调用函数 Power 的栈，显示了两个活动记录，其中一些记录填充了数值。假设此图是 Power 的 return 语句执行之前的状态。请给出图中用问号标记的记录的值。17.6 对于如下 C 函数：a请将此递归函数转化为非递归函数。Sigma ( ) 总是被非负变元所调用。b假设有 1KB 连续的存储单元提供给运行时栈使用，地址和整数都是 16 位的。在程序用尽所有的存储单元之前，可以调用多少次此递

33、归函数？假设不需要存储临时值。17.7 如下 C 程序被编译，并在 LC-3 上执行。当程序执行时，运行时栈起始于存储单元xFEFF，向 xC000 增长（栈占用 16KB 存储空间） 。a对于程序能够正确运行，最大的输入值是多少？b如果运行时栈占用 4KB 存储空间，程序能够正确运行，最大的输入值是多少？17.8 使用重复结构实现计算第 n 个斐波纳契数的函数。并解释为什么递归函数执行得更慢？17.9 改写图 17.16 中的在升序排序的数组中使用二分查找法的函数，实现在降序排列的数组中使用二分查找法。17.10 如下函数采用递归算法，比采用重复结构更容易：a对于如下函数调用，函数的最终返回

34、值分别是多少？（1）ea (12, 15) （2）ea (6, 10) （3）ea (110, 24) b这个函数计算了什么？并将其改写为重复结构实现的函数。17.11 将如下 C 程序中的函数改写为非递归的函数。17.12 对于如下递归函数：a是否存在某个 arg，其值将造成无限递归的出现？ b假设 func 函数是如下 main 函数所在程序中的一部分，当该程序执行时，将调用多少次 func 函数？c此程序的输出是什么？17.13 如下递归函数 Balanced，将一个未知长度的字符串作为参数，判断其中包含的圆括号是否匹配。如果匹配的话，返回 0，否则，返回不匹配的圆括号数目。初始调用为 Balanced (string, 0 ,0)。请在空格处填充代码，实现该函数。17.14 如下 C 程序的输出是什么？