文档介绍：第十七章递归
绪论
我们从描述一个你可能已经熟悉的递归程序开始这一章。假如我们想从一堆已经按字母顺序排列的试卷中查找到某个学生的成绩。我们将随机地从试卷堆的中间检查其姓名。如果这个被随机选中的成绩不是我们想要查找的,我们将用同样的方法查找适当的一半。也就是说,取决于我们要查找的名字比试卷中间点的名字小或大,我们将从前一半或者后一半里重复这样的查找。例如,假如我们要查找Babe Ruth的成绩,而在中间点,我们找到的是Mickey Mantle的成绩。我们将再次从初始堆中的后一半里重新查找。如果它存在于试卷堆中的话,很快地,我们将定位出Babe Ruth的成绩。这种查找一组已被排过序的元素的方法是递归的。我们在越来越小的试卷堆中一直应用这一相同的查找算法。
隐藏在递归之后的思想是简单的:一个递归的函数通过在一个更小的子任务中调用它本身来解决某个任务。正如我们即将看到的,递归是另一种表达重复程序结构的方法。递归的强大功能存在于它能够极好地捕获某些任务的控制流程。对于某些编程问题,递归的解决方法比使用相应的传统重复方法简单得多。在这一章,我们将通过五个不同的例子向你介绍递归的概念。我们检查递归函数是怎样在LC-3里实现的。运行时栈机制的好处就在于递归函数不需要特别的处理——它们以与其他任何函数相同的方式执行。本章的主要目的是为你提供递归的初步但深入的研究,这样你就可以分析和推理递归程序了。能够理解递归代码对于写递归代码是必要的因素,而且最终将使递归变成你解决编程问题的工具集中的一部分。
什么是递归?
调用它本身的函数就是递归函数,。
这个函数计算从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+1
RunningSum的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)。