本节书摘来自华章计算机《计算机系统：核心概念及软硬件实现（原书第4版）》一书中的第2章，第2.4节,作者：[美] J. 斯坦利·沃法德（J. Stanley Warford）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.4递归
你曾在字典中查找不认识单词的定义时，发现字典恰恰是以另一个不认识的单词来定义它的吗？接着你就查找第二个单词，发现它是用第一个单词来定义的吗？这是一个循环或间接递归的例子。字典的这个问题源于从一开始你就不知道第一个单词的意思。如果第二个单词用你认识的第三个单词来定义，就能得到满意的结果了。
数学上，函数的递归定义（recursive definition）是指函数使用它自己来定义自己。例如，假设函数f(n)定义如下：
f(n)＝nf(n-1)
若用这个定义来确定f(4)，就在定义中用4代替n：
f(4)＝4f(3)
但是现在你不知道f(3)是什么，那么在定义中用3代替n，得到：
f(3)＝3f(2)
把这个代进f(4)的公式中，得到：
f(4)＝4(3)f(2)
但是，现在你不知道f(2)是什么，定义告诉你它是2乘以f(1)，那么求f(4)的公式变为
f(4)＝4(3)(2)f(1)
可以看到这个定义的问题：没有什么能够结束这个过程，你将无穷尽地计算f(4)。
f(4)＝4(3)(2)(0) (-1)(-2)(-3)...
这就如同字典给了你一个无穷尽的定义串一样，每个单词都基于另一个你不认识的单词。为了完整，定义必须指定某个特定n的f(n)值，那么前述过程就能终止，你可以计算出任何n的f(n)。
下面是f(n)的一个完整递归定义：
f(n)＝nf(n-1)n>1
f(1)＝1
这个定义说明前述过程可以在f(1)停止。因此，f(4)是
f(4)＝4f(3)
＝4(3)f(2)
＝4(3)(2)f(1)
＝4(3)(2)(1)
＝24
你应该知道这就是阶乘函数的定义。
2.4.1阶乘函数
C++中的递归函数（recursive function）是调用它自己的函数。没有什么有新语法的特殊递归语句需要学习。它在运行时栈上分配存储空间的方法和非递归函数是一样的。唯一的不同是递归函数包括一条调用它自己的语句。
图2-22中的函数递归地计算一个数的阶乘，它是f(n)递归定义的一个直接应用。
图2-23给出了简化的该程序运行时栈的历史记录，它隐藏了主程序的栈帧。第一个函数调用来自主程序。图2-23c展示了第一次调用的栈帧，返回地址是ra1，它代表主程序中cout调用的地址。
图2-23图2-22的运行时栈
该函数中第一条语句测试n是否为1。因为n的值是4，所以执行else部分。而else部分的语句
在返回语句的右边包含一个对函数fact的调用。
这是一个递归调用，因为它在函数里调用它自己。这个调用和任何其他函数调用所做的事情顺序是一样的。分配新的栈帧，如图2-23d所示。第二个栈帧中的返回地址是这个函数中调用语句的地址，由ra2来表示。
实参是n-1，由于图2-23c中n的值是4，所以它的值是3。形参n是传值调用的，因此图2-23d顶部栈帧的形参n赋值为3。
图2-23d展示了一个对递归调用来说很典型的奇特现象。图2-22的程序代码中函数fact的形参表中只声明了一个n，但图2-23d中n出现了两次。n的旧实例从主程序获得的值4，而n的新实例从递归调用中获得值3。
计算机暂停该函数旧的执行，并从头开始该函数的一个新的执行。该函数的第一条语句是比较n是否等于1，图2-23d中在运行时栈上有2个n，应该比较哪个n呢？规则是：任何对局部变量或形参的引用指的都是顶部栈帧中的那个。因为n的值是3，所以执行else部分。
但是现在函数又进行一次递归调用，分配第三个栈帧，如图2-23e所示，接着是第四个，如图2-23f所示。每次调用，最新分配的形参n的值都比旧值小1，因为函数调用是
最后，如图2-23g所示，n的值为1 。该函数给栈上标号为retVal的单元赋值为1，跳过else部分，然后终止。这使得控制返回到它的调用语句。
递归返回发生的事情和非递归返回是一样的。retVal包含返回值，返回地址说明接下来要执行哪条语句。图2-23g中，retVal是1，返回地址是该函数中的调用的语句。释放顶部栈帧，调用语句
完成它的执行。该语句将n的值2乘以返回值1，并把这个乘积赋给retVal。这样retVal的值就是2，如图2-23h所示。
每次返回都执行同样的事件序列。图2-23i、j展示了从第二次调用返回的值6，而第一次调用返回的值是24。图2-24展示了图2-22程序的调用序列。主程序调用函数fact，接着函数fact调用它自己3次。本例中，函数fact总共被调用了4次。
你可以看到，程序计算4的阶乘的方法与从它的递归定义计算f(4)的方法一样。计算f(4)从4乘以f(3)开始，接着必须暂停计算f(4)，转而计算f(3)。在得到f(3)的值之后，用4乘以它就得到f(4)。
类似地，程序必须暂停对该函数的一次执行，再次调用同一个函数。运行时栈跟踪记录变量的当前值，这样当函数实例再继续时，还能使用正确的变量值。
2.4.2递归的思考方式
有两种不同的角度来看待递归：微观的和宏观的。图2-23是从微观的角度展示的，精确地给出了执行期间计算机内发生了什么。它考虑的是程序历史记录中运行时栈的细节。宏观的看法不考虑单独的每棵树，它考虑的是整个森林。
为了理解C++怎样实现递归，需要知道微观的看法。在学习Asmb5层怎样实现递归时，必须了解运行时栈的细节。如果只是想写递归函数，应该宏观而不是微观地思考。
写递归函数最难的地方是，必须假设可以调用正在写的程序。为此，你必须忘掉运行时栈，宏观地思考。
数学归纳法证明有助于进行宏观思考。归纳法证明的两个关键元素是
建立基础。
给定n的公式，证明它对n＋1是成立的。
同样，设计递归函数的两个关键元素是
计算该基础的函数。
假设有n-1的函数，写出n的函数。
想象你正在写函数fact，写到了这里：
不知该怎样写下去了。已经计算了基础n=1时的函数，但是现在必须假设能调用函数fact，尽管还没有写完这个函数。必须假设fact(n-1)将返回阶乘的正确值。
这里是必须宏观思考的地方。如果开始想知道fact(n-1)怎样返回正确值，如果栈帧开始在你脑中跳跃，那么这样的思考是不对的。在归纳法证明中，必须假设有n的公式。同样，在写函数fact时，必须假设能调用fact(n-1)，毋庸置疑。
递归程序是基于分治策略的，如果能把一个大问题分解为小问题从而解决它时，这个策略很合适。每次递归调用都使问题变得越来越小，直到程序到达最小的问题，即基础，基础是很容易解决的。
2.4.3递归加法
这里有递归问题的另一个例子。假设list是一个整数数组，想要递归地求出表中所有整数的和。
第一步是构想出以较小问题来解决大问题的解决方案。如果知道怎样求出list[0]和list[n-1]之间元素的和，可以简单地把这个和加上list[n]，就能得到所有整数的和。
第二步是设计出具有适当参数的函数。这个函数通过调用它自己计算n-1个整数的和来计算n个整数的和。因此参数表里必须有一个参数指明对数组中多少个整数相加。应该得到如下的函数头：
怎样建立归纳基础呢？很简单，如果n等于0，那么函数应该把a[0]和a[0]之间的元素求和，一个元素的和就是这个元素a[0]。
现在可以写出
现在，宏观地思考。假设sum(a,n-1)将返回a[0]和a[n-1]之间所有整数的和。要有信心！需要做的就是把这个和与a[n]相加即可。图2-25展示了完成的程序中的这个函数。
尽管写这个函数时没有从微观角度进行考虑，但是仍然可以跟踪记录运行时栈。图2-26展示了对sum头两次调用的栈帧。栈帧由返回值、参数a和n以及返回地址组成。因为这里没有局部变量，所以运行时栈上也没有为它们分配存储空间。
在C++中，数组总是传引用调用的。因此，过程sum中的变量a引用主程序中的list。图2-26b和c中从栈帧中标号为a的单元指向标号为list的单元的箭头表示a引用list。
2.4.4二项式系数函数
递归函数的下一个例子有一个更加复杂的调用序列。这个函数计算二项式扩展的系数。
考虑如下的扩展：
(x + y)1＝x + y
(x + y)2 ＝x2 + 2xy + y2
(x + y)3＝x3 + 3x2y + 3xy2 + y3
(x + y)4＝x4 + 4x3y + 6x2y2 + 4xy3 + y4
这些项的系数叫作二项式系数（binomial coefficient）。如果不带项只写出这些系数，就形成一个由数值组成的三角，称为帕斯卡三角（Pascal抯 triangle）。图2-27是一个最高到7次幂系数的帕斯卡三角。
从图2-27可以看到，每个系数是它正上方和左上方系数的和。例如，第5行第2列的二项式系数10等于4加6，6在10的正上方，4在10 的左上方。
n次幂k项二项式系数b(n, k)的数学表达式是：
b(n, k)＝b(n-1) + b(n-1, k-1)0≤k≤n
它是一个递归定义，因为函数b(n，k)以自己定义了自己。也可以看到，如果k等于0或者如果n等于k， 那么二项式系数的值就是1，数学表达式：
b(n, 0)＝1
b(k, k)＝1
是这个递归函数的归纳基础。
图2-28是递归计算二项式系数值的程序。该程序直接建立在b(n, k)的递归定义之上。图2-29是运行时栈的记录。图2-29b、c和d展示了前3个栈帧的分配，分别代表调用bincoeff(3,1)、bincoeff(2,1)和bincoeff(1,1)。第一个栈帧的
返回地址是主程序中的调用程序，接下来两个栈帧的返回地址是y1赋值语句，即标号为ra2的那条语句。
图2-29e展示了从bincoeff(1,1)的返回，y1获得函数的返回值1，接着y2赋值语句调用函数bincoeff(1,0)。图2-29f展示bincoeff(1,0)执行期间的运行时栈，每个栈帧都有不同的返回地址。
这个程序的调用序列不同于前面那些递归程序的调用序列。另一个程序是不断分配栈帧，运行时栈到达最大高度，然后不断释放栈帧直到运行时栈为空。这个程序是分配运行时栈，达到最大高度，但是不会连续把栈里的栈帧都释放。从图2-29d到图2-29e释放栈帧，但是从图2-29e到图2-29f分配栈帧；从图2-29f到图2-29g到图2-29h又释放栈帧，而从图2-29h到图2-29i又分配栈帧。为什么会这样呢？这是因为这个函数有两个递归调用而不是一个。如果基础判断为真，那么函数不执行递归调用；但如果基础判断为假，则函数执行两个递归调用，一个计算y1，一个计算y2。图2-30展示了该程序的调用序列。可以看到它是树状的。树的每个结点代表一个函数调用。除主程序外，每个结点有两个孩子结点或者没有，分别对应于有两个递归调用或者没有递归调用。
参照图2-30，调用和返回序列是
可以把调用树的执行顺序形象化，把调用树想象成海洋的海岸线。一艘船从主程序的左边沿着海岸线开始航行，并一直保持海岸在它的左边。船会按照结点被调用和返回相同的顺序访问结点，图2-31给出了访问路径。
当从微观的角度分析递归程序时，在构建运行时栈的记录之前，构建调用树更容易一些。一旦构建了调用树，就很容易看清楚运行时栈的行为。每当船在树中向下访问结点时，程序分配栈帧；每当船在树中向上访问结点时，程序释放栈帧。
可以根据调用树确定运行时栈的最大高度。只需记录到达调用树最低结点时分配的栈帧数量，这个数对应的就是运行时栈的最大高度。
按照执行顺序来画调用树不是最简单的方法。前面那个程序的执行序列从下面开始
不应该用这样的顺序来画调用树。从下面这样开始比较容易一些
从程序代码可以看到，BC(3, 1)会调用它自己两次：BC(2, 1)一次，BC(2, 0)一次。然后回到BC(2, 1)确定它的孩子，换句话说，就是要先确定本结点的所有孩子，然后再分析每个孩子的更深层次的调用。
相对于“深度优先”的构造方法，这是用“广度优先”的方法来构造树。在复杂的调用树中多次返回到较高层结点时，深度优先的问题就来了。你可能不记得该结点的执行状态是什么，也就不能确定它的下一个孩子结点是什么。如果一次性确定了一个结点的所有孩子，那么就不需要记得所有结点的执行状态。
2.4.5逆转数组元素顺序
图2-32是一个递归过程而不是函数，它把一个字符数组的元素顺序反转过来。
这个过程把数组str中str[j]和str[k]之间的字符顺序逆转。主程序是想逆转B和d之间的字符，因此它调用reverse，参数j为0，k为7。
这个过程通过把问题分解成更小的问题来解决。因为0小于7，该过程知道要把0和7之间的字符逆转，所以它把str[0]和str[7]互换，接着递归调用自己来交换str[1]和str[6]之间的字符。如果j大于或等于k，就不需要交换，过程也就什么都不用做。图2-33展示了开始时运行时栈的记录。
2.4.6汉诺塔
汉诺塔游戏是一个能用递归技巧方便解决的经典计算机科学问题。这个游戏由3个柱子和一组直径不同的盘子组成。柱子编号为1、2和3，每个盘子的中央有一个洞，能套在柱子上。游戏的初始设置是所有的盘子都套在一根柱子上，没有盘子直接放在直径比它小的盘子上。图2-34是4个盘子的初始设置。
要解决的问题是把所有盘子从起始的柱子移到另一根柱子，并遵循下列规则：
每次只可以移动一个盘子，只能把一根柱子顶部的盘子移动到另一根柱子顶部。
不能把大直径的盘子放在小直径盘子的上面。
解决这个问题的过程有3个参数n、j和k，其中
n是要移动的盘子数量。
j是起始柱子。
k是目标柱子。
j和k是整数，用于标识柱子。给定j和k的值，中间柱子的编号可以用6-j-k计算表示，所谓中间柱子就是既不是起始柱子也不是目标柱子的柱子。例如，如果起始柱子是1而目标柱子是3，那么中间柱子是6-1-3＝2。
Bjarne Stroustrup
Bjarne Stroustrup 1950年出生于丹麦。虽然并非出身于学术家庭，但他依靠自身的努力从丹麦阿鲁斯大学（Aarhus University）获得数学专业硕士学位，然后又从剑桥大学（Cambridge University）获得计算机专业博士学位。
Stroustrup小时候并没有接触过计算机，在大学数学系里他才第一次见到计算机。那台计算机占据了一整个房间，他学会了用Algo 60语言在上面编程。他博士期间的工作是用Simula67语言写了一个分布式系统模拟器。依靠写一些其他专职人员才能写出来的小型商业程序的收入，他供自己完成了正规的教育。他认为这段经历帮助他理解了编程在现实世界的重要性。
1979年完成了剑桥的学业后，Stroustrup举家搬到了新泽西，成为了AT&T贝尔实验室在Murry Hill的研究科学家。C语言和UNIX操作系统就是在这个实验室被研发出来并且流行开来的。
Stroustrup并不满足于当时的编程语言，他发明了一种新的带类的C（C with Classes）语言，在C语言中加入了面向对象的编程特性，就像Simula67中的一样。最终，这个语言演变成了C++，Stroustrup作为C++的发明者为人们所熟知。Stroustrup很早就决定希望他的语言能够支持真实的用户。他了解如果人们不需要去学习一门全新的语言，他的语言就能被广泛接受和使用，所以他使得除了有少数例外，C++与C语言兼容。也就是说，大多数用C语言书写的程序能够用C++编译器进行翻译（显然反过来不行）。这个目标对语言设计来说是限制，但是在它的使用上是大有裨益的。Stroustrup曾经说：“即使没有C语言可以与之兼容，我也会选择其他某种语言来兼容的。我曾经，现在依然，相信如果我的时间用来花在创造另一种书写循环的方式上，那就太不值得了。”事实上，C++语言在市场上非常成功。微软的Word、Adobe的Photoshop和Google的搜索引擎都是以C++来编写的。
Stroustrup当选了美国国家工程院院士，AT&T贝尔实验室院士，荣获ACM的Grace Murray Hopper奖。在本书编写之时，他是德州农工大学（Texas A&M University）计算机科学首席教授（College of Engineering Chair in Computer Science）。
“我总是希望能像使用电话那样简单地使用计算机。我的愿望终于成真了。我不知道该怎样使用电话了。”
—Bjarne Stroustrup
要把n个盘子从柱子j移到柱子k，首先检查是否n=1，如果是，那么简单地把这个盘子从柱子j移到柱子k即可。但如果不是，就把问题分解为几个小部分：
把n-1个盘子从柱子j移到中间柱子。
把一个盘子从柱子j移到柱子k。
把n-1个盘子从中间柱子移到柱子k。
图2-35展示了从柱子1移动4个盘子到柱子3的问题的分解。
假定初始n个盘子堆放的顺序是正确的，这样的操作过程保证盘子不会放在比它直径小的盘子上。例如，如图2-35所示，要把4个盘子从柱子1移到柱子3，这个过程告诉你应该把最上面的3个盘子从柱子1移到柱子2，把底部的一个从柱子1移到柱子3，接着再把那3个从柱子2移到柱子3。
把最上面的3个盘子从柱子1移到柱子2，柱子1上就只剩下底部的一个盘子。这个盘子是直径最大的，因此在移动其他盘子的过程中，放在它上面的任何盘子都是更小的。为了把底部这个盘子从柱子1移到柱子3，柱子3必须是空的。这样就不会把这个底部的盘子放在一个较小的盘子上。当把那3个盘子从柱子2移到柱子3上时，会把它们放在当前在柱子3底部的这个最大的盘子上，这样3个盘子就被正确地放在柱子3上了。
这个过程是递归的。第一步要把3个盘子从柱子1移到柱子2。为此，要把2个盘子从柱子1移到柱子3，再把另一个从柱子1移到柱子2，接着把那2个从柱子3移到柱子2。图2-36展示了这个移动的序列。根据前述推理，能够正确地实施这些步骤。在把2个盘子从柱子1移到柱子3的过程中，可以把这两个盘子中的任意一个放在柱子1底部的两个盘子上，不用担心违反规则。
最终，可以把这个问题归约到只需移动一个盘子的基础步骤，而一个盘子的解决方案是容易的。本章结尾的一道问题就是对汉诺塔游戏的解决方案进行编程。
2.4.7 相互递归
在有些问题最适合的解决方案中，过程不直接调用它们自己，但是仍然是递归的。假设一个主程序调用过程a，过程a包含一个对过程b的调用。如果过程b又包含一个对过程a的调用，那么a和b是相互递归的。尽管过程a不直接调用它自己，但是通过过程b，它间接地调用了它自己。
和普通递归相比，相互递归的实现没有什么不同。运行时栈上分配栈帧的方式也是一样的，先分配参数，接着是返回地址，再是局部变量。
不过，在C++程序中，声明相互递归过程时有一个小问题。原因在于C++语言要求程序的声明必须先于它的使用。如果过程a调用过程b，那么在代码中，b的声明必须在a的声明之前；但是如果过程b调用过程a，那么在代码中，a的声明必须在b的声明之前。问题是，如果每个过程都调用另一个，代码中每个程序都必须出现在另一个之前，这显然是不可能的。
针对这种情况，C++提供了函数原型（function prototype），它允许程序员写出第一个程序的头，而没有过程体。函数原型包括完整的形参列表，但在程序体的位置，放一个分号（;）。在一个过程的函数原型之后，就可以是第二个过程的声明，然后是第一个过程的过程体。
例2.6这是刚才讨论的相互递归的过程a和b的架构：
常量、类型、主程序变量
void a (someType x) ;
void b (someOtherType y) {
b的过程体
}
void a (someType x) {
a的过程体
}
int main( ) {
主程序的执行语句
}
如果b对a有一个调用，编译器将会核实实参的数量和类型是否与前面在函数原型里扫描的a的形参匹配。如果a对b有一个调用，那么这个调用会在a的程序体中，因为b在a的代码块之前，因此编译器已经扫描了b的声明。 □
尽管相互递归不如递归常见，但有一些编译器是基于一种叫递归下降（recursive descent）的技术，这个技术很大程度上使用了相互递归。看看C++语句的结构，你就能明白为什么是这样。把一个if嵌套在一个while中，而这个while又嵌套在另一个if中，这是很有可能的。在使用递归下降技术的编译器里有一个过程用于翻译if语句，另一个过程用于翻译while语句。当正在翻译外层if语句的过程遇到while语句时，它将调用翻译while语句的程序。而当翻译while语句的过程遇到嵌套在里面的if语句时，它又调用翻译if语句的过程，因此是相互递归的。
2.4.8递归的成本
本节例子的选取只基于一个标准：例子说明递归的能力。可以看到在使用递归的解决方案中，运行时栈需要大量的存储空间，同时也要花费时间分配和释放栈帧。递归解决方案在空间和时间上都是昂贵的。
如果一个问题有不用递归的简单解法，那么非递归方法通常优于递归方法。图2-18中的计算阶乘的非递归函数肯定比图2-22的递归阶乘函数好。图2-25对数组元素求和与图2-32都可以不用递归，只用循环就可以很容易地编程。
二项式系数b(n, k)有一个基于阶乘的非递归定义：
如果非递归地计算阶乘，基于这个定义的程序可能比相应的递归程序效率高很多。两种方法的选择还有一个可以考虑的因素：非递归方法需要乘法和除法，而递归方法仅需要加法。
有些问题本质上就是递归的，仅用非递归方法解决非常困难。汉诺塔游戏问题的解决本质上就是递归的。你可以试着不用递归去解决它，看看到底会有多难。快速排序法，最知名的排序算法之一，也属于这种类型，用非递归方法对快速排序进行编程比用递归方法难得多。
