F#/Scala 中优化相互递归的标准方法是什么？

Question

这些语言不支持“本机”相互递归函数优化，所以我猜它一定是蹦床或..呵呵..重写为循环）我错过了什么吗？

更新：看来我确实对 FSharp 撒了谎，但我只是在谷歌搜索时没有看到相互尾部调用的例子

Answer 1

首先，F# 本身支持相互递归函数，因为它可以受益于 .NET IL 中提供的 tailcall 指令 (MSDN）。然而，这有点棘手，并且可能不适用于 .NET 的某些替代实现（例如 Compact Frameworks），因此您有时可能需要手动处理这个问题。

一般来说，我认为有几种方法可以处理它：

• Trampoline - 当递归深度太高时抛出异常并实现处理异常的顶级循环（异常将携带恢复呼叫的信息）。除了异常之外，您还可以简单地返回一个值，指定应再次调用该函数。

• 使用计时器展开 - 当递归深度太高时，您创建一个计时器并给它一个回调，计时器将在很短的时间后调用该回调（计时器将继续递归） ，但使用的堆栈将被丢弃）。

  使用存储需要完成的工作的全局堆栈可以完成同样的事情。您可以将函数添加到堆栈中，而不是调度计时器。在顶层，程序将从堆栈中选择函数并运行它们。

为了给出第一种技术的具体示例，在 F# 中您可以这样写：

type Result<´T> =
  | Done of ´T
  | Call of (unit -> ´T)

let rec factorial acc n = 
  if n = 0 then Done acc
  else Call(fun () -> factorial (acc * n) (n + 1))

这也可以用于相互递归函数。命令式循环将简单地调用存储在 Call(f) 中的 f 函数，直到生成具有最终结果的 Done。我认为这可能是实现这一点的最干净的方法。

我确信还有其他复杂的技术可以解决这个问题，但这些是我所知道的（并且我使用过的）。

Answer 2

在 Scala 2.8 上，scala.util.control.TailCalls：

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(true) 
  else 
    tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) 
    done(false) 
  else 
    tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result

Answer 3

只是为了在 Bing for F# 相互递归时方便使用代码：

let rec isOdd x =
    if x = 1 then true else isEven (x-1)
and isEven x = 
    if x = 0 then true else isOdd (x-1)

printfn "%A" (isEven 10000000)

如果您在没有尾部调用的情况下进行编译（“调试”模式下的默认设置，该模式保留堆栈以便于调试），这将导致 StackOverflow，但在使用尾部调用编译时运行得很好（默认为“Release”模式）。编译器默认执行尾部调用（请参阅--tailcalls 选项） ，并且大多数平台上的 .NET 实现都遵循它。