零基础C++从入门到精通：递归函数展示与栈溢出示例

我们知道，在一个函数的内部我们也可以调用另外一个函数。那么这另外一个函数可不可以是当前函数自己呢？答案是可以，C++支持这样的循环调用，也叫作递归（Recursion）。

动手写7.8.1

动手写7.8.1展示了递归函数的语法。运行结果如图7.8.1所示：

图7.8.1　递归函数

addNum（）的作用非常简单，就是将两个数字相加。不过在这里我们是将要加上的numToAdd拆分开来，每次加1，再把numToAdd减1代入下一层函数。比方说这里的例子是3和2，那么调用addNum（）的步骤应该是这样的：

1.第一次调用addNum（3，2），在返回之前再次调用addNum（3，1）。

2.进入addNum（3，1），在返回前再次调用addNum（3，0）。

3.进入addNum（3，0），由于0<=0，返回3。

4.回到addNum（3，1），返回1+3。

5.回到addNum（3，2），返回1+4，也就是5。

递归思想可以用来解决很多复杂的问题，它的关键在于分而治之，也就是把一个问题分解成许多小问题，比如示例中我们把“3+2”的问题分解成“3+1+1”，然后解决。在每一次进入更深一层递归函数的时候，当前函数都要放下正在进行的工作，也就是将本地变量、计算结果和函数状态存进栈里，当所有内层函数都执行完了以后再返回。由于栈是有限的，我们在递归函数中一定要有终止条件，不然可能就会像动手写7.8.2一样造成栈溢出（Stack Overflow）。

动手写7.8.2(www.xing528.com)

动手写7.8.2展示了栈溢出的例子，由于递归函数中没有终止条件，程序将会无限地将函数的状态推进栈中并调用新的函数，直到栈没有空间为止。在编译的时候，Visual Studio可以识别出这个递归函数存在风险。而当我们忽略警告并编译运行的时候，系统将会抛出异常，并且我们可以在“调用堆栈”窗口看到相当数量的对infiniteAdd（）的调用：

图7.8.2　栈溢出

接下来，我们再看一个递归的应用实例来加深对它的理解：

动手写7.8.3

动手写7.8.3展示了一个计算爬楼梯方法数的程序。运行结果如图7.8.3所示：

图7.8.3　爬楼梯程序输出

程序中的countWays（）函数接受台阶数量n作为参数，并输出走台阶的方法数。函数先针对一级和零级台阶的特殊情况进行了单独处理并返回1，因为不可能有别的走法；随后程序就直接返回走一步之后剩下n-1级台阶的走法数countWays（n - 1）以及走两步之后剩下n-2级台阶的走法数countWays（n - 2）的和。接下来我们详细解释一下算法。

这个程序的问题很简单，但是实际思考起来却不太容易，特别是台阶数多的时候。的确，当台阶有十级的时候，走台阶的方法就已经有89种之多。面对这样一个问题，递归的思想是非常适用的，因为我们可以把这个问题分解成多个小的子问题。

就拿四级台阶来说，小强如果先走一级，那么就还有三级没走，如果先走两级，就还有两级没走；只剩两级台阶的时候，小强只有走一级和走两级两种选择。所以如果小强先走两级台阶就一共有2种走法，而先走一级的时候有几种走法则取决于走剩下三级台阶有多少走法。在这里我们不需要关心有多少种走法，因为我们可以简单地在countWays（4）里面调用countWays（3）。也就是说，要解决countWays（4）这个问题，由于小强只有2个选择，因此我们相当于要求出countWays（3）+countWays（2）。