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

第十七章 递归17.1 绪论我们从描述一个你可能已经熟悉的递归程序开始这一章。假如我们想从一堆已经按字母顺序排列的试卷中查找到某个学生的成绩。我们将随机地从试卷堆的中间检查其姓名。如果这个被随机选中的成绩不是我们想要查找的，我们将用同样的方法查找适当的一半。也就是说，取决于我们要查找的名字比试卷中间点的名字小或大，我们将从前一半或者后一半里重复这样的查找。例如，假如我们要查找Babe Ruth的成绩，而在中间点，我们找到的是Mickey Mantle的成绩。我们将再次从初始堆中的后一半里重新查找。如果它存在于试卷堆中的话，很快地，我们将定位出Babe Ruth的成绩。这种查找一组已被排过序的元素的方法是递归的。我们在越来越小的试卷堆中一直应用这一相同的查找算法。隐藏在递归之后的思想是简单的：一个递归的函数通过在一个更小的子任务中调用它本身来解决某个任务。正如我们即将看到的，递归是另一种表达重复程序结构的方法。递归的强大功能存在于它能够极好地捕获某些任务的控制流程。对于某些编程问题，递归的解决方法比使用相应的传统重复方法简单得多。在这一章，我们将通过五个不同的例子向你介绍递归的概念。我们检查递归函数是怎样在LC-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)在数学上，我们用递归方程来表达这样的函数。前面那个方程是一个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(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，而且代码可能要比对应的递归更简明。这里我们提供了一个递归的版本是为了用一个易于理解的例子来演示一个递归调用。在编程中使用递归和传统的重复（如for和while循环）是相同的。所有的递归函数都可以用重复来写。但是对于某些程序设计问题，递归版本要比重复版本更简单、更好。一些特定问题的解决方案很自然地就是以递归的方式表达的，比如以递归方程表达的问题。所以，对于这些问题，递归是必不可少的程序设计技术。知道哪些问题需要递归，哪些问题用重复可以更好的解决是计算机程序设计艺术的一部分；随着经验的积累，你将会更擅长于什么时候该使用什么。递归很有用，但是要我们付出代价。做个实验，我们写一个RunningSum的重复版本，然后对于很大的n的运行时间，与递归版本对比。为了实现这个对比，你可以使用库函数来获得函数开始和结束时的时间（比如，gettimeofday）。对于不同的n的值，用图画出它们的运行时间，你将会注意到递归版本相对要慢（假设编译器没有优化递归）。正如我们将在17.5节中看到的，递归函数在它上面进行函数的调用，而重复则不是这样。17.4 汉诺塔使用递归解决方案更简单的一个问题就是经典的汉诺塔的难题。这个难题包括一个有三个柱子的平台。其中一个柱子上放置了一些木盘，每一个都比它下面的小。目的是把所有的盘子从当前的柱子上移到另一根柱子上。但是，移动木盘有两个规则：一次只能移动一个木盘，并且大木盘永远不能放在小木盘的上面。例如，图17.3显示了在柱子1上有五个盘子的问题。为了解决这个难题，这五个盘子必须在遵守这两个规则的前提下被移动到另一根柱子上。这个难题来自于一个传说，当世界初创时，印度教寺庙的僧侣们被分配了一个把64个盘子从一根柱子移动到另一根柱子的任务。当他们完成这项任务时，世界就终结了。现在我们怎样写一个计算机程序来解决这个问题？如果我们首先从最后来看这个问题，我们可以得出如下的观察：最后的移动顺序必须包括把最大的盘子从柱子1移动到目标柱子，比如柱子3，然后再把其它的盘子移回它的上面。从概念上来说，我们需要把所有的n-1个盘子从最大的盘子上面移到中间的柱子上，然后把最大的盘子从它的柱子上移到目标柱子。最后，我们把所有的n-1个盘子从中间的柱子移动到目标柱子。这样我们就完成了。实际上，我们没这么快完成，因为一次移动n-1个盘子是不合法的。但是，我们已经以这种方法说明了这个问题，这样如果我们能够解决了它的两个子问题的话，我们就可以解决它了。一旦最大的盘子到了目标柱子上，我们不需要再处理它了。现在第（n-1）个盘子成了最大的盘子，子目的变成了将它移到目标柱子。因此我们可以将同样的技术应用在一个更小的子问题上。 我们现在对这个问题有了一个递归的定义：为了把n个盘子移动到目标柱子上，我们将其象征性的表示为Move(n, target)，我们首先将n-1个盘子移动到中间的柱子上Move(n-1, intermediate)然后移动第n个盘子到目标上，最后把n-1个盘子从中间移动到目标上，或Move(n-1, target)。所以为了Move(n, target)，需要两次递归的调用来解决两个包括n-1个盘子的子问题。 与数学上的递归方程一样，所有的递归定义都需要一个结束递归的基本条件。对于我们说明的问题，这种方法的基本条件包括移动最小的盘子（第1个盘子）。既然第1个盘子总是位于顶部，不需移动任何其它的盘子，就可以被直接从一根柱子移动到任意其它的柱子上，因此不需要移动其它的盘子。如果没有基本条件，递归函数将是一个无限递归，类似于传统重复中的无限循环。 用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上，使用柱子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 post 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行的MoveDisk的调用中。/*盘子：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上。盘子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行的完成的。/*盘子：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；起始柱子 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 斐波纳契数列下面的递归方程生成了一个非常著名的数列叫斐波纳契数列，它有一些非常有趣的数学、几何学和自然界的特性。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把这个数列用公式表示出来，作为估算兔子繁殖数量的一种方法，从那以后，我们发现这个数列以吸引人的方式模拟了其它一些自然现象，比如螺旋贝壳的结构或者在一朵花的花瓣的组合。 我们可以直接根据这个递归方程明确地写出一个递归函数来计算第n个斐波纳契数。Fibonacci (n)可以通过Fibonacci(n-1)+Fibonacci(n-2)递归计算出来。递归的基本条件是非常简单的Fibonacci(1)和Fibonacci(0)都等于1的事实。图17.13给出了计算第n个斐波纳契数的递归代码。我们将使用这个例子，以计算系统的更低层的视角查看递归是如何工作的。特别的，我们将查看运行时栈的机制以及它是如何处理递归调用的。无论函数何时被调用，不管是被它本身调用还是被其他函数调用，活动记录的一个新的副本被压入运行时栈中。也就是说，每一个函数的调用都会得到参数和局部变量的一份新的、私有副本，每一份副本不同于任何其他副本。为了递归的运行，必须如此，运行时栈使递归能够运行。如果函数的变量被静态的分配于存储单元中，每一次对Fibonacci的递归调用都会覆盖前次调用的值。现在让我们看看当以3为参数，调用Fibonacci(3)时发生了什么。我们从运行时栈顶部的Fibonacci(3)的活动记录开始。图17.14显示了当计算最初的函数调用时栈的发展过程。函数调用Fibonacci(3)会计算Fibonacci(3-1)，因为表达式Fibonacci(n-1)+Fibonacci(n-2)的自左向右计算的。因此，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）。调用Fibonacci(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)+Fibonacci(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)调用的一个子集。在这一章的结尾有一个习题，要求计算在求Fibonacci(n)的值时进行的函数调用的次数。LC-3编译器为这个程序生成如下代码，列在图17.15中。注意，因为这个函数是递归的，所以不需要特别的处理。由于激活函数的运行时栈的机制，递归函数的处理与每种其他函数都一样。如果你仔细检查代码，你会注意到，为了恰当的翻译Fibonacci的24行，编译器生成了一个临时变量。在编译复杂的表达式时，大多数编译器都会生成那样的临时变量。那样的临时值被存储在活动记录顶部为程序声明的局部变量分配的空间中。17.6 二分法查找在本章的绪言里，我们描述了一种在按照字母表顺序排列的试卷堆中查寻一份指定的试卷的递归技术。这种技术叫做二分法查找，这是一个在一组有序元素中寻找一个特定元素的快速方法。此时，我们已经理解了递归和数组，就可以用C语言定义一个递归函数来实现二分法查找。如果我们想要在一组按递增顺序排列的整数数组里查找某个整数值。这个函数应该返回这个整数的下标，如果这个整数不存在，则返回-1。为了实现这个任务，我们将使用如下的二分查找技术：对于一个数组和一个要查找的整数，我们将检查这个数组的中点，判定要查找的整数是否：(1)等于中点的数值，(2)小于中点的数值，(3)大于中点的数值。如果是相等的，我们就完成了。如果是小的，我们再次执行查找，只是这次只对数组的前一半查找。如果是大的，我们只对数组的后一半执行查找。注意，我们可以使用递归调用表示情况(2)和(3)。但是如果我们要查找的数值不在这个数组中将发生什么？已知递归技术在越来越小的原始数组的子数组中执行查找，如果我们要查找的那个记录不存在，那么最后将在没有元素的数组（即，大小为0）中执行查找。如果我们遇到这种情况，就返回-1。这将是递归的基本条件。图17.16是C语言的二分查找算法的递归实现。注意为了判断每一步的数组的大小，我们在每一次调用BinarySearch时都从子数组的起点遍历到终点。每次调用都重新定义变量start和end来查找原始数组list的越来越小的子数组。图17.17图示了在执行期间这段代码的表现。数组list包含11个元素，如图所示。对BinarySearch的第一次调用传递了我们要查找的数值（item）以及被查找的数组（回忆16章，这是数组的第一个元素的地址，或者基址）。与数组一起，我们还提供了数组的范围。也就是说，我们提供了要查找的数组部分的起点及终点。在随后的每一个对BinarySearch的递归调用中，这个范围被缩小，最终到达一点，在这一点上，我们要查找的数组的子集只有一个元素或根本没有元素。这两种情况是递归的基本条件。如果不求助于像二分法查找这样的技术，我们可以尝试一个更直接遍历数组的顺序查找。也就是说，我们可以检查list0，然后list1，再list2，如此继续，最终或者找到那个记录或者确定其不存在。然而，二分法需要更少的比较，而且如果数组足够大的话可能执行得更快。在后面的计算课程中，你将分析二分法查找，推导出其运行时间与log2n成比例，此处n为数组的大小。而另一方面，顺序查找是与n成正比的。17.7 从整数到ASCII码我们最后一个关于递归函数的例子是一个将任意一个整数数值转换为ASCII码字符串的函数。回忆第10章，为了在显示器上显示出一个整数的数值，数值的每一位都必须被单独取出，转换为ASCII码，然后显示于输出设备上。在第10章，我们使用一个简单的重复技术写了一个LC-3程序来实现。我们可以使用如下的递归公式来递归的完成这个任务：如果要显示的数字是一位的，我们就把它转换成ASCII码并显示出来，这样我们就完成了。如果数字是多位的，我们对那个数字除了最低位（最右边的）进行一个递归调用，当递归调用返回时，我们输出最右边的一位。图17.18列出了C语言的这个递归函数。它读入一个正整数值，把这个值的每一位转化为ASCII码，并且将结果字符显示出来。 递归函数IntToAsii按照如下方式工作：为了打印出一个数字，例如，假设是21,669（即，我们正在调用IntToAsii（21669），函数会把这个问题分成两个部分。首先，通过一次对IntToAsii的递归调用，2166必须被显示出来，并且一旦调用结束，9也将被打印出来。 函数通过将参数num除以10将其向右移动一位，从而移除它的最低位。对于这个新（也更小）的值，我们进行一次递归调用。如果输入的值num只有一位，它将被转化为ASCII码，并且被显示在屏幕上这种情况不需要递归调用。 一旦控制返回到每一次的调用，被移除的数位被转化为ASCII码并被显示。为了明确起见，我们列出最初的调用IntToAsii（12345）中的调用顺序。17.8 总结 在这一章，我们介绍了递归的概念。我们可以使用对一个更小的子问题调用它自身的函数来递归地解决一个问题。对于递归，我们假设用f(n)来表示函数，而对于在n的更小的数值上的相同函数，假设用f(n-1)来表示。比如斐波纳契数列，可以被递归地表示为：Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2);为了使递归能够最终终止，递归调用需要一个基本条件。 递归是一种强大的程序设计工具，当应用于正确的问题上时，可以使程序设计任务变得相当容易。例如，汉诺塔问题可以使用递归以简单的方法解决。而用重复来表示就要困难得多。在今后的课程中，你将查看包括指针的组织数据的方式（如树和图），而操作这些数据结构的最简单的技术就包括递归函数。从更低的层次看，递归函数的处理方式与其他任意