问题标签 [tail-recursion]

我有一些可变的 scala 代码，我正试图以更实用的方式重写它们。这是一段相当复杂的代码，所以我试图将其重构。我的第一个想法是这样的：

这对我来说似乎根本不起作用，因为我的代码中仍然混合有副作用。我的第二个想法是这样的：

这对我来说似乎是一个更好的解决方案，因为至少我已经将我的函数值生成代码与可变值处理代码隔离开来。但是，这大大降低了内存效率，因为我正在生成一个我并不真正需要存储的大列表。

这让我有 3 个选择：

1. 写一个尾递归函数，咬紧牙关重构值处理代码
2. 使用惰性列表。这不是一个内存敏感的应用程序（虽然它是性能敏感的）
3. 想出一个新的方法。

我想我真正想要的是一个懒惰的评估序列，我可以在处理完这些值后丢弃它们。有什么建议么？

我刚开始使用 VS2010 学习 F#，下面是我第一次尝试生成斐波那契数列。我想做的是建立一个所有小于 400 的数字的列表。

我的第一个问题是，在最后一条语句中，我在最后一行收到一条错误消息“在表达式中的此点或之前的结构构造不完整”。我不明白我在这里做错了什么。

虽然这似乎是一种以相当有效的方式（来自 c++/C# 程序员）构建列表的明显方法，但从我对 f# 知之甚少的情况来看，这似乎不是执行程序的正确方法. 我的这种感觉是正确的吗？

像这样的简单附加函数（在 F# 中）：

当 s 变大时会崩溃，因为该函数不是尾递归的。我注意到 F# 的标准 append 函数不会因大列表而崩溃，因此必须以不同的方式实现它。所以我想知道：追加的尾递归定义是什么样的？我想出了这样的事情：

这有效，但看起来很奇怪。有更优雅的定义吗？

我想知道为什么

不会导致堆栈溢出错误。前奏中的 ++ 似乎是直截了当且非尾递归的：

编辑：最初，我认为这个问题与前奏中定义 ++ 的方式有关，特别是与重写规则有关，因此问题继续如下。讨论告诉我，事实并非如此。我现在认为一些惰性求值效果会导致代码在没有堆栈溢出的情况下运行，但我不太清楚如何。

所以就这样，它应该会遇到堆栈溢出，对吧？所以我认为这可能与遵循 ++ 定义的 ghc 魔法有关：

{-# RULES "++" [~1] forall xs ys。xs ++ ys = 增加 (\cn -> foldr cn xs) ys #-}

*这有助于避免堆栈溢出吗？有人可以为这段代码中发生的事情提供一些提示吗？**

最近在学习F#。我尝试以不同的方式解决问题。像这样：

我认为V2和V3的结果应该是一样的。但是，我得到以下结果：

为什么V2和V3的结果不同？

我写了一些代码来学习 F#。这是一个例子：

我很高兴它可以正常工作！

我完全是递归的初学者

递归是一件美妙的事情。

我认为findPrimes效率不高。

如果可能的话，有人帮我将 findPrimes 重构为尾递归吗？

顺便说一句，有没有更有效的方法来找到前 n 个素数？

我想看看.tailIL 指令，但是我一直在编写的使用尾调用的简单递归函数显然已优化为循环。我实际上是在猜测这一点，因为我不完全确定 Reflector 中的循环是什么样的。不过，我绝对看不到任何.tail操作码。我在项目的属性中检查了“生成尾调用”。我还尝试了 Reflector 中的调试和发布版本。

我使用的代码来自Chris Smith 的 Programming F#，第 190 页：

谁能建议一些确实会生成的简单 F# 代码.tail？

这是我在 Clojure 中对 Erathosthene 筛的实现（基于关于流的 SICP 课程）：

现在，当我取前 100 个素数时，一切正常：

但是，如果我尝试取前 1000 个素数，程序会因为堆栈溢出而中断。我想知道是否有可能以某种方式将函数筛更改为尾递归，并且仍然保留算法的“流”？

有什么帮助？？？

类型的值如何：

有一个引用自身以功能方式生成的值吗？

在以下 Python 代码中，结果值应等于 x，以获得合适的 Tree 定义：

编辑：显然需要更多解释。我正在尝试学习 F# 和函数式编程，所以我选择实现我之前用其他语言编写的封面树。这里相关的是，每个级别的点都是下一个级别的点的子集。该结构在概念上达到水平-无穷大。

在命令式语言中，节点有一个包含自身的子节点列表。我知道这可以在 F# 中强制完成。不，考虑到覆盖树算法，它不会创建无限循环。

先来点背景。我目前正在学习一些关于单子解析器组合器的东西。当我尝试从本文（第 16-17 页）转移“chainl1”函数时，我想出了这个解决方案：

我用一些大的输入测试了这个函数，得到了一个 StackOverflowException。现在我想知道，是否可以重写一个递归函数，它使用一些计算表达式，以某种方式使用尾递归？

当我扩展计算表达式时，我看不出它通常是如何实现的。