发布日期:2015-12-30 11:13 来源: 标签: 编程语言 C教程 C语言递归函数 C语言函数调用
本章我们主要学习什么是递归函数?C语言中如何调用递归函数?下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
1.什么是递归函数(recursive function)   
递归函数即自调用函数,在函数体内部直接或间接地自己调用自己,即函数的嵌套调用是函数本身。   
例如,下面的程序为求n!:   
      long fact(int n)   
      {   
       if(n==1)   
       return 1;   
       return fact(n-1)*n; //出现函数自调用   
      } 
2.函数调用机制的说明   
任何函数之间不能嵌套定义, 调用函数与被调用函数之间相互独立(彼此可以调用)。 发生函数调用时,被调函数中保护了调用函数的运行环境和返回地址,使得调用函数的状态可以在被调函数运行返回后完全恢复,而且该状态与被调函数无关。   
被调函数运行的代码虽是同一个函数的代码体,但由于调用点,调用时状态, 返回点的不同,可以看作是函数的一个副本,与调用函数的代码无关,所以函数的代码是独立的。被调函数运行的栈空间独立于调用函数的栈空间,所以与调用函数之间的数据也是无关的。函数之间靠参数传递和返回值来联系,函数看作为黑盒。   
这种机制决定了C/C++允许函数递归调用。
3.递归调用的形式   
递归调用有直接递归调用和间接递归调用两种形式。   
直接递归即在函数中出现调用函数本身。   
例如,下面的代码求斐波那契数列第n项。 斐波那契数列的第一和第二项是1,后面每一项是前二项之和,即1,1,2,3,5,8,13,...。 代码中采用直接递归调用:   
      long fib(int x)   
      {   
       if(x>2)   
        return(fib(x-1)+fib(x-2)); //直接递归   
       else   
        return 1;   
      }   
间接递归调用是指函数中调用了其他函数,而该其他函数却又调用了本函数。例如,下面的代码定义两个函数,它们构成了间接递归调用:   
      int fnl(int a)   
      {   
       int b;   
       b=fn2(a+1); //间接递归   
             //...   
      }   
      int fn2(int s)   
      {   
       int c;   
       c=fnl(s-1); //间接递归   
             //...   
      }   
上例中,fn1()函数调用了fn2()函数,而fn2()函数又调用了fn1()函数。 
4.递归的条件
(1)须有完成函数任务的语句。   
例如,下面的代码定义了一个递归函数:   
      #include  
      void count(int val) //递归函数可以没有返回值   
      { if(val>1)   
         count(val-1); 、   
       cout<<"ok:" <<<="" 此语句完成函数任务="" />   
该函数的任务是在输出设备上显示"ok:整数值”。   
(2)—个确定是否能避免递归调用的测试   
例如,上例的代码中,语句"if(val>1)"便是—个测试, 如果不满足条件,就不进行递归调用。   
(3)一个递归调用语句。   
该递归调用语句的参数应该逐渐逼近不满足条件,以至最后断绝递归。   
例如,上面的代码中,语句“if(val>1)” 便是一个递归调用,参数在渐渐变小,这种发展趋势能使测试"if(val>1)”最终不满足。   
(4)先测试,后递归调用。   
在递归函数定义中,必须先测试,后递归调用。也就是说,递归调用是有条件的,满足了条件后,才可以递归。  
例如,下面的代码无条件调用函数自己,造成无限制递归,终将使栈空间溢出:   
      #include   
      void count(int val)   
      {   
       count(val-1); //无限制递归   
       if(val>1) //该语句无法到达   
        cout <<"ok: " <<    } 
5.消去递归 
   大多数递归函数都能用非递归函数来代替。例如,下面的代码求两个整数a,b的最大公约数,用递归和非递归函数分别定义之:   
      long gcdt(int a,int b) //递归版   
      {   
       if(a%b==0)   
        return b;   
       return gcdl(b,a%b);   
      }   
      long gcd2(int a,int b) //非递归版   
      {   
        int temp;   
        while(b!=0)   
        {   
         temp=a%b;   
         a=b;   
         b=temp;   
        }   
        return a;   
      }    
6.递归的评价 
1)递归的目的是简化程序设计,使程序易读。   
2)但递归增加了系统开销。 时间上, 执行调用与返回的额外工作要占用CPU时间。空间上,随着每递归一次,栈内存就多占用一截。   
3)相应的非递归函数虽然效率高,但却比较难编程,而且相对来说可读性差。   
4)现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高,程序在更多的场合优先考虑可读而不是高效,所以,鼓励用递归函数实现程序思想。

相关评论

专题信息
    C语言是一种计算机程序设计语言。它既有高级语言的特点,又具有汇编语言的特点。它可以作为系统设计语言,编写工作系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。C语言对操作系统和系统使用程序以及需要对硬件进行操作的场合,用C语言明显优于其它解释型高级语言,有一些大型应用软件也是用C语言编写的。 C语言具有绘图能力强,可移植性,并具备很强的数据处理能力,因此适于编写系统软件,三维,二维图形和动画。它是数值计算的高级语言。C语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。