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

Question

这些语言不“本地”支持相互递归函数优化，因此我猜它一定是蹦床或.. heh ..作为循环重写)我会错过某些东西吗？

更新:似乎我确实对FSharp撒谎，但我只是没有看到在谷​​歌搜索时相互尾部调用的示例

Answer 1

首先，F# native 支持相互递归函数，因为它可以从.NET IL(MSDN)中可用的tailcall指令中受益。但是，这有点棘手，可能无法在.NET的某些替代实现中使用(例如Compact Frameworks)，因此有时您可能需要手动处理此问题。
总的来说，我认为有两种处理方法:

蹦床-当递归深度过高时引发异常，并实现处理该异常的顶级循环(该异常将携带信息以恢复通话)。除了异常，您还可以简单地返回一个值，该值指定应再次调用该函数。

使用计时器展开-当递归深度太高时，您将创建一个计时器，并为其提供一个回调，该回调将在很短的时间后由计时器调用(计时器将继续递归，但使用的堆栈将是删除)。
使用存储需要完成的工作的全局堆栈可以完成相同的操作。您可以将功能添加到堆栈中，而不是安排计时器。在顶层，程序将从堆栈中选择功能并运行它们。

为了给出第一种技术的特定示例，您可以在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))

这也可以用于相互递归函数。命令性循环将简单地调用存储在 f中的 Call(f)函数，直到产生最终结果的 Done。我认为这可能是实现此目的的最干净的方法。
我敢肯定还有其他复杂的技术可以解决这个问题，但是那是我所知道的(也是我曾经使用过的)两种技术。