前两天发了一篇关于递归的博客,感谢一位博主提出了尾递归的概念,之前还没了解过尾递归,这两天稍微弄了一下尾递归,发现了尾递归的确实相对于传统的树形递归有着效率上的优势,不过通过比对之后我还是发现了一个问题,不知道哪位博主能帮帮忙?
在上一篇博客中就已经说到递归调用时,系统会记录递归链,使用树形递归计算连整数的和时,数字过大就会溢出栈空间。所以通过前两天一位博主提出的尾递归的概念,我也进行了一些资料的搜索,百度百科上面关于尾递归有这样一个例子:
线性递归:
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
看下来之后大概也了解了尾递归的过程,不过把这段代码放到eclipse里面去运行,经过反复测试之后,发现它比之前所写的树形结构的递归更容易溢出栈空间,很明显,它记录的递归链比线性递归的还要长,但这是为什么呢?希望一些大牛们来指出。
不过,通过尾递归的思想,我已经解决了之前所提到的用递归求解fibonacci数的效率问题,算法如下:
/**
* 尾递归求fibonacci数
*/
long Tailfibonacci(int n){
if(n<=2){
return 1;
}
return Tailfibonacci(n,1,1);
}
long Tailfibonacci(int n,int a,int b){
int c=a+b;
if(n<=3){
return c;
}
a=b;
b=c;
return Tailfibonacci(n-1,a,b);
}
这个算法求解fibonacci数的效率是线性的,感谢博主们的帮助。
相关推荐
这几天看到几篇关于尾递归的文章,之前对尾递归没有多大概念,所以回头研究了一下尾递归。 尾递归的概念尾递归(Tail Recursion)的概念是递归概念的一个子集。对于普通的递归,由于必须要记住递归的调用堆栈,...
这是一个关于尾递归和Cooper变换的文档,有兴趣的人可以下载。
/*int f(int n,int a1,int a2) { if(n) return a1; else return f(n - 1, a2, a1 + a2); }*/
本文实例讲述了JS尾递归的实现方法及代码优化技巧。分享给大家供大家参考,具体如下: 在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的。 对于特定的递归函数,一般我们都是手动对它们...
本文实例讲述了es6函数之尾递归用法。分享给大家供大家参考,具体如下: 函数调用自身,称为递归,如果尾调用自身,就称为尾递归。 递归非常耗费内存。因为需要同时保存成千上百个调用帧,很容易发生“栈溢出”错误...
本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列,非常具有实用价值,需要的朋友可以参考下
尾递归简介 尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归。 递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出。而尾...
尾递归与Continuation递归与尾递归关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度: 代码如下:public class ...
关于递归相信大家已经熟悉的不能再熟悉了,所以笔者在这里就不多费口舌,不懂的读者们可以在博客园中找到很多与之相关的博客。下面我们直接切入正题,开始介绍尾递归。 尾递归 普通递归和尾递归如果仅仅只是从代码的...
本文实例讲述了Python递归及尾递归优化操作。分享给大家供大家参考,具体如下: 1、递归介绍 递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且...
主要介绍了C#中的尾递归与Continuation详解,本文讲解了递归与尾递归、尾递归与Continuation、Continuation的改进等内容,需要的朋友可以参考下
在C语言的环境下,运用尾递归将整数转换为二进制数 在C语言的环境下,运用尾递归将整数转换为二进制数
fibonacci数列的各种解法,递归、存储优化的递归、自下而上的递归(迭代法)、尾递归。其中分析内容请移步我的博客、
因为随着递归的深入,之前的一些变量需要分配堆栈来保存。 尾递归相对传统递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一...
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在...
主要介绍了Java8使用lambda实现Java的尾递归的相关资料,需要的朋友可以参考下