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

Question

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

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

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

是否以这种方式定义,以便生成的本机机器代码或字节码最终只包含一个函数,尾递归优化应用于F和G？这会阻止堆栈溢出吗？

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

另一方面,Haskell不需要这样的语法.是因为Haskell的懒惰评估？或者@augustss建议,Haskell编译器是否也像上面那样做？

Answer 1

函数式语言通常执行所谓的正确尾部调用优化,它完全独立于递归.任何尾调用都被优化为跳转,无论是递归调用,对先前定义的函数的调用,部分应用的函数,还是对第一类函数的调用.例如:

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有一个尾调用指令(尽管已知它很慢).