let rec f n =
match n with
| 0 | 1 | 2 -> 1
| _ -> f (n - 2) + f (n - 3)
如果没有 CPS 或 Memoization,怎么能做到尾递归呢?
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
i
器;和你已经要求一个尾递归代码,实际上有两种方法:制作你自己的组合器,就像@Tomas 所做的那样,或者利用现有的组合器,Seq.unfold
这肯定是尾递归的。我更喜欢第二种方法,因为我可以将整个代码拆分为一组let
语句。
@bytebuster 的解决方案很好,但他没有解释他是如何创建它的,所以它只有在你解决这个特定问题时才会有所帮助。顺便说一句,您的公式看起来有点像斐波那契(但不完全是),它可以在没有任何循环的情况下进行分析计算(即使没有隐藏在 中的循环Seq.unfold
)。
您从以下功能开始:
let rec f0 n =
match n with
| 0 | 1 | 2 -> 1
| _ -> f0 (n - 2) + f0 (n - 3)
该函数需要f0
参数n - 2
和n - 3
,因此我们需要知道这些值。诀窍是使用动态编程(可以使用 memoization 完成),但由于您不想使用 memoization,我们可以手动编写。
我们可以编写f1 n
which 返回一个三元素元组,其当前值和两个过去值值为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
我们需要处理参数0
,1
特别是在fc
. 对于任何其他输入,我们从初始三个值(即(f0 0, f0 1, f0 2) = (1, 1, 1)
)开始,然后循环 n 次执行给定的递归步骤,直到达到 2。递归loop
函数是 @bytebuster 的解决方案使用 实现的Seq.unfold
。
因此,您的函数有一个尾递归版本,但这仅仅是因为我们可以简单地将过去的三个值保留在一个元组中。通常,如果计算您需要哪些先前值的代码执行更复杂的操作,这可能是不可能的。
甚至比尾递归方法更好,您可以利用矩阵乘法来减少使用 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