数据结构与算法分析(1):浅析线性递归和尾递归(含java代码)

2016年11月27日 07:59 | 277次浏览 | 分类: 数据结构与算法

线性递归:也即是普通递归,单向递归,线性递归函数的最后一步操作不是递归操作,而是其他的操作。当数据量很大的时候,会造成栈溢出,这是因为,在每次递归调用时,递归函数中的参数,局部变量等都要保存在栈中,如果数据量很大的话,便可能会溢出。


尾递归:也即是线性迭代,尾递归函数的最后一步操作是递归,也即在进行递归之前,把全部的操作先执行完,这样的好处是,不用花费大量的栈空间来保存上次递归中的参数、局部变量等,这是因为上次递归操作结束后,已经将之前的数据计算出来,传递给当前的递归函数,这样上次递归中的局部变量和参数等就会被删除,释放空间,从而不会造成栈溢出。但是很多编译器并没有自动对尾递归优化的功能,也即当编译器判断出当前所执行的操作是递归操作时,不会理会它究竟是线性递归还是尾递归,这样也就不会删除掉之前的局部变量和参数等。另外,尾部递归一般都可转化为循环语句。

一般来说,线性递归和尾递归的时间复杂度相差不大(当然也有例外情况,比如斐波拉契数列,这是因为其线性递归的实现,产生了大量冗余的计算,它的时间复杂度为指数级,而其尾递归的实现只需要线性级别的时间复杂度),但尾递归的空间复杂度比较小(这是在假定尾递归被优化的前提下),线性递归容易理解,尾部递归性能比较好。

以下举出两个例子:

n的阶乘的两种递归实现方式,前者为线性递归,后者为尾递归,后者在计算时,传入的参数a为1,即执行facttsail(n,1),很明显,后者很容易转化为循环语句。

斐波拉契数列的两种递归实现方式:

1、线性递归实现(这种方法很直观,很容易理解,但是效率很低,应尽量避免,不符合递归调用时的合成效益准测)

public static int FibonacciRecursively(int n){  
  if (n < 2)  
      return n;
  else  
      return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
 }

2、尾递归实现,这里需要提供两个累加器:acc1和acc2,调用时acc1赋值0,acc2赋值1

很明显,该方法也很容易转化为循环语句

public static int FibonacciTailRecursively(int n, int acc1, int acc2) {  
  if (n == 0)
       return acc1;  
  else 
       return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);  
}



感觉本站内容不错,读后有收获?小额赞助,鼓励网站分享出更好的教程


上一篇:
^