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

Question

这些语言不支持"原生"的相互递归函数优化,所以我猜它必须是蹦床或者......嘿......重写为循环)我想念一些东西吗？

更新:似乎我对FSharp撒了谎,但我只是没有看到谷歌搜索时相互尾调用的例子

Answer 1

首先,F#本身支持相互递归的函数,因为它可以受益tailcall于.NET IL(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))

这也可以用于相互递归的函数.命令循环将简单地调用f存储的函数,Call(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为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实现都遵循它.