7.3　函数递归调用精彩演绎

7.3.1　函数递归调用的定义

所谓递归，就是指函数的递归调用。函数的递归调用，也是属于一种函数的嵌套调用，只不过这是一种很特殊的函数嵌套调用。为什么特殊呢？因为它是自己调用自己。自己调用自己导致了很多初学的朋友觉得递归调用很难，很不好理解，实际它并没有那么难以理解。

举个递归调用的例子，有如下自定义函数：

在main函数中，调用上述的diguifunc函数，代码如下：

把程序执行起来，等几秒钟，可以看到，屏幕不断滚动并输出如下内容：

继续等待一会儿（几秒）后，有的Visual Studio编译环境版本直接出现程序报错，弹出异常对话框，有的Visual Studio编译环境版本直接退出了整个程序的执行，等等，各种不正常的现象都会发生，但总归就是一句话，程序执行不正常，出现了各种问题。

报错也好，执行崩溃或者程序退出也罢，根本原因是系统的资源（内存）耗尽了，这是因为不断无限次地调用函数自身所导致。很容易想象，调用函数是要占内存的，每多调用一次函数，系统的内存就要多占用一些，当函数调用完成，从函数中返回时，调用该函数时所占用的内存才能被系统释放掉。以图7.2为例，如果是在第3步定义一个变量（局部变量，后面会讲解这个概念），那么这个变量所占用的内存需要到第11步才能被释放，这也说明了，函数嵌套调用的层次越深，所需要占用的系统内存就越大。还是以7.2节内容所举的范例来进一步阐述函数嵌套调用时的内存分配问题，不过这里要改造一下7.2节的代码。

在函数qtfunc1中，额外定义了一个变量tempvar1，在函数qtfunc2中，额外定义了一个变量tempvar2，这两个变量在执行到相应代码时肯定都是要占用内存。代码如下：

这里可以设置断点并进行单步调试。不难发现，tempvar1的内存需要在qtfunc1函数执行完之前才释放，而tempvar2的内存需要在qtfunc2函数执行完之前才释放，不光是这些局部变量，在函数调用过程中，可能还会存在函数参数需要临时保存，一些函数调用关系（例如qtfunc1调用的qtfunc2，qtfunc2调用的qtfunc3）也要记录，这样函数调用返回的时候才知道返回到哪个函数里。对于函数嵌套调用来讲，只需要记住，系统会给函数调用分配一些内存来保存提到的这些信息（局部变量、函数参数、函数调用关系等），但分配的内存大小是固定和有限的，一旦超过这个内存大小，程序执行就会出现上述崩溃或者异常退出的情况。

本节开头做了一个函数递归调用（自己调用自己）的代码演示，针对这个调用，可以绘制一个比较形象的图看看函数调用关系，如图7.3所示。

图7.3　函数递归调用关系图（这种调用导致死循环）

这个例子导致函数自己不断地调用自己（递归调用），造成了调用的死循环。所以递归调用这种自己调用自己的方式必须要有一个出口，这个出口也叫作递归结束条件，有了这个递归结束条件，就能够让这种函数调用结束，可以用图7.4做一个形象一点的说明。

图7.4　函数递归调用关系图（增加出口条件代码使递归函数能够执行结束）

总结一下图7.4：递归调用就是一个函数在它的函数体内部调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层，递归函数必须有结束条件（递归调用的出口），从而引出下一个话题：递归调用的出口。