程序员大神教你学C语言编程——递归函数

一、什么是递归函数

（1）递归函数即自调用函数，在函数内部直接或间接地自己调用自己，即函数的嵌套调用是函数本身。

从字面上来看递归，递即递推，采用循环的思路来描述复杂问题的方法。在递推阶段每一个递归调用通过进一步调用自己来记住这次递归过程，当其中调用满足终止条件时，递推结束。归即回归，函数调用已逆序的方式回归，知道最初调用的函数返回为止，此时递归过程结束。举个例子：

（2）递归的基本原理

第一：每一级的函数调用都有自己的变量。

第二：每一次函数调用都会有一次返回。

第三：递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。

第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。

第五：虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

最后：递归函数中必须包含可以终止递归调用的语句。

（3）递归的优缺点

其优点在于为某些变成问题提供了最简单的解决方法，简化了程序设计。而缺点是一些递归算法会很快耗尽计算机的内存资源。同时，使用递归的程序难于阅读和维护。

二、函数调用机制的说明

任何函数之间不能嵌套定义，调用函数与被调用函数之间相互独立递归函数的概念用法与实例（彼此可以调用）。发生函数调用时，被调用函数中保护了调用函数的运行环境和返回地址，使得调用函数的状态可以被调用函数运行返回完全恢复，而且该状态与被调用函数无关。

被调用函数运行的代码虽然是同一个函数的代码体，但由于调用点，调用时状态，返回点的不同，可以看作是函数的一个副本，与调用函数的代码无关，所以函数的代码是独立的。被调用函数运行的栈空间独立于调用函数的栈空间，所以与调用函数之间的数据也是无关的。函数之间考参数传递和返回值来联系，函数看作为黑盒。

这种机制决定了 C/C++ 允许函数递归调用。

上面这段话的意思可以理解为，递归函数调用自身函数的时候，可以看作调用的是调用别的函数。

再有，被调用函数运行的栈空间独立于调用函数的栈空间 这句话如何理解？

首先，我们先说一下栈的概念：

参看：递归函数的概念用法与实例

参看：C语言再学习 -- 内存管理

栈是一个后进先出(LIFO)的压入（push）和弹出（pop）式的数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行时系统自动处理。所谓系统自动维护，实际上就是编译器所产生的程序代码。尽管在程序中看不到他们，但是程序员应该对此有所了解。

再看看程序中的栈是如何工作的。当一个函数（调用者）调用另一个函数（被调用者）时，运行系统将把调用者的所有实参和返回地址压入栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用这开始执行时，系统把被调用者的自变量压入栈中，并把栈指针再向下移，以保证有足够的空间存储被调用这声明的所有自变量。当调用这把实参压入栈后，被调用者就在栈中以自变量的形式建立形参。被调用这内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以它为参考，用正或负的偏移量来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这是栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。

现在接着说递归：

上面有提到了函数调用机制。递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。

程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。看下面的例子：

这里有一个问题一定要注意，就是static int sum = 0;

有些人就不明白，为什么要使用 static 类型修饰符，为什么不使用 int sum=0;？如果使用 int sum=0; 这样的语句，在每次调用函数add()的时候，sum的值都是赋值为0，也就是第一步虽然加了1上来，可是第二次调用的时候，sum又回到了0。我们前面说了，static能保证本次初始化的值是上次执行后的值，这样也就保证了前面想加的结果不会丢失。如果你修改为int sum=0，最后结果一定是最后结果是5而不是15。

上面的例子就很好的解释了，被调用函数运行的栈空间独立于调用函数的栈空间 这句话。

三、递归调用的形式

递归函数有直接递归调用和间接调用两种形式.

直接递归即在函数出现调用函数本身，例如：

间接递归调用指函数中调用其他函数，而该其他函数却又调用了本函数。例如：

下面，再扩展一种递归，尾递归

当递归调用是整个函数中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归的。

上面的直接递归例子的返回值是 return num*func(num-1); 是一个表达式自然不是尾递归了，将其改为尾递归：

当编译器检查到一个函数是尾递归的时候，它就会覆盖当前活跃记录而不是在栈中去创建一个新的，这样就解决了普通递归函数占用栈空间过大的问题。遗憾的是，大多数编程语言没有针对尾递归做优化，所以，即使把函数改成尾递归方式，也会导致栈溢出。星辰就暂时把递归说到这，下一篇的话继续接上，内容还是讲递归吧，基于太多，一下子写太多的话，各位看了也会累。