6.3.3　递归调用

递归调用是指函数自己调用该函数本身，即一个函数在其函数体内调用其函数本身的调用方式。递归调用中的函数称为“递归函数”。在递归函数中，一个函数本身既是主调函数又是被调函数。执行递归函数时，将反复多次调用其本身。每递归调用一次就进入新的一层。递归调用的示例如下。

int fun（int a）//函数定义

{

int i；

b=fun（i）；//递归调用

return b；

}

在本例中声明了一个函数fun（），在函数fun的函数体中同样调用了该函数，因此这是一个递归函数。该函数在运行时将无休止地调用其自身，这当然是不合理的。在程序中使用递归调用时，一定要防止出现这种无休止地调用，否则将形成一个死循环。因此在函数体内一定要有终止递归调用的条件语句，一旦满足条件，则立即停止递归调用，然后逐层返回。

从变量以及内存分配角度来看，函数每调用自身一次，都将在栈中创建新的局部变量并分配内存，函数使用这些新的局部变量重新运行。当每次递归调用返回时，原有的局部变量和参数就从栈中删除，从函数内的此次函数调用点重新启动运行。n！的计算是最典型的采用递归调用的情况。n！可用下述公式表示。

n！=n×（n-1）×……×1；（n＞1）

n！=1；（n=0，1）

按照上面的公式，下面采用递归函数来进行计算，程序示例如下。

include＜stdio.h＞//头文件

long nn（int n）//定义函数

{

long result；

if（n＞1）

result=n*nn（n-1）；//递归调用

else

result=1L；

return result；

}

void main（）//主函数

{

int num；

long y；

num=7；//赋初值

y=nn（num）；//调用函数计算阶乘

printf（“7！=%ld\n”，y）；//输出结果

}

该程序可以在KeilµVision3编译环境中执行，运行的结果如下。

7！=5040

在本例中，定义递归函数nn（），用于计算n！的值。主函数调用函数nn后即进入函数体进行运算，如果n≤1，将结束函数的执行，否则就递归调用nn函数自身。因为每次递归调用的实参为n-1，即把n-1的值赋予形参n，最后当n-1的值为1时再作递归调用，形参n的值也为1，递归将终止。然后可逐层返回，便可以得到最终n！的结果。

说明本例除了采用递归调用外，也可以采用for循环语句来实现，即从1×2开始，再×3，……，×n。采用for循环语句比递归法更容易理解和实现。但是实际中有些问题，例如汉诺塔问题，就只能采用函数递归调用才能完成。

采用递归函数可以使代码紧凑、程序简洁，尤其是与人工智能有关的问题，更适合采用递归调用的方法。但是递归程序并没有减少代码和节省内存空间。递归形式比非递归形式运行速度反而要慢一些，这是因为在递归调用时，附加的函数调用增加了执行时间，而且要占用大量内存空间作为递归调用时的栈。在大部分情况下，速度相差不明显。

注意在程序中使用递归函数时，必须在函数体内，使用if语句使函数在不执行递归调用时及时返回。否则一旦调用函数后，将进入死循环，这是实际编程中很容易犯的一个错误。