`
cq520
  • 浏览: 166622 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

关于尾递归的一些疑惑

阅读更多

      前两天发了一篇关于递归的博客,感谢一位博主提出了尾递归的概念,之前还没了解过尾递归,这两天稍微弄了一下尾递归,发现了尾递归的确实相对于传统的树形递归有着效率上的优势,不过通过比对之后我还是发现了一个问题,不知道哪位博主能帮帮忙?

       在上一篇博客中就已经说到递归调用时,系统会记录递归链,使用树形递归计算连整数的和时,数字过大就会溢出栈空间。所以通过前两天一位博主提出的尾递归的概念,我也进行了一些资料的搜索,百度百科上面关于尾递归有这样一个例子:

线性递归:

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数的效率是线性的,感谢博主们的帮助。

2
5
分享到:
评论

相关推荐

    C#中的尾递归与Continuation详解

    关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度: 代码如下: public class Node {  public Node(int value,...

    关于尾递归和Cooper变换

    ### 关于尾递归 尾递归是一种特殊的递归形式,在这种形式中,递归调用是函数中的最后一个操作。也就是说,递归调用之后没有其他待执行的操作。这种递归形式的重要之处在于它可以被优化为迭代过程,从而避免了传统...

    关于尾递归的使用详解

    **尾递归详解** 尾递归(Tail Recursion)是一种特殊的递归形式,它是递归概念的一个子集,主要用于优化递归算法。普通递归在执行过程中会不断积累调用栈,随着递归深度的增加,内存消耗也会急剧增大,可能导致栈...

    Fibonacci数列的四种解法:递归、存储优化的递归、自下而上的递归(迭代法)、尾递归

    fibonacci数列的各种解法,递归、存储优化的递归、自下而上的递归(迭代法)、尾递归。其中分析内容请移步我的博客、

    尾递归.cpp

    /*int f(int n,int a1,int a2) { if(n) return a1; else return f(n - 1, a2, a1 + a2); }*/

    详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    但Python标准解释器并未对尾递归进行优化,所以尾递归在Python中的效果并不明显。 3. **循环**: 循环是最有效的方法,如 `Fib_circle` 函数所示。通过循环,我们可以避免递归带来的额外开销,只需线性时间复杂度...

    尾递归详细总结分析

    一些语言如Scheme和Scala等,默认对尾递归进行优化,使其等同于循环,不会增加调用栈。在C#中,虽然没有原生支持尾递归优化,但开发者可以通过手动管理累加器或使用迭代的方式来模拟尾递归优化。 尾递归的优势在于...

    C.rar_instead5ss_尾递归_整数转为二进制数

    尾递归是一种优化的递归形式,它可以被编译器或解释器有效地处理,以减少内存栈的需求。在这个场景中,我们将深入探讨如何使用尾递归来实现整数到二进制的转换。 首先,让我们了解什么是尾递归。尾递归是指在一个...

    Java8使用lambda实现Java的尾递归

    Java8 使用 lambda 实现 Java 的尾递归 Java8 使用 lambda 实现 Java 的尾递归是 Java8 中一个重要的知识点。本篇文章主要介绍了 Java8 使用 lambda 实现 Java 的尾递归的相关资料,需要的朋友可以参考下。 什么是...

    es6函数之尾递归用法实例分析

    本文实例讲述了es6函数之尾递归用法。分享给大家供大家参考,具体如下: 函数调用自身,称为递归,如果尾调用自身,就称为尾递归。 递归非常耗费内存。因为需要同时保存成千上百个调用帧,很容易发生“栈溢出”错误...

    JS尾递归的实现方法及代码优化技巧

    JavaScript中的尾递归是一种特殊的递归形式,它在递归调用出现在函数体末尾时出现,且没有其他操作紧跟其后。这种形式的递归理论上可以被优化,因为其不会增加额外的堆栈帧,使得无限递归变为可能而不会导致堆栈溢出...

    Python中使用装饰器来优化尾递归的示例

    尾递归简介 尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归。 递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出。而尾...

    C#函数式编程中的递归调用之尾递归详解

    关于递归相信大家已经熟悉的不能再熟悉了,所以笔者在这里就不多费口舌,不懂的读者们可以在博客园中找到很多与之相关的博客。下面我们直接切入正题,开始介绍尾递归。 尾递归 普通递归和尾递归如果仅仅只是从代码的...

    Python递归及尾递归优化操作实例分析

    Python递归是编程中一种强大的技术,它允许函数在解决问题时自我调用。递归的基本原理是通过将复杂问题分解为相同或相似的子问题来解决。...在实际编程中,理解递归和尾递归的概念对于编写高效和优雅的代码至关重要。

    Python尾递归优化实现代码及原理详解

    因为随着递归的深入,之前的一些变量需要分配堆栈来保存。 尾递归相对传统递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一...

Global site tag (gtag.js) - Google Analytics