首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

尾递归与非尾递归。前者速度慢吗?

尾递归和非尾递归是编程中常用的两种递归方式。

尾递归是指递归函数在调用自身之后不再执行其他操作,而是直接返回递归函数的结果。这意味着在尾递归中,递归调用是函数的最后一条语句。尾递归的优势在于可以通过优化,将递归转化为循环,从而减少内存消耗和提高执行效率。

非尾递归是指递归函数在调用自身之后还需要执行其他操作,比如对递归结果进行处理或者进行其他计算。非尾递归的执行过程中,每次递归调用都会在内存中创建一个新的函数调用帧,导致内存消耗较大。

由于尾递归可以通过优化转化为循环,所以在大多数情况下,尾递归的执行速度要快于非尾递归。尾递归的优化可以避免递归调用帧的堆栈溢出问题,提高了程序的执行效率和性能。

在实际应用中,尾递归通常用于解决需要进行大量递归计算的问题,比如数学中的阶乘、斐波那契数列等。通过使用尾递归,可以有效地减少内存消耗和提高计算效率。

腾讯云相关产品中,无直接与尾递归和非尾递归相关的产品或服务。然而,腾讯云提供了一系列云计算产品和服务,如云服务器、云数据库、云存储等,可以满足各种应用场景的需求。您可以访问腾讯云官方网站(https://cloud.tencent.com/)了解更多关于腾讯云的产品和服务信息。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

递归递归

前言:   本博客前面介绍了不少跟递归的思想相关的例子,比如“汉诺塔”,“八皇后”等。因最近又回忆起“递归”,故本文通过2个例子再跟大伙儿探讨一下递归。。。...什么是递归: 当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是递归递归实例一: 求阶乘!...1:n*fac2(n-1); 31 } 32 /* 33 * 阶乘构造递归,进行编译优化 34 */ 35 public static int fac(int...43 } 44 45 } 46 /* 47 * 回文串递归判断 48 */ 49 public static boolean isPalindrome1...true 递归的意义: 从以上递归的实现过程当中我们可以发现,回归过程中不用做任何操作(运算),这样的一种特性使得在执行尾递归的过程时,能够被某些特定编译器进行优化,减少内存空间的消耗。

75220

递归递归

在介绍递归递归之前,我们来看看递归的定义:程序调用自身的编程技巧称为递归( recursion) 百度对递归的定义:递归 接着,我们再来看看一道题 编写一个函数fn,接收一个或者多个参数,其中一个参数为...#递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是递归的。...百度定义:递归 递归基于函数的调用(调用:返回一个函数并且调用这个函数), 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!...上面就是关于一般递归递归的说明。但是这里存在一个很大的问题,那就是JavaScript的 V8引擎 对递归的优化做的并不好,上面的代码递归还不如一般的递归。...以上就是关于递归递归的说明以及优化,当然,如果你要更好的方案,欢迎在评论区留言。

99110
  • 递归函数转换为循环或递归形式

    1、问题背景在 Python 中,递归函数可能会导致递归深度限制问题。当递归深度超过限制时,程序将引发 RecursionError 异常。...为了避免这个问题,我们可以将递归函数转换为循环或递归形式。2、解决方案2.1 循环形式我们可以使用循环来实现递归函数的功能。...例如,我们可以将以下递归函数:def fact(n): if n == 0: return 1 else: return n * fact(n-1)转换为以下循环形式...然而,递归形式更易于理解和维护,因为它是直接递归的。2.4 转换技巧将递归函数转换为循环或递归形式时,我们可以使用以下技巧:确定递归函数的基线情况,即不需要递归调用的情况。...0.00030803680419921875Tail recursion: 40238726007709377354158490592 0.0002338886260986328从输出中可以看出,循环形式比递归形式和递归形式都要快

    13610

    递归递归简析

    递归调用是函数最后执行的一步时,该递归函数就是递归之相对的是非递归函数,你先执行递归调用,然后获取递归调用的结果进行计算, 这样你需要先获取每次递归调用的结果,才能获取最后的计算结果。...看下面计算n阶乘的函数,它是一个递归函数。我们发现cal(n-1)返回的值被cal(n)使用,因此对cal(n-1)的调用并不是cal(n)所做的最后一步。...cal(6) 6*cal(6-1) 6*5*cal(5-1) 6*5*4*cal(4-1) 6*5*4*3*cal(3-1) 6*5*4*3*2*cal(2-1) 6*5*4*3*2*1 720 通常认为递归函数优于尾部递归函数...而非递归函数调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。 一个non-tail递归函数可以优化成递归函数?...看如下方法: public class TailRecursiveTest { //一个递归函数 public static int calTR(int n, int a) {

    82430

    递归递归总结

    2、递归  顾名思义,递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量....递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。  ...递归是极其重要的,不用递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。...从图可以看出,为递归不需要向上返回了,但是需要引入而外的两个空间来保持当前的结果。  为了更好的理解递归的应用,写个程序进行练习。...采用直接递归递归的方法求解单链表的长度,C语言实现程序如下所示: #include #include typedef struct node {

    76210

    30秒了解递归递归优化

    递归递归优化 之前提到过调用,调用就是函数的最后一步调用另外一个函数。那么递归就是调用自身,递归就是再函数的最后一步调用自身。?...在计算机学里,调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形,即最后一步新调用的返回值直接被当前函数的返回结果。此时,该尾部调用位置被称为位置。...调用中有一种重要而特殊的情形叫做递归。经过适当处理,递归形式的函数的运行效率可以被极大地优化。...---wikipedia 和调用一样,递归因为调用栈中只存在一个调用记录,因此不会像普通递归那样耗费那么多内存。...if (n === 1) return total return f(n - 1, n * total) // ⚡ total 结果和 n 相乘作为参数放入到函数中 } 默认大部分浏览器不会对递归进行优化

    94320

    递归递归区别,Python 实现递归递归

    这样,编译器或者解释器就可以把递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。...要改成递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中: #定义递归函数 def fact(n): return fact_iter(n,1) def fact_iter...遗憾的是,大多数编程语言没有针对递归做优化,Python 解释器也没有做优化,所以,即使把上面的fact(n)函数改成递归方式,也会导致栈溢出。...小结 使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。 针对递归优化的语言可以通过递归防止栈溢出。...递归事实上和循环是等价的,没有循 环语句的编程语言只能通过递归实现循环。

    2K70

    递归递归区别,Python 实现递归递归

    这样,编译器或者解释器就可以把递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。...要改成递归方式,需要多一点代码,主要是要把每一步的乘积传入到递归函数中: #定义递归函数 def fact(n): return fact_iter(n,1) def fact_iter...遗憾的是,大多数编程语言没有针对递归做优化,Python 解释器也没有做优化,所以,即使把上面的fact(n)函数改成递归方式,也会导致栈溢出。...小结 使用递归函数的优点是逻辑简单清晰,缺点是过深的调用会导致栈溢出。 针对递归优化的语言可以通过递归防止栈溢出。...递归事实上和循环是等价的,没有循 环语句的编程语言只能通过递归实现循环。

    1.5K10

    大家都知道递归递归呢?什么又是递归优化?

    递归又是啥? 我得知这个概念,最开始还是因为很多年前一次面试,面试官问我“你知道什么是递归?”,我以为是“伪”递归,难道是假的递归???当初我也是懵逼状态(当初面试官忍住没笑也是厉害了 )。...从“”字可看出来即若函数在尾巴的地方递归调用自己。...默认启用递归优化正常计算结果,禁用递归优化则“StackOverflow”。 我们来看看生成的字节码有什么不同。 ? 包含递归优化的字节码,直接 goto 循环。 ?...禁用递归优化的字节码,方法调用。 从上面可以看出,递归优化后,变成循环了(前面的 C++ 类似)。 好了,递归咱们就了解到这里。...个人看法,我们知道有“递归”这个点就好了,有时候我们写递归就是为了方便,代码可读性好,如果确实是出于性能考虑,我们可以自己用迭代的方式去实现,不依赖于具体的编译器实现。

    1.5K30

    递归调用优化

    之前分享过递归,其中有一个优化就是调用。 先明确调用的概念: 调用(Tail Call)是函数式编程的一个重要概念,就是指某个函数的最后一步是return调用另一个函数。...调用因为是最后一步操作,所以不需要保留之前的栈,也就不需要保存之前的内存,就是递归里面计算阶乘那两个函数。...调用优化其实很大一部分就是递归函数在使用,因为递归函数调用的时候非常耗费内存,可能需要保存成百上千调用栈,很容易内存溢出。如果是递归就只有一个调用栈,能把复杂度O(n)的变成O(1)。...至于怎么改写递归变成可以使用调用就比较复杂了,需要根据不同函数去修改。...而ES6对调用有什么优化?就是函数默认值,在一些场景下,比如阶乘的递归,采用默认值实现递归优化。 (完)

    68810

    javascript递归优化

    这就是ES6调用优化的关键递归优化的条件代码在严格模式下执行外部函数的返回值,是对调用函数的调用调用函数返回后,不需要执行额外的逻辑调用函数不是外部函数作用域中自由变量的闭包下面是《高程》里面的示例...有哪位同仁能够帮我解答一下我这个问题实操一个优化代码下面是一个普通的求斐波那契数列的函数function fib( n ){ if( n < 2){ return n; } return...fib(n - 1) + fib(n - 2)}这是一个非常简单的斐波那契数列的函数,可以看到它不符合递归的条件。...{ if(n <= 1){ return 1; } return n * foo( n - 1 );}foo(5); // 120这个是上面计算阶乘的代码,我们可以用同样的思路,来对其做递归函数优化...,比较递归递归的时间。

    62930

    朋友你听说过递归

    调用和调用 说到递归,那就必然要以斐波那契数列为例子 斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci...递归有着循环同样优秀的计算性能,使用递归可以同时拥有着循环的性能以及递归的数学表达能力。 4....什么鬼,说好的递归优化呢? 5. PTCSTC ES6标准规定了 调用不会创建额外的调用帧。 在严格模式下 调用不会造成调用栈溢出。...STC采用类似于 return continue 的语法来明确标识出要进行尾调用优化,而在调用的场景下使用该语法会抛出语法错误异常。...我们以斐波那契数列为例子讲解了递归的运用方式,并对比了普通递归递归的性能。

    59410

    递归的后续探究

    本文作者:IMWeb 孙世吉 原文出处:IMWeb社区 未经同意,禁止转载 0 前言 去年大致也是这个事件,曾经探索过调用(PTC)相关的内容,并总结了一片文章——朋友你听说过递归。...为了写出正确的递归方法,你需要首先了解是不是正确的调用形式。同时你可能还需要尝试写不同的递归和普通递归的写法,调整递归参数让能超过调用栈,并不断的进行调试。...语义上的调用是针对上述PTC的问题而提出的建议。 STC采用类似于 return continue 的语法来明确标识出要进行尾调用优化,而在调用的场景下使用该语法会抛出语法错误异常。...下使用递归写法的方法依旧出现调用栈溢出的原因在于: 直接原因: 各大浏览器(除了safari)根本就没部署调用优化 根本原因: 调用优化依旧有隐式优化和调用栈丢失的问题 参考资料 朋友你听说过递归...JS中递归STCPTC(hax演讲视频) ES6, ES7 and beyond V8 团队眼中的 ES6、ES7及未来 Tail call optimization in ECMAScript

    1.5K22

    Python中的递归

    递归 递归的原理:当编译器检测到一个函数调用是递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。...---- 换一种说法,递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。...这样,编译器或者解释器就可以把递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。...递归优化 通过实现一个 tail_call_optimized 装饰器,来优化递归。 #!..._getframe().f_back # 调用者的帧 ---- tail_call_optimized实现递归优化的原理: 当递归函数被该装饰器修饰后, 递归调用在装饰器while循环内部进行, 每当产生新的递归调用栈帧时

    1.3K30

    递归的后续探究

    0 前言 去年大致也是这个事件,曾经探索过调用(PTC)相关的内容,并总结了一片文章——朋友你听说过递归。...为了写出正确的递归方法,你需要首先了解是不是正确的调用形式。同时你可能还需要尝试写不同的递归和普通递归的写法,调整递归参数让能超过调用栈,并不断的进行调试。...语义上的调用是针对上述PTC的问题而提出的建议。 STC采用类似于 return continue 的语法来明确标识出要进行尾调用优化,而在调用的场景下使用该语法会抛出语法错误异常。...下使用递归写法的方法依旧出现调用栈溢出的原因在于: 直接原因: 各大浏览器(除了safari)根本就没部署调用优化 根本原因: 调用优化依旧有隐式优化和调用栈丢失的问题 参考资料 朋友你听说过递归...JS中递归STCPTC(hax演讲视频) ES6, ES7 and beyond V8 团队眼中的 ES6、ES7及未来 Tail call optimization in ECMAScript

    1K100
    领券