C++抽象编程——递归

发表时间：2022-03-25来源：网络

最近在学习standford的CS106b，借知乎把一些重要知识点记录下来。

递归（recurison）是我在CS106b中接触的第一个比较困难也很有趣的章节。类似C课程中函数迭代求解阶乘，这里的应用举例更广泛。

Marty（授课老师）首先举了一个M&M bowl的例子来引入递归的概念：

问题介绍：现在有一碗M&M，我们需要使里面的M&M的数量翻倍。条件：我们不知道现在碗中的M&M数量。参与此项工作的人数不限制，但每个人的计数能力仅限于1。每个人可放入的M&M数量不受限制。

条件2是我根据迭代思路稍微修改的条件（便于引导读者）。

我第一次看到这个问题，想到的是：既然每个人只能数1个，那每个人从碗中拿出1个M&M，然后再在另一新碗中放入2个M&M不就解决了吗？但这从编程的角度，仅应用循环的知识。那么，现在另加一条件：

4. 无其他可用于容纳M&M的容器

现在整理下思路，问题的关键在于得知现有碗中的M&M数量，但数量的加倍不能在计数过程中操作（否则碗中M&M永远也数不完），那么这样引导，数量加倍的操作能否放到碗中的M&M计数结束（即已清空）？也就是说这些之前计完数的人，之后还需要依次执行加倍碗中数量的操作（也就是递归思想的体现），按照编程的思想，这一思路可写为：

doubleMnMs(bowl):{ if(bowl is empty){ //计数结束，将空碗递给上一个人} else if (bowl is handed by last person){ // 计数操作：取出一个M&M，并将碗递给下一个人 } else if (bowl is handed by next person){ // 加倍操作：向碗中放入2个M&M，并将碗递给上一个人 if (no next person){ // 操作结束 return 0; } }

总结上述这一例子，可以得出递归算法的2个重要特性：

每次的递归操作相类似（self-similarity）结束递归的base case，M&M例子中bowl is empty的情况

类似递归，C中函数迭代的例子：

int factorial(int n){ if (n == 0 || n == 1){ // base case return 1; }else{ // recursive case return n*factorial(n-1); } }

需要注意的是，上述的回溯是单向的，即一旦到达base case，回溯就将开始直至代码结束。这一特点使得此类递归操作更容易理解。实际上，更加复杂的递归，较难将每一步都提前计算好，编程更注重迭代的过程，这也更贴近抽象编程的思想，使代码变得更加有趣，这将是本文重点介绍的内容。

下面介绍一有趣的递归例子——汉诺塔

6层汉诺塔问题，玩家需要将1号汉诺塔的6个圆盘移动到3号汉诺塔问题介绍：图中为3个汉诺塔，玩家需将1号汉诺塔的6个圆盘移动到3号汉诺塔。条件：小圆盘上不能放大圆盘，一次只能移动一个圆盘，2号汉诺塔可作为中介塔。

对于此问题，显然我们无法提前将整个操作流程规划好。那如何采用递归解决这一问题？

递归的关键在于找到问题中的self-similarity，或者说是否可将问题拆解为相似的部分（像M&M问题中每个人仅做取出、递给和加倍的简单操作）。对于上述的6层汉诺塔，如果我们能将1-5层圆盘移动到2号塔，那么接下来可以将最下面的6号圆盘移动到3号塔，之后只需要想办法将2号塔台的5个圆盘移动到3号，问题就解决了。

简化问题：想办法将1-5号圆盘移动至2号塔，移动6号圆盘到3号塔，再将1-5号圆盘移动到3号塔

这样的想法可能看似很“愚蠢”（如何将1-5层圆盘移动到2号塔，更别说之后其移动到3号塔？？），但实际上这样的思考过程已经将原先的6层汉诺塔问题化简为5层汉诺塔，因为我们在这些操作中不需要再考虑6号圆盘（因为它是最大圆盘，始终位于塔台最下，遵守了条件）。

那么现在首先需解决的问题为如何将1-5层圆盘从1号塔移动到2号塔？（注意此时目标塔台为2号塔台），继续按照上述的思路，我们需要将1-4号移动到3号塔，然后将5号移动到2号，之后再将1-4号移动到2号塔上。

继续简化：想办法将1-4号圆盘移动至3号塔，移动5号圆盘到2号塔，再将1-5号圆盘移动到2号塔

按照这样的思路，发现这一想法似乎变得实际可行，因为任何一个操作都可以拆解为上述的流程（可以称其为“三步走”方法）。想法既然可行，那么写成代码也就不难。我们的递归函数的参数需要知道当前操作塔台号、移动至的目标塔台号和需要移动的圆盘数，代码如下：

void moveDiscs(int numDics, int startPeg, int targetPeg){ // 这里定义一个函数thirdPegNumber()用于得知当前操作的中介塔台号 int thirdPeg = thirdPegNumber(startPeg,endPeg) ; //三步走 moveDics(numDics-1,startPeg,thirdPeg); move(startPeg,targetPeg); moveDics(numDics-1,thirdPeg,targetPeg); // move()和thirdPegNumber()均为写好的函数，具体代码未给出，读者理解迭代代码结构即可 }

便于理解消化，给出5层汉诺塔的移动操作，可以观察其中出现的“三步走”操作

Cantor Set 康托尔集

这一例子类似细胞繁殖，取一段长度固定的直线段，将它三等分后去掉中间一段，将剩下两端执行三等分操作，各自去掉中间的一段，剩下更短的四段，以此类推......这里定义对绳子三等分的次数为康托尔的阶数(level)。

7阶的康托尔集合

如何利用递归解决这一问题，思路同样是寻找每次操作的self-similarity。对于这一问题，明显发现到绳子的每次三等分操作相类似。进一步地，上图中7阶的康托尔集合可以简化为除去第一条最长绳子的6阶康托集合，那么这一问题也就可以按照之前的思路快速解决。代码中，我们的递归函数参数需要阶数level，当前阶数的绳长length，以及标明位置的x和y。

void cantorSet(GWindow & window, int x, int y, int length, int level); int main(){ GWindow window(800,600); window.setColor("black"); cantorSet(window,50,50,700,10); return 0; } void cantorSet(GWindow & window, int x, int y, int length, int level){ if(level==0){ window.drawLine(x,y,x+length,y); }else{ window.drawLine(x,y,x+length,y); cantorSet(window,x,y+10,length/3,level-1); cantorSet(window,x+2*length/3,y+10,length/3,level-1); } }

注意到if语句的两个分支中都有drawline()的操作，因此代码还可简化为将level=1的情况并入另一语句中，并在level=0时，不做任何操作。

void cantorSet(GWindow & window, int x, int y, int length, int level){ if(level>0){ window.drawLine(x,y,x+length,y); cantorSet(window,x,y+10,length/3,level-1); cantorSet(window,x+2*length/3,y+10,length/3,level-1); } }

观察7阶康特尔集的生成过程，理解递归过程中的代码执行顺序。

简单加乘法计算

问题介绍：要求给出一递归函数，输出数学表达式的计算结果。条件：数学表达式中对于优先级高的运算将添加括号，例如：(1+(2*4))

注意到，每个括号内部都需要进行一次二元运算，这一特征即为本题递归的self-similarity。代码的大致思路为：对于一表达式，从左至右依次读入字符，遇到"("说明开始一个二元运算，那么开始读取运算的左右数和识别中间的运算符，若在读取的过程中再次遇到"("，则迭代上述的操作。

运算的递归流程int evaluate(string exp); int evaluateHelper(string exp, int& index); void test_evaluate(const string expression, int expected); int main(){ cout

上一篇：C/C++编程笔记：C/C++ 的编译和链接

下一篇：全面回顾认识C++，全面了解。