2
let rec f n =
    match n with
    | 0 | 1 | 2 -> 1
    | _ -> f (n - 2) + f (n - 3)

如果没有 CPS 或 Memoization,怎么能做到尾递归呢?

4

3 回答 3

4
let f n = Seq.unfold (fun (x, y, z) -> Some(x, (y, z, x + y))) (1I, 1I, 1I)
          |> Seq.nth n

甚至更好:

let lambda (x, y, z) = x, (y, z, x + y)
let combinator = Seq.unfold (lambda >> Some) (1I, 1I, 1I)
let f n = combinator |> Seq.nth n

要了解这里发生了什么,请参阅代码段。它定义了斐波那契算法,和你的非常相似。

UPD这里包含三个组件:

  1. 得到第-个元素的lambda ;i
  2. 运行递归的组合i器;和
  3. 启动整个运行然后获取值的包装器(从三元组中,就像在@Tomas 的代码中一样)。

你已经要求一个尾递归代码,实际上有两种方法:制作你自己的组合器,就像@Tomas 所做的那样,或者利用现有的组合器,Seq.unfold这肯定是尾递归的。我更喜欢第二种方法,因为我可以将整个代码拆分为一组let语句。

于 2012-09-17T19:47:12.447 回答
4

@bytebuster 的解决方案很好,但他没有解释他是如何创建它的,所以它只有在你解决这个特定问题时才会有所帮助。顺便说一句,您的公式看起来有点像斐波那契(但不完全是),它可以在没有任何循环的情况下进行分析计算(即使没有隐藏在 中的循环Seq.unfold)。

您从以下功能开始:

let rec f0 n = 
  match n with 
  | 0 | 1 | 2 -> 1 
  | _ -> f0 (n - 2) + f0 (n - 3) 

该函数需要f0参数n - 2n - 3,因此我们需要知道这些值。诀窍是使用动态编程(可以使用 memoization 完成),但由于您不想使用 memoization,我们可以手动编写。

我们可以编写f1 nwhich 返回一个三元素元组,其当前值和两个过去值值为f0。这意味着f1 n = (f0 (n - 2), f0 (n - 1), f0 n)

let rec f1 n = 
  match n with 
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | 2 -> (1, 1, 1)
  | _ -> 
    // Here we call `f1 (n - 1)` so we get values
    //   f0 (n - 3), f0 (n - 2), f0 (n - 1)
    let fm3, fm2, fm1 = (f1 (n - 1))
    (fm2, fm1, fm2 + fm3)

这个函数不是尾递归,而是只递归调用自己一次,这意味着我们可以使用累加器参数模式:

let f2 n =
  let rec loop (fm3, fm2, fm1) n = 
    match n with 
    | 2 -> (fm3, fm2, fm1)
    | _ -> loop (fm2, fm1, fm2 + fm3) (n - 1)
  match n with
  | 0 -> (0, 0, 1)
  | 1 -> (0, 1, 1)
  | n -> loop (1, 1, 1) n

我们需要处理参数01特别是在fc. 对于任何其他输入,我们从初始三个值(即(f0 0, f0 1, f0 2) = (1, 1, 1))开始,然后循环 n 次执行给定的递归步骤,直到达到 2。递归loop函数是 @bytebuster 的解决方案使用 实现的Seq.unfold

因此,您的函数有一个尾递归版本,但这仅仅是因为我们可以简单地将过去的三个值保留在一个元组中。通常,如果计算您需要哪些先前值的代码执行更复杂的操作,这可能是不可能的。

于 2012-09-17T20:51:14.787 回答
3

甚至比尾递归方法更好,您可以利用矩阵乘法来减少使用 O(log n ) 操作的解决方案的任何递归。我把正确性的证明留给读者作为练习。

module NumericLiteralG =
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne

// these operators keep the inferred types from getting out of hand
let inline ( + ) (x:^a) (y:^a) : ^a = x + y
let inline ( * ) (x:^a) (y:^a) : ^a = x * y

let inline dot (a,b,c) (d,e,f) = a*d+b*e+c*f
let trans ((a,b,c),(d,e,f),(g,h,i)) = (a,d,g),(b,e,h),(c,f,i)
let map f (x,y,z) = f x, f y, f z

type 'a triple = 'a * 'a * 'a
// 3x3 matrix type
type 'a Mat3 = Mat3 of 'a triple triple with
    static member inline ( * )(Mat3 M, Mat3 N) = 
        let N' = trans N
        map (fun x -> map (dot x) N') M
        |> Mat3
    static member inline get_One() = Mat3((1G,0G,0G),(0G,1G,0G),(0G,0G,1G))
    static member (/)(Mat3 M, Mat3 N) = failwith "Needed for pown, but not supported"

let inline f n =
    // use pown to get O(log n) time
    let (Mat3((a,b,c),(_,_,_),(_,_,_))) = pown (Mat3 ((0G,1G,0G),(0G,0G,1G),(1G,1G,0G))) n
    a + b + c

// this will take a while...
let bigResult : bigint = f 1000000
于 2012-09-18T00:18:13.230 回答