0

单个递归函数可以对其应用尾递归优化，以防止堆栈溢出，但是相互递归函数呢？

这个答案显示了如何在 F# 中定义相互递归函数：

let rec F() = 
    G()
and G() =
    F()

是否以这种方式定义，以便生成的本机机器代码或字节码最终仅包含一个函数，并且对 F 和 G 都应用了尾递归优化？这会防止堆栈溢出吗？

对于相互递归函数，尾调用算法如何工作？

另一方面，Haskell 不需要这样的语法。是因为 Haskell 的懒惰评估吗？或者正如@augustss 所建议的那样，Haskell 编译器是否也在做与上述相同的事情？

4

2 回答 2

5

函数式语言通常会进行所谓的适当尾调用优化，这完全独立于递归。任何尾调用都被优化为跳转，无论是递归调用、对先前定义的函数的调用、部分应用的函数，甚至是对一等函数的调用。例如：

g x = let y = 2*x in abs x  -- tail call
add x = (+) x  -- tail call
apply f x = f x  -- tail call

F# 应该能够完成所有这些工作，因为 CLR 有一个尾调用指令（尽管已知它很慢）。

于 2015-02-28T08:40:11.460 回答
1

由于 F# 属于 ML 家族，我想这是一件相当简单的事情：plainlet根本不是递归的，相互递归的函数需要通过let rec. 这确实在一定程度上简化了编译器的分析。在 Haskell 中，编译器最终将代码本身分解为相似的块，以支持类型推断和执行优化。可以说，ML 方式更具可预测性。我不认为这两种方法本质上都更好。

你提到了惰性评估，我怀疑这确实有助于在每种语言中平衡某种程度。在 ML 中，递归定义的值几乎必须是一个函数，而在 Haskell 中，任何类型的值都可以递归定义。

于 2015-02-28T06:11:44.603 回答