5.6　递归

递归是函数调用的特殊形式，即函数调用其自身，这在C语言中是允许的。在具体使用时又分直接递归和间接递归。其区别如下:

直接递归:函数直接调用自身。例如有函数f，在f的定义(函数体)中包含了调用f的语句就是直接递归。

间接递归:函数采用间接的方式来调用自己。例如有两个函数f1和f2，其中f1的定义(函数体)中包含了调用函数f2的语句，而f2的定义(函数体)中则包含了调用f1的语句，这也相当于函数f1调用其自身，即间接递归。

数学中的求阶乘是递归的一个典型例子。现有如下定义:

根据上述定义来求5的阶乘。

0!=1

1!=1*0!=1

2!=2*1!=2

3!=3*2!=6

4!=4*3!=24

5!=5*4!=120

下面写程序来计算n的阶乘。

【例5．12】利用递归求n!。

运行结果如图5-18所示。

图5-18

分析:

本程序就是一个典型的直接递归。函数f的作用就是求整数n的阶乘，在f的函数体中包含了调用f本身的语句见代码第17行。下面来看看具体的调用过程。输入的整数为6，程序执行的步骤如下:

(1)进入main函数执行到第8行时，得到fac=f(6);整数6传递给了形参n，进入函数体执行后得到6*f(5);

(2)现在计算f(5)，进入函数体执行后得到5*f(4);

(3)上一步中f(4)调用的结果为4*f(3);

(4)上一步中f(3)调用的结果为3*f(2);

(5)上一步中f(2)调用的结果为2*f(1);

(6)上一步中f(1)调用的结果为1*f(0);

(7)f(0)调用后可以得到返回值为1，此时流程返回第(6)步得到的相应结果为1，这个1又被送到了第(5)步进行计算。照此进行下去，一直等到流程返回至第(1)步得到了720这个结果。最终“720”这个数值被返回到main函数的第8行代码处，即赋给了变量fac并输出该结果。

通过上例我们来总结用递归来解决问题时需要考虑的问题，主要有下列3个方面:

(1)第1个数据是否已知?

(2)第n个数据与第n－1个数据之间有何关联?

(3)递归终止的条件是什么?

当然，能用递归解决的问题也可以采用非递归的办法来解决，如迭代法。

【例5．13】利用迭代法求n!。

运行结果如图5-19所示。

图5-19

分析:

本程序采用迭代的方法来求n的阶乘，主要是利用一个for循环语句来实现，见代码第15、16行。