记忆F#中的尾调用优化的递归函数 [英] Memoizing tail call optimized recursive functions in F#

问题描述

可能重复:
组合备忘录和尾递归

Possible Duplicate:
Combine memoization and tail-recursion

因此，以下是我编写的代码，使用累积变量对尾调用进行了优化

So the following is the code that I wrote, tail call optimized using an accumulation variable

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

我该如何记住?当我尝试记忆时遇到的问题是，递归调用必须转到该记忆对象，所以您必须有一个...递归对象?

How do I memoize this? the problem I ran into when I tried to memoize it is that the recursive call has to go to the memoize object, so you have to have a...recursive object?

还是更简单，我只是没有经验?

Or is it a lot simpler and I am just inexperienced?

推荐答案

F#允许您定义递归值(例如您提到的递归对象)，因此如果您具有memoize2函数，做记忆(带有两个参数的功能-使它与您的counter兼容)，然后您可以编写:

F# allows you to define a recursive value (like recursive object that you mentioned), so if you have memoize2 function to do the memoization (taking a function of two arguments - to make it compatible with your counter), then you can write:

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"来禁用警告.

Recursive references like this can be dangerous, so F# inserts some runtime checks. It also gives a warning FS0040 to notify you about this, but in this case the recursion is correct (a problem could occur if the recursive reference was accessed during initialization - here we use it only later, when the function is already declared, so everything is fine). You can disable the warning by adding #nowarn "40".

这篇关于记忆F#中的尾调用优化的递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！