今天一直在研究尾递归,看了些博文,记下点笔记,供以后复习用
线性递归:也即是普通递归,单向递归,线性递归函数的最后一步操作不是递归操作,而是其他的操作。当数据量很大的时候,会造成栈溢出,这是因为,在每次递归调用时,递归函数中的参数,局部变量等都要保存在栈中,如果数据量很大的话,便可能会溢出。
尾递归:也即是线性迭代,尾递归函数的最后一步操作是递归,也即在进行递归之前,把全部的操作先执行完,这样的好处是,不用花费大量的栈空间来保存上次递归中的参数、局部变量等,这是因为上次递归操作结束后,已经将之前的数据计算出来,传递给当前的递归函数,这样上次递归中的局部变量和参数等就会被删除,释放空间,从而不会造成栈溢出。但是很多编译器并没有自动对尾递归优化的功能,也即当编译器判断出当前所执行的操作是递归操作时,不会理会它究竟是线性递归还是尾递归,这样也就不会删除掉之前的局部变量和参数等。另外,尾部递归一般都可转化为循环语句。
一般来说,线性递归和尾递归的时间复杂度相差不大(当然也有例外情况,比如斐波拉契数列,这是因为其线性递归的实现,产生了大量冗余的计算,它的时间复杂度为指数级,而其尾递归的实现只需要线性级别的时间复杂度),但尾递归的空间复杂度比较小(这是在假定尾递归被优化的前提下),线性递归容易理解,尾部递归性能比较好。
以下举出两个例子:
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);
}
分享到:
相关推荐
浅析C语言递归算法
非线性递归数列化归为线性递归数列的常见技巧[整理].pdf
浅析C语言递归算法.pdf
%92数列化归为线性递归数列的常见技巧.pdf
本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列,非常具有实用价值,需要的朋友可以参考下
为了解决可验证秘密共享中存在的问题,基于非齐次线性递归序列和环上椭圆曲线,构造出一个可验证的秘密共享方案。在方案中用环上的椭圆曲线和单调陷门函数对参与者进行验证。方案中的非齐次递归序列在密钥分发时性能...
江苏省金湖县实验中学高中数学 奥赛辅导 线性递归数列
本文描述了线性递归序列与多项式环的一个非常有意思的内在联系,给出了线性递归序列与一元多项式环的理想 之间的一个对应关系。
递归, 作为 语言最经典的算法之一 , 是一种非常有用的 程序设计方法。 虽然用递归算法编写的程序结构清晰, 具有很 好的可读性, 还往往使某些看起来不易解决的问题变得容易解 决。 但在递归函数中, 由于存在着自调用...
提出了线性齐次DataLog 逻辑程序的概念, ...该算法利用带有约束条件的递归调用方法, 将 线性DataLog 程序求解问题变换成齐次程序求解问题。算法简单, 易于实现, 可应用于任何线性Data2 Log 程序的求解。</p>
使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用自己,这种问题显然可以用递归解决,递归的...
用C语言开发的递归和非递归二分查找算法,具体内容详见代码
DNS递归和迭代
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
浅析PHP递归函数返回值使用方法,需要的朋友可以参考一下
2.一般操作 3.相通的参数设置 2.一般操作 3.相通的参数设置
普通递归和尾递归如果仅仅只是从代码的角度出发来看,我们可能发现不了他的特点,所以笔者利用两张堆栈上的图来展示具体的差距在哪,首先我们来看看普通的递归调用的情况,如下图1.1所示: 假设这里执行的函数是...
/*int f(int n,int a1,int a2) { if(n) return a1; else return f(n - 1, a2, a1 + a2); }*/
递归和非递归方式计算Ackerman函数。非递归方法用堆栈实现。代码内部有详细的注释说明,比较适于学习。
NULL 博文链接:https://touch-2011.iteye.com/blog/1113143