您当前的位置:首页 > 计算机 > 编程开发 > C语言

什么是C语言递归(recursion)?怎样使用递归?

时间:12-30来源:作者:点击数:

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门