将递归函数重写为尾递归函数

文章/答案/技术大牛

发布

1回答

有没有一个使用堆栈帧是不可避免的(不能完全尾递归)的递归函数/算法？

algorithm、recursion、tail-recursion

我正在尝试想出一些递归算法/函数的例子，这些递归算法/函数不能以避免使用大量堆栈内存的方式重写(例如，不能完全尾递归，也不能使用不使用堆栈的循环重写)。这样的函数存在吗？我认为快速排序可能是一个候选，但不确定它是否可以重写为使用单个尾递归函数调用。

浏览 2提问于2013-09-19得票数 0

2回答

将线性递归函数重写为尾递归函数。

algorithm、recursion、pseudocode、tail-recursion

我想知道，如何将“常规”递归函数重写为尾递归函数？有什么策略吗？例如:我有一个简单的函数，我想把它变成一个尾递归函数： if (n % 2 || n > 10) { } return

浏览 0提问于2018-06-15得票数 1

回答已采纳

2回答

python、algorithm、recursion、stack-overflow、tail-recursion

解决方案:我已经为它写了一个递归的解决方案，它输出正确的答案。对于较大的n值，它应命中堆栈溢出。所以我想避免它，并使用尾递归方法重写代码。arr) print(numWays(5, li)) #example n=5 我见过在web上编写阶乘函数作为尾递归函数的例子无法应用该累加器技巧将所需答案作为附加参数存储在函数

浏览 27提问于2020-05-29得票数 0

2回答

尾递归函数的性能

algorithm、scala、performance、recursion、tail-recursion

各种各样的书籍、文章、博客文章表明，将递归函数重写为尾递归函数可以使其更快。毫无疑问，对于像生成Fibonacci数或计算阶乘这样的琐碎情况，它更快。在这种情况下，有一种典型的重写方法--使用“助手函数”和中间结果的附加参数。很好地描述了尾递归函数与非尾递归函数的区别，以及如何将递归

浏览 3提问于2021-10-21得票数 2

回答已采纳

2回答

如果我可以用foldl定义一个函数，它会使它成为尾递归吗？

haskell、functional-programming

在我的函数式编程课程中，我被分配了一个任务，要求我重写几个函数，比如map和filter，使其成为尾递归函数。我还不是100%确定该怎么做，但我知道你可以通过调用foldr和foldl来定义函数。我知道foldl是尾递归的，所以如果我可以用foldl定义filter，它也会变成尾递归吗？

浏览 3提问于2015-10-13得票数 1

1回答

使用尾端递归重写公共函数。

recursion、lisp、racket、tail-recursion

我一直试图修改这段代码，用尾尾递归重写一个“重复”函数，但在我的尝试中遇到了一些问题。它遍历递归的‘n-1’级别，然后在'n‘额外递归调用中将'x’附加到列表中。相反，应该进行递归调用，同时将'x‘附加到列表中。[acc '()]) acc这是我想出的最接近的重写

浏览 9提问于2022-04-06得票数 2

回答已采纳

2回答

在什么情况下是一元计算尾递归？

haskell、monads、tail-recursion

如果我们去糖do我们得到f n acc = getLine >>= \v -> f (n-1) (v : acc)fn acc = (>>=) getLine (\v -> f (n-1) (v : acc)) 因此，我们看到f发生在>>=的第二个参数中，而不是在尾递归位置。显然，在块中将递归调用作为最后一行的不是一个足够的条件，一个函数是尾</em

浏览 3提问于2012-11-14得票数 28

回答已采纳

1回答

Scala有尾调用优化( TCO )，如果编译器不能使用TCO优化递归函数，我可以告诉编译器停止。例如，请参见。但是，我可以把它重写为def allLengths(strs: List[String], acc: List[Int] = Nil): List[Int] = strs match使用@tailrec，Scala通过将代码转换为不存在递归错误风险的命令式循环来编译代码。我相信，作为一个命令式循环，它也可能更快。由于来自Scala，我对他

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

1回答

Google应用程序脚本(GAS)是否支持正确的尾调用或尾调用优化？

javascript、google-apps-script、google-sheets、v8

我想知道花时间为Google脚本做是否值得。据推测， (适当的)尾调用优化来自规范。但是，有一些认为V8实际上没有实现它：正确的尾调用:在尾位置调用的函数重用当前堆栈帧，从而防止创建额外的堆栈帧，从而导致空间

浏览 15提问于2022-04-14得票数 0

回答已采纳

1回答

为什么尽管是尾部递归的，但是叶酸似乎是有害的呢？

haskell、recursion、fold

我一直认为，从性能上看，尾递归函数比非尾递归函数要好。因此，列表中的计数项可能实现如下：count [] = 0但是这个函数不是尾递归函数，因此不能尽可能地执行b_count b (x:xs) = _count (b + 1) xs c

浏览 1提问于2018-01-22得票数 6

回答已采纳

2回答

简单的尾递归函数和循环一样有效吗？

c#、clr

有时，我发现自己在编写尾递归函数。我一直在到处寻找，我发现在.NET框架中有尾递归，但我不确定在哪些情况下我可以使用尾递归，在哪些情况下我不能有效地使用尾递归。会不会发生什么奇特的事情，算法会递归运行吗？最重要的是，我应该将其重写为迭代式的吗？

浏览 1提问于2012-12-19得票数 20

回答已采纳

1回答

嵌套递归调用--这是尾递归吗？

algorithm、recursion、tail-recursion

我认为我理解尾递归函数的教科书定义:函数调用后不执行任何计算的函数。因此，尾递归函数的内存效率将更高，因为每次调用只需要一个记录，而不需要每个记录(就像正常递归中的那样)。我将提供一个例子： if(x > 100): else:我

浏览 4提问于2020-01-16得票数 0

回答已采纳

1回答

SML:尾递归本地辅助函数

sml、tail-recursion

我正在尝试使用尾递归本地辅助函数作为赋值的一部分来重写代码。all_except_option是一个返回类型为fn : string * string list -> string list option的函数 x :: all_except_option' str_list SOME (all_except_option' str_list)下面的函数</

浏览 0提问于2013-01-29得票数 0

2回答

卷积函数可以用尾递归形式写成吗？

recursion、functional-programming、dynamic-programming、tail-recursion、continuation-passing

我有一个函数，我想用尾递归的形式来写。该函数通过滚动k边模n次数来计算获得s之和的方法的数量。我在上看到了这个函数的数学解。其内容如下：我在R中的参考递归实现是： if (k_sum < n_times || k_sumsum_ways(n_times - 1, k_sum - j, s_side) return(sum(sigma_values)

浏览 6提问于2017-01-11得票数 3

回答已采纳

2回答

如何将此函数重写为尾递归函数？

clojure、tail-recursion

我正在读“小阴谋家”一书，我在Clojure中实现了函数，如何将这个函数重写为Clojure中的尾递归函数？

浏览 9提问于2022-10-21得票数 0

回答已采纳

1回答

短路算子与尾递归

recursion、compiler-optimization、tail-recursion、short-circuiting

all_true(bools+1, len-1);此函数可以以更明显的尾递归方式重写，如下所示： if (len我的问题是:如果一个编译器足够聪明地将第二个优化为尾递归调用，那么在"&&“短路的情况下，期望它以同样的方式对第一个进行优化是否合理呢？显然，如果使用非短路操作符，这将不是尾递归的，因为这两个表达式都会在运算符应用

浏览 2提问于2011-12-15得票数 6

回答已采纳

7回答

所有递归函数都可以重写为尾递归吗？

algorithm、recursion、tail-recursion

可能重复：那么，是否有可能使用尾递归来实现所有递归函数呢？像DFS这样的东西怎么样?

浏览 0提问于2012-07-30得票数 20

回答已采纳

1回答

理解以下是否为尾递归函数的问题

recursion、tail-recursion

引用 return x-10; return foo(foo(x+11));基于上面的定义，在我看来foo应该是一个尾递归函数，因为它的递归调用是过程的最终操作，但在我曾经读过的某个地方，它不是<e

浏览 6提问于2015-05-25得票数 1

5回答

每一个递归都能被转换成迭代吗？

c、recursion、iteration

每个递归函数都可以转换为迭代吗？递归函数应该具有什么特性才能使用迭代来实现它？ pathCounter++; }} 扩展:在不实现自己的堆栈的情况下，可以将上述递归函数转

浏览 10提问于2012-07-29得票数 4

1回答

关于两个函数的堆栈溢出

lisp、clisp

所以我对lisp很陌生，我对我遇到的问题感到很困惑： (if (>= x 1) 1))(defun sum (x) 1堆栈溢出在(sum 10000)，我使用clisp。

浏览 0提问于2014-03-19得票数 1

回答已采纳

点击加载更多

有没有一个使用堆栈帧是不可避免的(不能完全尾递归)的递归函数/算法？

将线性递归函数重写为尾递归函数。