3

它是使用递归的强大技术，因为它具有强大的可描述性。尾递归提供比普通递归更强大的计算，因为它将递归变为迭代。Continuation-Passing Style (CPS) 可以将大量循环代码更改为尾递归。Continuation Monad 提供递归语法，但本质上它是尾递归，也就是迭代。100000阶乘应该合理使用Continuation Monad。这是代码。

type ContinuationBuilder() =
   member b.Bind(x, f) = fun k -> x (fun x -> f x k)
   member b.Return x = fun k -> k x
   member b.ReturnFrom x = x
(*
type ContinuationBuilder =
  class
    new : unit -> ContinuationBuilder
    member Bind : x:(('d -> 'e) -> 'f) * f:('d -> 'g -> 'e) -> ('g -> 'f)
    member Return : x:'b -> (('b -> 'c) -> 'c)
    member ReturnFrom : x:'a -> 'a
  end
*)
let cont = ContinuationBuilder()
//val cont : ContinuationBuilder
let fac n =
    let rec loop n =
      cont {
              match n with
              | n when n = 0I -> return 1I   
              | _ -> let! x = fun f -> f n
                     let! y = loop (n - 1I)   
                     return x * y
           }
    loop n (fun x -> x)

let x2 = fac 100000I

出现错误消息：“由于 StackOverflowException 而终止进程。”

使用 ContinuationMonad 的 100000 阶乘有什么问题？

4

2 回答 2

11

您需要在发布模式下编译项目或检查项目属性中的“生成尾调用”选项（或者--tailcalls+如果您通过命令行运行编译器，则使用）。

默认情况下，Debug 模式下不启用尾调用优化。原因是，如果启用了尾调用，您将看不到有关堆栈跟踪的有用信息。因此，默认禁用它们会给您带来更愉快的调试体验（即使在调试模式下，编译器也会优化调用自身的尾递归函数，这可以处理大多数情况）。

于 2013-09-27T03:30:47.457 回答
2

您可能需要将此成员添加到您的 monad 构建器： 

member this.Delay(mk) = fun c -> mk () c
于 2013-09-27T09:29:38.050 回答