Memoizing尾调用优化递归函数

Question

可能重复：
Combine memoization and tail-recursion

所以下面是代码我写，尾调用使用可变累积优化

let rec counter init count = 
    if init = 1 then count + 1 else 
    match init with 
    | Even value -> (counter (value/2) (1 + count)) 
    | Odd value -> (counter ((3 * value) + 1) (count+1)) 

let SeqBuilder (initval:int) : int = 
    counter initval 0 

我该如何记忆？当我试图记忆它时遇到的问题是，递归调用必须去memoize对象，所以你必须有一个...递归对象？

还是更简单一些，我只是缺乏经验？

Answer 1

F＃允许您定义一个递归值（像你提到的递归对象），所以如果你有memoize2功能做记忆化（取的两个参数的函数 - 使其与您counter兼容），那么你可以写：

let rec counter = memoize2 (fun init count -> 
    if init = 1 then count + 1 else 
    match init with 
    | Even value -> (counter (value/2) (1 + count)) 
    | Odd value -> (counter ((3 * value) + 1) (count+1))) 

像这样的递归引用可能是危险的，所以F＃插入一些运行时检查。它也给出了一个警告FS0040来通知你这件事，但在这种情况下，递归是正确的（如果递归引用在初始化过程中被访问过，则会发生问题 - 这里我们稍后使用它，当函数已经被声明时，很好）。您可以通过添加#nowarn "40"来禁用该警告。