飞度网
转到手机版您现在的位置: 飞度网电脑/网络正文
扫码穿越到手机

[ 字号:    来源:互联网 2008-3-25 17:10:00 ]
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 gcd1(int a,int b) //递归版
  {
   if(a%b==0)
    return b;
   return gcd1(b,a%b);
  }
  long gcd2(int a,int b) //非递归版
  {
    int temp;
    while(b!=0)
    {
     temp=a%b;
     a=b;
     b=temp;
    }
    return a;
  }
思考:将求n!的递归函数非递归化。
6.递归的评价
递归的目的是简化程序设计,使程序易读。
但递归增加了系统开销。 时间上, 执行调用与返回的额外工作要占用CPU时间。空间上,随着每递归一次,栈内存就多占用一截。
相应的非递归函数虽然效率高,但却比较难编程,而且相对来说可读性差。
现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高,程序在更多的场合优先考虑可读而不是高效,所以,鼓励用递归函数实现程序思想。
注意几个要点就是了:
1 是要防止栈溢出,也就是不能递归太深;
2 考虑效率问题, 因为递归的效率相对而言比较低下;
3 算法,设计的递归必须要有适当的递归结束条件, 否则就没完没了了
·分享到:
·看完后,您有任何想法或观点,请立即参与评论
·或者:向飞度网提问 留言 举报 纠错
·更多关于  递归 函数 编程 的内容
 
站内搜索:
·相关评论
  还没有人评论!赶快第一个发表评论吧!
·我来评论
评论内容(必填)

注:评论内容限200字,不支持图片和链接。
您的姓名(选填): 
注:姓名所有人可见,可以填写昵称。
联系方式(选填): 
注:联系方式仅管理员可见,推荐填写电子邮箱。
评价(选填): 
不好
验证码(必填): 
验证码,看不清楚?请点击刷新验证码
版权与免责声明:
1. 凡注明来源为“飞度网”(faydo.com 以下简称为"本站")的所有作品(文章、资料),包括文字与图片,除特殊注明外均可转载,但必须保留版权信息并回链。违反上述声明者,本站将依法追究法律责任。
2. 凡未注明来源的作品(文章、资料),均转载自互联网,本站转载的目的在于传播更多信息,此类作品(文章、资料)并不代表本站观点,本网不承担此类作品侵权行为的直接责任及连带责任。
3. 如因作品内容、版权等需要同本站联系的,请使用页面底部的联系方式。
4. 本站竭力确保所刊载的作品(文章、资料)准确可靠,但不保证该等资料绝对正确可靠;对于任何因资料不确或遗漏又或因根据或依赖本站资料所作决定、行动或不行动而引致的损失或损害,本站概不负责(不论是民事侵权行为责任或合约责任或其他)。
5. 网友评论不代表本站观点。
设为首页 收藏本页 留言与建议 网站地图
©2016 飞度网 版权所有 联系方式:请邮件联系或msn联系。