let rec f n =
match n with
| 0 | 1 | 2 -> 1
| _ -> f (n - 2) + f (n - 3)
如果没有CPS或Memoization，它怎么可能是尾部递归的呢？
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这里有三个组件：
- 得到
i元素的lambda - 组合子在
i上运行递归；以及 - 包装器启动整个运行，然后获取值(如@Tomas代码中的三元组)
您已经要求使用尾部递归代码，实际上有两种方法：像@Tomas那样制作自己的组合子，或者使用现有的Seq.unfold，这当然是尾部递归。我更喜欢第二种方法，因为我可以将整个代码拆分为一组let语句。
@bytebuster的解决方案很好，但他没有解释他是如何创建的，所以只有当你正在解决这个特定的问题时，它才会有所帮助。顺便说一句，你的公式看起来有点像斐波那契(但不完全如此)，它可以在没有任何循环的情况下进行分析计算(即使没有隐藏在Seq.unfold中的循环)。
您从以下功能开始：
let rec f0 n =
match n with
| 0 | 1 | 2 -> 1
| _ -> f0 (n - 2) + f0 (n - 3)
函数为参数n - 2和n - 3调用f0，因此我们需要知道这些值。诀窍是使用动态编程(可以使用记忆来完成)，但由于您不想使用记忆，我们可以手动编写。
我们可以编写f1 n，它返回一个具有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)
这个函数不是tail-recurisve，但它只递归地调用自己一次，这意味着我们可以使用累加器参数模式：
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
我们需要在fc的主体中专门处理参数0和1。对于任何其他输入，我们从最初的三个值(即(f0 0, f0 1, f0 2) = (1, 1, 1))开始，然后循环n次执行给定的递归步骤，直到达到2。递归loop函数是@bytebuster的解决方案使用Seq.unfold实现的。
因此，您的函数有一个尾部递归版本，但这只是因为我们可以简单地将过去的三个值保存在元组中。一般来说，如果计算您需要的先前值的代码执行了更复杂的操作，那么这可能是不可能的。
即使比尾部递归方法更好，您也可以利用矩阵乘法来减少使用O(logn)运算的解决方案的任何重复。我把正确性的证明留给读者练习。
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