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

什么是尾递归?

尾递归是一种特殊的递归形式,它指的是在函数的最后一个操作是递归调用的情况。在尾递归中,递归调用的结果直接作为函数的返回值,而不需要进行任何额外的计算。这种特殊的递归形式可以被编译器优化,以减少栈空间的使用,从而提高程序的性能。

尾递归的实现需要遵循一定的规则,即在递归调用的时候,函数的最后一步操作必须是调用自身,并且不能有任何其他的操作。这种特殊的递归形式可以被编译器优化,以减少栈空间的使用,从而提高程序的性能。

例如,下面的递归函数是一个尾递归函数:

代码语言:txt
复制
function factorial(n, acc = 1) {
  if (n === 0) {
    return acc;
  }
  return factorial(n - 1, n * acc);
}

在这个函数中,递归调用是函数的最后一步操作,并且不需要进行任何额外的计算。因此,这个函数可以被编译器优化为一个循环,从而提高程序的性能。

总之,尾递归是一种特殊的递归形式,它可以被编译器优化,以提高程序的性能。在实现尾递归函数时,需要遵循一定的规则,确保递归调用是函数的最后一步操作,并且不需要进行任何额外的计算。

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

相关·内容

递归怎么一回事?什么递归?

了解数据结构的人都知道, 树结构本身就是用递归定义的,所以解决树相关的问题会优先考虑递归 什么递归?...众所周知, 递归会记录上一个函数的调用状态, 造成大量的资源占用, 为了尽量减少资源的占用, 有了为递归的玩法, 就是把递归操作放到 return 内, 由于return 函数的最后一句, 所以, 就可以减少记录函数体的空间...console.log("普通递归|第",new_num,"次调用") recursion(new_num) } recursion(1) 递归写法 (直接将函数调用return出去 ) /.../ 递归 function recursion2(num){ new_num = num + 1 if (num >= 20000){ return }...console.log("递归|第",new_num,"次调用") return recursion2(new_num) } recursion2(1) 递归节约了递归过程中压栈的内存消耗

2.2K60

2020-1-6-什么递归

递归算法想必大家都已经很熟悉了。递归算法虽然简单,但是容易导致一些性能问题,于是就有了递归这种优化算法。 ---- 首先我们先看看递归算法的性能问题在哪里?...此时程序会将当前上下文压栈,计算出下一个foo的值,然后再出栈和x进行相乘 所以对于foo(3)的调用,整个栈的情况这样的 那么递归呢?...它是指函数的最后一个位置(或者动作)调用自身 我们把上面的方法改一下递归 //C#递归实现 int Foo(int x, int result=1) { if(x==1) {...那么原本需要在内存中记录的信息,从方法参数中传入了 最后的递归调用处位于return,递归的方法只需要返回一个值,而不需要同上一层递归调用的方法再做交互 那么这么有什么好处呢?...目前我知道的python支持的,探索c#之递归编译器优化 - 蘑菇先生 - 博客园文章中表示64位release下会进行尾递归优化 ---- 参考文档: 调用 - 维基百科,自由的百科全书 探索

27620

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

今天,我们来聊聊递归函数。为啥突然想到递归?其实就从电影名字《恐怖游轮》《盗梦空间》想到了。 递归啥? 递归函数大家肯定写过,学校上课的时候,估计最开始的例子就是斐波拉契数列了吧。...递归又是啥? 我得知这个概念,最开始还是因为很多年前一次面试,面试官问我“你知道什么递归吗?”,我以为“伪”递归,难道假的递归???当初我也是懵逼状态(当初面试官忍住没笑也是厉害了 )。...从“”字可看出来即若函数在尾巴的地方递归调用自己。...默认启用递归优化正常计算结果,禁用递归优化则“StackOverflow”。 我们来看看生成的字节码有什么不同。 ? 包含递归优化的字节码,直接 goto 循环。 ?...禁用递归优化的字节码,方法调用。 从上面可以看出,递归优化后,变成循环了(前面的 C++ 类似)。 好了,递归咱们就了解到这里。

1.5K30

递归递归

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

74920

递归递归

#递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数递归的。...百度定义:递归 递归基于函数的调用(调用:返回一个函数并且调用这个函数), 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!...上面就是关于一般递归递归的说明。但是这里存在一个很大的问题,那就是JavaScript的 V8引擎 对递归的优化做的并不好,上面的代码递归还不如一般的递归。...手动优化 既然我们在JavaScript中无法使用递归,使用递归也害怕爆栈,那我们可以自己来一些方法实现相同的效果,例如上面的多个值相加 方案一:修改函数内部,使用循环 // n 正整数 function...} return fn(n -1, total + n) } 这里我们来求一下 n=3 的时候的值,如果使用递归,那么 n = 3 ==> 6 首先来了解一下什么蹦床函数,先来看一段代码 function

98710

调用和递归

function foo () { foo(); } 上面这个操作就叫做递归,但是注意了,这里没有结束条件,递归,所以会报栈溢出错误的,写代码时千万注意给递归添加结束条件。...那么什么递归? 前面我们知道了调用的概念,当一个函数调用自身,就叫做递归。 function foo () { return foo(); } 2....作用 那么递归相比递归而言,有哪些不同呢?...由此可见,调用优化对递归操作意义重大,所以一些函数式编程语言将其写入了语言规格。 避免改写递归函数 递归的实现,往往需要改写递归函数,确保最后一步只调用自身。...通过这个例子,可能看不出为什么要用柯里化,有什么好处,这个我们以后再谈,这里先引出一个概念。

9310

调用和递归

调用 1. 定义 调用是函数式编程中一个很重要的概念,当一个函数执行时的最后一个步骤返回另一个函数的调用,这就叫做调用。...那么什么递归? 前面我们知道了调用的概念,当一个函数调用自身,就叫做递归。 function foo () { return foo(); } 复制代码 2....作用 那么递归相比递归而言,有哪些不同呢?...由此可见,调用优化对递归操作意义重大,所以一些函数式编程语言将其写入了语言规格。 避免改写递归函数 递归的实现,往往需要改写递归函数,确保最后一步只调用自身。...通过这个例子,可能看不出为什么要用柯里化,有什么好处,这个我们以后再谈,这里先引出一个概念。

1.1K10

30秒了解递归递归优化

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

93720

递归递归简析

递归调用是函数最后执行的一步时,该递归函数就是递归。 与之相对的是非递归函数,你先执行递归调用,然后获取递归调用的结果进行计算, 这样你需要先获取每次递归调用的结果,才能获取最后的计算结果。...看下面计算n阶乘的函数,它是一个非递归函数。我们发现cal(n-1)返回的值被cal(n)使用,因此对cal(n-1)的调用并不是cal(n)所做的最后一步。...,编译器优化尾部递归函数的思想很简单,因为递归调用是最后一条statement,所以在当前函数中没有什么可做的,这样没有必要保存当前函数的堆栈结构了。...而非递归函数调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。 一个non-tail递归函数可以优化成递归函数吗?...我们还是以n阶乘为例,其方法再使用一个参数,并在第二个参数中累积阶乘值。当n达到0时,返回累积值。

81730

递归递归总结

1、递归关于递归的概念,我们都不陌生。简单的来说递归就是一个函数直接或间接地调用自身,为直接或间接递归。一般来说,递归需要有边界条件、递归前进段和递归返回段。...递归一般用于解决三类问题: (1)数据的定义递归定义的。(Fibonacci函数,n的阶乘)  (2)问题解法按递归实现。(回溯)  (3)数据的结构形式递归定义的。...2、递归  顾名思义,递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为尾部, 所以根本没有必要去保存任何局部变量....递归极其重要的,不用递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。...从图可以看出,为递归不需要向上返回了,但是需要引入而外的两个空间来保持当前的结果。  为了更好的理解递归的应用,写个程序进行练习。

74610

递归调用优化

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

68510

javascript递归优化

这就是ES6调用优化的关键递归优化的条件代码在严格模式下执行外部函数的返回值,调用函数的调用调用函数返回后,不需要执行额外的逻辑调用函数不是外部函数作用域中自由变量的闭包下面《高程》里面的示例...fib(n - 1) + fib(n - 2)}这是一个非常简单的斐波那契数列的函数,可以看到它不符合递归的条件。...,我们可以用同样的思路,来对其做递归函数优化function foo( n ){ return inner(n, n - 1)}function inner(sum, n){ if(n <= 1)...{ return sum; } return inner(sum * n , n -1);}foo(5);是不是超简单最新版的浏览器已经支持递归可以在计算斐波那契数列的时候,比较递归和非递归的时间...相信你会和我一样,会不由自主的感叹总结JS中的递归函数调用的时候,上下文栈怎么变化的什么递归优化递归优化的条件是什么手动优化一个递归代码

62530

什么递归

看了楼上很多答案,大多偏重于描述递归的现象,而没说明为什么要用递归递归的思想到底是什么。前阵子刚好看了点东西,试着整理下,如有错误之处,请不吝指正。 什么递归? 1....递归静中有动,有去有回。 循环动静如一,有去无回。 举个例子,给你一把钥匙,你站在门前面,问你用这把钥匙能打开几扇门。...递归思想 递归就是有去(递去)有回(归来)。 具体来说,为什么可以”有去“?...什么时候需要用递归? 当有些问题的定义本身就是递归形式的时候,最是适合用递归来解决。 计算机专业的同学最最熟悉的莫过于”树“的定义了[4,5]。...原文地址《什么递归?》

1.5K00

将非递归函数转换为循环或递归形式

1、问题背景在 Python 中,非递归函数可能会导致递归深度限制问题。当递归深度超过限制时,程序将引发 RecursionError 异常。...为了避免这个问题,我们可以将非递归函数转换为循环或递归形式。2、解决方案2.1 循环形式我们可以使用循环来实现非递归函数的功能。...def fact_loop(n): result = 1 while n > 0: result *= n n -= 1 return result2.2 递归形式递归递归函数在最后一步调用自身...递归函数可以很容易地转换为循环形式,因为递归函数的最后一步可以被一个循环来代替。...然而,递归形式更易于理解和维护,因为它是直接递归的。2.4 转换技巧将非递归函数转换为循环或递归形式时,我们可以使用以下技巧:确定递归函数的基线情况,即不需要递归调用的情况。

13410

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

(回溯)    (3)数据的结构形式递归定义的。(二叉树的遍历,图的搜索) 递归的缺点:   递归解题相对常用的算法如普通循环等,运行效率较低。...x n = fact(n-1) x n def fact(n): if n==1: return 1 return n*fact(n-1) 递归指,在函数返回的时候,调用自身本身...遗憾的,大多数编程语言没有针对递归做优化,Python 解释器也没有做优化,所以,即使把上面的fact(n)函数改成递归方式,也会导致栈溢出。...小结 使用递归函数的优点逻辑简单清晰,缺点过深的调用会导致栈溢出。 针对递归优化的语言可以通过递归防止栈溢出。...递归事实上和循环等价的,没有循 环语句的编程语言只能通过递归实现循环。

1.9K70

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

(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 递归一般用于解决三类问题:  (1)数据的定义递归定义的。(n的阶乘)    (2)问题解法按递归实现。...x n = fact(n-1) x n def fact(n): if n==1: return 1 return n*fact(n-1) 递归指,在函数返回的时候,调用自身本身...遗憾的,大多数编程语言没有针对递归做优化,Python 解释器也没有做优化,所以,即使把上面的fact(n)函数改成递归方式,也会导致栈溢出。...小结 使用递归函数的优点逻辑简单清晰,缺点过深的调用会导致栈溢出。 针对递归优化的语言可以通过递归防止栈溢出。...递归事实上和循环等价的,没有循 环语句的编程语言只能通过递归实现循环。

1.5K10

递归的后续探究

大家可以发现其实每次进入ES6兼容表的时候,功能行的第一行就是我们的递归调用(proper tail calls),而它的兼容性也可以看出满片飘红啊。...,但是默认关闭该功能的。...那么为什么V8引擎都已经实现了调用优化,但是默认不开启呢? 3 调用优化默认关闭 V8 blog里有这么一篇文章《ES6, ES7 and beyond》给了我们对应的解释。...3.1 隐式优化问题 首先,由于引擎消除递归隐式的,函数是否符合调用而被消除了递归很难被程序员自己辨别。...为了写出正确的递归方法,你需要首先了解是不是正确的调用形式。同时你可能还需要尝试写不同的递归和普通递归的写法,调整递归参数让能超过调用栈,并不断的进行调试。

1.5K22

递归的后续探究

大家可以发现其实每次进入ES6兼容表的时候,功能行的第一行就是我们的递归调用(proper tail calls),而它的兼容性也可以看出满片飘红啊。...,但是默认关闭该功能的。...那么为什么V8引擎都已经实现了调用优化,但是默认不开启呢? 3 调用优化默认关闭 V8 blog里有这么一篇文章《ES6, ES7 and beyond》给了我们对应的解释。...3.1 隐式优化问题 首先,由于引擎消除递归隐式的,函数是否符合调用而被消除了递归很难被程序员自己辨别。...为了写出正确的递归方法,你需要首先了解是不是正确的调用形式。同时你可能还需要尝试写不同的递归和普通递归的写法,调整递归参数让能超过调用栈,并不断的进行调试。

1K100
领券