函数式编程语言中的相互递归函数

Question

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

此 answer 展示了如何在 F# 中定义相互递归函数：

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

这样定义是不是让生成的native machine code或bytecode最终只由一个函数组成，F和G都进行了尾递归优化？这会防止堆栈溢出吗？

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

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

Answer 1

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

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

Answer 2

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

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 有一个尾调用指令（尽管众所周知它很慢）。

函数式编程语言中的相互递归函数

Mutually recursive functions in functional programming languages

f#

haskell

functional-programming

ml

mutual-recursion