首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 网站开发 > Web开发 >

尾递归解决思路

2013-01-08 
尾递归尾递归 - Tail Recursion   尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中

尾递归
尾递归 - Tail Recursion
 
  尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。
 
  也许在C语言中有很多的特例,但编程语言不只有C语言,在函数式语言Erlang中(亦是栈语言),如果想要保持语言的高并发特性,就必须用尾递归来替代传统的递归。
 
  原文的说法是错误的:原文如下:
 
  一种算法, 用于计算机编程技术.
 
  尾递归是针对传统的递归算法而言的, 传统的递归算法在很多时候被视为洪水猛兽. 它的名声狼籍, 好像永远和低效联系在一起.
 
  尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.
 
  以下是具体实例:
 
  线性递归:
 
  long Rescuvie(long n) {
 
  return(n == 1) ? 1 : n * Rescuvie(n - 1);
 
  }
 
  尾递归:
 
  long TailRescuvie(long n, long a) {
 
  return(n == 1) ? a : TailRescuvie(n - 1, a * n);
 
  }
 
  long TailRescuvie(long n) {//封装用的
 
  return(n == 0) ? 1 : TailRescuvie(n, 1);
 
  }
 
  当n = 5时
 
  对于线性递归, 他的递归过程如下:
 
  Rescuvie(5)
 
  {5 * Rescuvie(4)}
 
  {5 * {4 * Rescuvie(3)}}
 
  {5 * {4 * {3 * Rescuvie(2)}}}
 
  {5 * {4 * {3 * {2 * Rescuvie(1)}}}}
 
  {5 * {4 * {3 * {2 * 1}}}}
 
  {5 * {4 * {3 * 2}}}
 
  {5 * {4 * 6}}
 
  {5 * 24}
 
  120
 
  对于尾递归, 他的递归过程如下:
 
  TailRescuvie(5)
 
  TailRescuvie(5, 1)
 
  TailRescuvie(4, 5)
 
  TailRescuvie(3, 20)
 
  TailRescuvie(2, 60)
 
  TailRescuvie(1, 120)
 
  120
 
  很容易看出, 普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程
 
  调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就
 
  不存在这样的问题, 因为他的状态完全由n和a保存.
 
  具体事例2 快速排序算法实施尾递归优化
 
  void quickSort(SqList * list , int low ,int high)
 
  {
 
  int pivot;
 
  while(low<high)
 
  {
 
  pivot=Partition(list,low,high);
 
  quickSort(list, low,high);
 
  //quickSort(list,low,pivot-1); 原递归调用
 
  //quickSort(list,pivot+1,high);
 
  low = pivot+1; /*尾递归*/
 
  }
 
  }
 
  //
 
  首先:尾递归是线性递归的子集,属于线性递归。具体概念请参阅各大高校出版的书籍。作者把概念搞错了
 
  其次,上文所举的第二个例子中在TailRescuvie(n-1, 1)没有计算出来之前,是不能return的。也就是说递归过程和第一个例子是差不多的,根本没有节约资源,甚至更浪费。
 
  其实,编译器会很容易的对尾递归使用跳转语句进行优化,其实是可以return的。
 
  尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题——因为参数里带有前面若干步的运算路径。对于阶乘而言,越深并不意味着越复杂。
 
  从时间和空间效率上看,尾递归和传统递归差不多。递归运算效率低主要是分支巨大,像阶乘这类单分支的递归,效率并不低。递归运算的深度和运算总量大致成指数关系,return多次并不会造成显著的性能损失。
 
  一言以蔽之,传统递归越深,距离目标越近;尾递归越深,距离起点越远。
 
  尾递归适用于运算对当前递归路径有依赖的问题,传统递归适用于运算对更深层递归有依赖的问题。
 
  /**************************************************************************************************/
 
  第二作者对第二个例子的解释上有点不全面,尾递归的效果就是去除了将下层的结果再次返回给上层,需要上层继续计算才得出结果的弊端,如果读者仔细观看第二例子就可以看出,其实每个递归的结果是存储在第二个参数a中的,到最后一次计算的时候,会只返回个a的值,但是因为是递归的原理虽然仍然要返回给上层,依次到顶部才给出结果,但是不需要再做计算了,这点的好处就是每次分配的内存不会因为递归而扩大。


 
  在效率上,两者的确差不多。
      通过以上的简单的论述,我们可以得到这样子的总结,递归是由外向里,距离的目标越来越近。 尾递归是由内向里,越来越近。  总而言之他的算法复杂度是O(n2) 效率确实是差不多啊,这对我们将来写递归算法着实提供了一个新的思路。
[解决办法]
学习了;
技术问题啊为什么不发技术区呢

热点排行