在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循环来计算一个值的阶乘，它不仅比递归版本快得多，而且只占用很小的栈空间。
|
楼主
标题置顶
标题高亮
