在c语言中,一个调用自身(不管是直接地还是间接地)的函数被称为是递归的(recursive)。你可能不明白究竟为什么一个函数要调用自身,要解释这种情况,最好先举一个例子。一个经典的马上可以举出来的例子就是计算整数的阶乘。为了计算一个整数的阶乘值,你要用这个数(x)乘以它的前一个数(X一1),并且一直乘下去,直到到达1。例如,5的阶乘可以这样来计算:
5*4*3*2*1
如果X是5,你可以把这个算式转换为一个等式:
X!=X*(X-1)*(X-2)*(X-3)*(X-4)*1
为了用C语言完成这项计算任务,你可以编写一个名为calc_factorial()的函数,它反复调用自身,每次都把被计算的值减1,直到到达1。下面的例子说明怎样编写这个calc_factorial()函数:
#include<stdio.h>
void main(void);
unsigned long calc_factorial(unsigned long x);
void main(void)
{
int x=5;
printf("The factorial of %d is %ld. \n" ,x,calc_factorial(x));
}
unsigned long calc_factorial(unsigned long x)
{
if(! x)
return 1L ;
return(x * calc_factorial(x-1L)) ;
}
在上例中,calc_factorial()在调用自身前要先把x的值减去1。如果x等于O,if语句的条件将为真,calc factorial()将不再被递归调用。因此,当被计算的值到达O时,calc_factorial()作完最后一次递归调用并退出,其返回值为1。返回1是因为任何值都可以安全地和1相乘,并仍能保持其原来的值。如果程序中包含下述语句:
x=calc_factorial(5);
它将开展为:
x=5*(5-1)*(4-1)*(3-1)*(2-1)*1;
因此,x将等于5的阶乘,即120。
递归是一个简洁的概念,同时也是一种很有用的手段。但是,使用递归是要付出代价的。与直接的语句(如while循环)相比,递归函数会耗费更多的运行时间,并且要占用大量的栈空间。递归函数每次调用自身时,都需要把它的状态存到栈中,以便在它调用完自身后,程序可以返回到它原来的状态。未经精心设计的递归函数总是会带来麻烦。如果可能的话,你应该避免使用递归函数。
例如,前文中的阶乘函数可以写成下面这种形式:
# include <stdio. h>
void main(void) ;
unsigned long calc factorial(unsigned long x);
void main (void)
{
int x=5;
printf("The factorial of %d is %ld. \n" ,x ,calc_factorial (x)) ;
}
unsigned long calc-factorial(unsigned long x)
{
unsigned long factorial;
factorial=x;
while (x>1L)
{
factorial * =--x;
}
return (factorial);
}
这个版本的calc_factorial()函数用一个while循环来计算一个值的阶乘,它不仅比递归版本快得多,而且只占用很小的栈空间。