递归函数的理解 - 技术分享 - 志盟培训
首页技术分享 递归函数的理解

递归函数的理解

更新时间:2017-05-17      作者:齐老师       阅读:1056

1、什么是递归函数   

递归函数即自调用函数,在函数体内部直接或间接地自己调用自己,即函数的嵌套调用是函数本身。  

例如,下面的程序为求n!:  

  long fact(int n)  

 {  

      if(n==1)  

      return 1;  

      return fact(n-1)*n; //出现函数自调用  

 }  

   

2、函数调用机制的说明  

任何函数之间不能嵌套定义, 调用函数与被调用函数之间相互独立(彼此可以调用)。 发生函数调用时,被调函数中保护了调用函数的运行环境和返回地址,使得调用函数的状态可以在被调函数运行返回后完全恢复,而且该状态与被调函数无关。  

被调函数运行的代码虽是同一个函数的代码体,但由于调用点,调用时状态, 返回点的不同,可以看作是函数的一个副本,与调用函数的代码无关,所以函数的代码是独立的。被调函数运行的栈空间独立于调用函数的栈空间,所以与调用函数之间的数据也是无关的。函数之间靠参数传递和返回值来联系,函数看作为黑盒。  

这种机制决定了C/C++允许函数递归调用。  

   

3、递归调用的形式  

递归调用有直接递归调用和间接递归调用两种形式。  

直接递归即在函数中出现调用函数本身。  

例如,下面的代码求斐波那契数列第n项。 斐波那契数列的第一和第二项是1,后面每一项是前二项之和,即1,2,3,4,5,6…..。 代码中采用直接递归调用:  

  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、递归的评价      

递归的目的是简化程序设计,使程序易读。  

但递归增加了系统开销。 时间上, 执行调用与返回的额外工作要占用CPU时间。空间上,随着每递归一次,栈内存就多占用一截。  

相应的非递归函数虽然效率高,但却比较难编程,而且相对来说可读性差。  

现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高,程序在更多的场合优先考虑可读而不是高效,所以,鼓励用递归函数实现程序思想。

在线报名

志盟科技上海招聘

在线报名 联系我们

志盟科技深圳招聘

在线报名 联系我们

志盟科技北京招聘

在线报名 联系我们
联系我们

咨询热线:

咨询 QQ:517578         

就业学员

  • 就业学员

    姓名:郭凡凡 
    院校:阜阳师范学院
    就职:佳戴
    职位:软件工程师
    月薪:10000

  • 就业学员

    姓名:陈祥龙 
    院校:中北大学
    就职:美囤妈妈
    职位:软件工程师
    月薪:9000

  • 就业学员

    姓名:陈建伟
    院校:南昌航空大学
    就职:SONY
    职位:嵌入式工程师
    月薪:8000

×
×
  • *真实姓名
  • *联系手机
  • *上课地址
  •    QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一报名服务。

×
  • *真实姓名
  • *联系手机
  • *联系邮箱
  • * QQ号码

温馨提示:请保持手机畅通,咨询老师将为您提供专属的一对一的服务。

本站由 宽敬科技——创新企业的建站运营顾问 提供支持