8

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

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

4

3 回答 3

10

首先，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最终结果。我认为这可能是实现这一点的最干净的方法。

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

于 2010-05-09T19:21:46.393 回答
8

在 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
于 2010-05-10T01:19:01.653 回答
7

只是为了在 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，但在使用尾调用（“发布”模式下的默认值）编译时运行得很好。编译器默认执行尾调用（参见--tailcalls 选项），大多数平台上的 .NET 实现都支持它。

于 2010-05-09T22:03:35.833 回答