F#尾递归及为什么不写while循环？

Question

我正在学习F#（虽然多年来一直使用C＃的函数式方面，但对函数式编程还是新手），其中之一我读到的是F#编译器会识别尾递归并将其编译为while循环（参见http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/）。

我不明白的是，如果它最终会变成while循环，为什么你要编写递归函数呢？特别是考虑到您需要做一些额外的工作使函数变为递归。我有一种感觉，有人可能会说while循环不太功能化，你想要表现得像个功能化的东西，所以你使用递归，但那么编译器为什么要将其转换为while循环呢？

有人能解释一下吗？

- hackerhasid

---

可能是以下问题的重复：While或Tail Recursion在F#中，何时使用？ - nawfal

Answer 1

你可以用相同的观点来看待编译器执行的任何转换。比如，当你使用C#时，你是否经常使用 lambda 表达式或匿名委托？如果编译器只是将它们转换为类和（非匿名）委托，那么为什么不自己使用这些结构呢？同样，你是否经常使用迭代块？如果编译器只是将它们转换为显式实现 IEnumerable<T> 的状态机，那么为什么不自己编写这些代码呢？或者，如果 C# 编译器只是要发出 IL，那么为什么不一开始就用 IL 而不是 C# 呢？等等。

所有这些问题的一个明显答案是，我们想编写能够清晰表达自己的代码。同样地，许多算法本质上是递归的，因此编写递归函数通常会导致对这些算法的清晰表达。特别地，在许多情况下，相对于 while 循环，推断递归算法的终止可能更容易（例如，是否存在明确的基本情况，并且每个递归调用使问题“变小”？）。

然而，由于我们正在编写代码而不是数学论文，所以拥有能够满足某些实际性能标准的软件也很好（例如能够处理大型输入而不会溢出栈）。因此，将尾调用转换为 while 循环的事实对于使用递归算法的形式至关重要。

- kvb

---

也许是因为我仍然更喜欢使用while循环，所以才会问这个问题... - hackerhasid

@statichippo - 是的，如果你发现while循环比递归更容易理解，那么你的问题是相当合理的。然而，随着对函数式编程风格的更多接触，你可能会开始看到递归更适合某些情况。 - kvb

@statichippo - 当然，你会更喜欢写你已经知道的东西，但请考虑一下。在我开始编码之前，我非常习惯不写代码。 - ChaosPandion

+1 针对论证的观点。尽管我认为这使得（部分）正确性和终止更容易进行推理。这一点真的需要更加强调 - 程序员一直在证明程序的属性（通常是在他们的头脑中非正式地证明）。使用归纳法推理函数式程序非常自然。而关于命令式程序的推理则不是。 - petebu

Answer 2

一种递归函数通常是处理某些数据结构（例如树和F#列表）最自然的方式。如果编译器为了性能原因想要将我的自然、直观的代码转换成笨拙的while循环，那没关系，但我为什么要亲自写呢？

此外，Brian在相关问题的回答也与此相关。高阶函数通常可以替代您代码中的循环和递归函数。

- Joel Mueller

---

唯一的问题是，“与某些数据结构最自然的工作方式”通常不是尾递归。因此，我们只能自己将其转换为不太可读的东西。但仍然比while循环好。 :-) - petebu

@petebu - 这就是我提到Brian的帖子的原因。循环和递归函数都不是完美无缺的，这就是为什么拥有map和fold会非常好的原因。 - Joel Mueller

Answer 3

F#执行尾部优化只是一种实现细节，它允许您使用尾递归与while循环相同的效率（且不会出现堆栈溢出）, 但这仅仅是一种"实现细节"。从表面上看，您的算法仍然是递归的，并以这种方式结构化，对于许多算法来说，这是最合理、最功能化的表示方法。

在F#中，一些列表处理内部也是如此 - 内部使用变异以更有效地实现列表操作，但程序员对此并不知情。

关键在于语言如何允许您描述和实现您的算法，而不是使用什么机制使其发生。

- BrokenGlass

---

我认为“尾部优化只是一个实现细节”这种说法是错误的。垃圾回收也不是一个实现细节吧？如果两者中的任何一个关闭，它们不仅会使某些程序运行缓慢，而且还会崩溃并出现堆栈溢出或内存不足异常。知道某些程序仅消耗恒定的栈空间（与堆相比）非常有用。我希望 F# 规范能对此做出一些保证。许多程序都假设存在尾调用消除（更多则假设存在垃圾回收），否则它们将无法运行。 - petebu

@petebu：同意 - 我本想说的是 F# 如何执行尾部优化（即将其转换为 while 循环）并不重要，但它确实是语言规范的一部分，因此某些程序需要。 - BrokenGlass

值得注意的是，F#编译器并不总是将尾递归函数转换为while循环。根据情况，它可能会这样做，也可能会发出.tail IL指令。 - Joel Mueller

您是否有关于规范保证任何关于尾调用的内容的参考？我尝试查找了一下（通过搜索“tail”），但没有找到。 - petebu

@petebu：显然那个说法是错误的，这种优化不是语言的一部分，而是 F# 编译器的属性，我的错 - 应该更仔细地阅读你的第一条评论；-) - BrokenGlass

Answer 4

while循环本质上是一种命令式的循环。大多数情况下，在使用while循环时，你会发现自己写出了如下代码：

let mutable x = ...
...
while someCond do
    ...
    x <- ...

这种模式在命令式语言如C、C++或C#中很常见，但在函数式语言中不太常见。

正如其他帖子所说，一些数据结构，更确切地说是递归数据结构，适合进行递归处理。由于函数式语言中最常见的数据结构是单向链表，因此使用列表和递归函数解决问题是一种常见做法。

另一个支持递归解决方案的论点是递归与归纳之间的紧密关系。使用递归解决方案可以让程序员归纳地思考问题，这有助于解决问题。

同样，正如其他帖子所说，编译器优化尾递归函数（显然，并非所有函数都能从尾调用优化中受益）是一个实现细节，它使您的递归算法在恒定空间内运行。

- Alex