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

文章/答案/技术大牛

发布

2回答

erlang、tail-recursion

我正在学习函数式编程和Erlang的基础知识，并且我已经实现了阶乘函数的三个版本:使用带保护的递归，使用带模式匹配的递归，以及使用尾递归。执行结果：递归版本： 3> mytimer:execution_time(factorial, fac, [1000000], false).Execution took 1253949667 microseconds ok 带有模式匹配版本的递归： 4> mytimer:execution_time(factorial, fac_pat

浏览 25提问于2019-06-16得票数 2

回答已采纳

1回答

在F#中定义尾递归函数的累加器

f#、tail-recursion

我是F#的初学者，对于尾递归的概念，我仍然不能理解。具体地说，我不知道尾递归是如何工作的，因为既没有任何与累加器相关的值，也没有定义累加器。以下是用于计算阶乘的尾递归函数的一些示例代码// Keep track of both x and an accumulator value (acc) tailRecursiveFactorial (x - 1) (acc

浏览 2提问于2016-08-12得票数 2

1回答

在Scala中，非尾递归递归有多有用？

scala、recursion、tail-recursion

由于非尾递归调用像Java一样使用堆栈框架，所以我会厌倦任何递归，比如超过1000次的递归。因此，我会厌倦在大多数事情上使用它。另外，是否计划在Scala的未来版本中消除这种内存限制？

浏览 2提问于2014-07-08得票数 3

回答已采纳

4回答

尾递归函数总是要避免的吗？

performance、recursion、tail-recursion

如果我没记错的话，尾递归函数总是有一个简单的非递归等价函数。由于递归涉及不必要的函数调用开销，因此最好使用非递归方式。这个假设总是正确的吗？还有没有其他支持/反对尾递归的论点？

浏览 2提问于2010-07-20得票数 4

回答已采纳

2回答

Scala:为什么在Scala中递归比使用循环更好？(仅仅是因为突变？)(尾部回收器与蓄能器)

scala、recursion

但是，在Scala中，递归是否仅仅因为可变性而被认为是遍历循环的呢？简而言之，我有两个问题：，因为尾递归不能用于解决所有循环问题(或者可以吗？)对于某些特定的用例，循环不是更好的解决方案还是唯一的解决方案？，基于尾递归

浏览 2提问于2021-11-26得票数 0

回答已采纳

1回答

length函数的尾递归版本是否在运行时节省了堆栈空间？

functional-programming、f#、tail-recursion、space-efficiency

我被要求将这个F# length函数更改为尾递归函数。let rec len xs = | [] -> 0 match xs with | x::xr -> leni xr r+1;; 与非尾</e

浏览 24提问于2020-11-03得票数 1

1回答

Idris使用尾调用优化吗？

tail-recursion、idris

Scala有尾调用优化( TCO )，如果编译器不能使用TCO优化递归函数，我可以告诉编译器停止。例如，请参见。如果我用一个非常长的List运行它(没有注释)，我就会得到"ERROR:太多递归“，就像预期的那样。使用@tailrec，Scala通过将代码转换为不存在递归错误风险的命令式循环来编译代码。我相信，作为一个命令式循环，它也可能更快。由于来自Scala，我对他没有以尾递归的方式编写它感到惊讶。几个问题：对于不是尾递归的

浏览 2提问于2020-06-30得票数 4

1回答

尾递归Foldr

functional-programming、f#

我想用f#编写一个尾递归文件夹，以利用尾递归优化，并学习更多关于函数编程的知识。 | [x] -> func acc x | x :: xs -

浏览 0提问于2019-07-09得票数 0

回答已采纳

1回答

@tailrec会影响编译器优化吗？

scala、recursion、compiler-optimization、tail-recursion

我不确定的是，注释是否也暗示编译器进行一些优化，还是只在标记不是尾递归的方法时才用于警告？更具体地说，这个注释可能会以任何方式影响性能吗？例如，如果我不添加这个注释，编译器将将一个尾递归函数编译为非尾递归函数？

浏览 3提问于2014-05-08得票数 0

回答已采纳

1回答

硬币换币问题的尾部递推解法

recursion、functional-programming、f#

我试图用尾递归来解决。我遇到的递归解决方案通常如下所示 if amount = 0 thenelse显然是低效和非尾递归的我尝试自己将解决方案尾递归化：

浏览 2提问于2022-02-02得票数 1

1回答

不进行尾部调用优化的尾递归

recursion、optimization、tail-recursion

假设我们有两个版本的递归函数，其中一个是尾递归函数。如果所使用的语言没有尾部调用优化，那么使用函数尾递归有什么好处吗？据我所知，在没有优化的情况下，函数的每个版本(尾部和非尾部)将使用相同数量的堆栈框架(在大多数情况下)。尾递归函数还会更高效吗？

浏览 14提问于2021-03-01得票数 0

1回答

方程Tn=n∑k=1 =k的尾递归函数

python、python-3.x、recursion、tail-recursion

我需要为python中的方程Tn=n∑k=1 =k (和从k=1到n)编写尾递归函数。我能够编写非尾递归 if n == 0: return n + TN(n-1)def TN(n): return 0; return s 这是否算作第一个代码的尾递归函数？

浏览 1提问于2021-11-30得票数 0

回答已采纳

5回答

C++中的尾递归

c++、recursion、g++、tail-recursion

谁能用C++给我演示一个简单的尾递归函数？除了尾递归之外，还有其他类型的递归吗？

浏览 4提问于2010-04-23得票数 67

回答已采纳

1回答

C++：fibonacci的三个递归实现。时间/空间的复杂性是什么？

c++、recursion、time-complexity、tail-recursion、space-complexity

我编写了三个版本的fibonacci序列，我不太确定它们的时间/空间复杂性(以及为什么)： int fibonacci_h(int n) { return 1; return fibonacci_h(n - 1) + fibonacci_h(n - 2);变体2:尾递归 if (n == 1) { } return fibonacci_t(n - 1,

浏览 0提问于2020-10-23得票数 1

3回答

F#中的慢速尾递归

performance、f#、tail-recursion

最初，我将其实现为一个非尾递归函数，如下所示： match start with考虑到尾递归是可取的indicesForStepInternal start [] 然而，当我在Mono下的fsi中使用参数

浏览 1提问于2011-03-28得票数 4

回答已采纳

1回答

Java中的尾递归编程

java、c++、performance、algorithm、recursion

在我做过的一个项目中，我对一个大数据集做了尾递归(很抱歉我没有提供代码，因为我找不到它.)。我意识到了一个明显的性能问题，而不是在C/C++中。然后，我读了几篇关于为什么JVM不支持尾调用优化的文章(现在呢？)而且Java程序员通常使用循环来代替尾递归调用。因此，在Java中尾递归编程在语义上是错误的，还是不管使用哪种语言，它只是一个糟糕的实践呢？int

浏览 2提问于2015-04-08得票数 1

回答已采纳

2回答

流(又称“惰性列表”)和尾递归

ocaml、lazy-evaluation

，它以一个非空(和非惰性)列表l作为参数，并返回对应于在元素l上反复循环的lazylist。我已经实现了几个非尾递归的lcycles版本，例如： let rec inner l' = | [] -> raise基本上，我遇到了这样的问题:惰性计算是通过表单的构造来实现的这意味着我的所有递归调用都发生在

浏览 4提问于2014-11-20得票数 2

1回答

在惰性评估的上下文中，什么时候需要尾递归？

haskell、clojure、functional-programming、scheme、lazy-evaluation

我的理解(这可能是不正确的或不完整的)是，懒惰的评估可以提供尾巴递归的所有优点，并且做得更好。 (* a a)这个函数可以很容易地转换成尾递归函数.然而，如果是这样的话，我们将失去懒惰的优势-评估。实际上，当输入是相当大的列表(或无限)时，这个非尾递归函数需要消耗许多堆栈吗？我不这样认为。那么，是否有充分的理由使

浏览 3提问于2016-01-08得票数 3

3回答

实现尾部呼叫消除的一些好方法是什么？

c、lisp、scheme、tail-call-optimization、trampolines

我知道经典的，但是还有其他很好的实现方法吗？我知道我可以将Scheme堆栈放到堆中，但这仍然不是正确的消除，因为标准说应该支持无限数量的活动尾调用。我也使用了长tail，但到目前为止，我认为它只在非互递归尾调用中才能很好地工作。主要的基于C的方案如何实现适当的尾递归？

浏览 6提问于2011-05-14得票数 21

回答已采纳

1回答

我什么时候用Scala写一个非尾递归函数？

scala、recursion、functional-programming、stack-overflow

由于非尾递归调用像Java一样使用堆栈框架，所以我认为您会非常谨慎地使用它，如果有的话。考虑到这是最重要的工具之一，这似乎是非常严格的限制。什么时候可以使用非尾递归函数？

浏览 3提问于2014-07-07得票数 0

回答已采纳

点击加载更多