f# - 如何让这个简单的递归关系(差分方程)尾递归呢？

Question

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

没有CPS，没有Memoization，尾递归怎么实现？

Answer 1

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

要了解这里发生了什么，请参阅 this片段。它定义了斐波那契算法，和你的很相似。

UPD 这里包含三个组件:

1. 获取第 i 个元素的 lambda；
2. 在i 上运行递归的组合器；和
3. wrapper 启动整个运行然后获取值(从三元组中获取值，就像在@Tomas 的代码中一样)。

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