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

首先,F#本身支持相互递归的函数,因为它可以受益于.NET IL( MSDN)中提供的tailcall指令.但是,这有点棘手,可能不适用于.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并得到最终结果.我认为这可能是实现这一目标的最简洁方法.

我确信还有其他复杂的技术来处理这个问题,但那些是我所知道的(我用过的).