我怎样才能表达一个阶乘n!使用F#函数,递归还是其他？

Question

自然数的阶乘(任何大于或等于的数0)是该数乘以其自身的阶乘减去1,其中阶乘0被定义为1.

例如:

0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!

写这个的另一种方式是乘之间的所有自然数1和n为n!:

5! = 1 * 2 * 3 * 4 * 5

如何用F#中的递归函数表达这个？我应该用递归函数来做吗？

//Factorials!
let factorial n = 
    result = ?

Answer 1

如何,选项1:

let rec factorial n =
    match n with
    | 0 | 1 -> 1
    | _ -> n * factorial(n-1)

如何,选项2(尾递归,编译成循环):

let factorial n =
    let rec loop i acc =
        match i with
        | 0 | 1 -> acc
        | _ -> loop (i-1) (acc * i)
    loop n 1

应该:不,请看我的回答:

虽然在F#中使用Tail Recursion,但在什么时候使用？

我提倡经常避免迭代和递归,而支持高阶函数.但是如果你刚刚开始,也许不要过多担心这个建议.(但后来看看例如@ ChaosPandion的答案,或者例如

let factorial n = [1..n] |> List.fold (*) 1

甚至:

let factorial n = [1..n] |> List.reduce (*) // doesn't require the 2nd parameter

Answer 2

这是另一个例子:

let factorial (num:int) =
    seq { for n in [1..num] -> n }
    |> Seq.reduce (fun acc n -> acc * n)

这个例子可能更清楚一点:

let factorial num =
    [1..num] |> Seq.fold (fun acc n -> acc * n) 1

Answer 3

Brian的答案是最实用的,但这是继续传递风格的解决方案:

let rec factorial n = 
  let rec loopk i k = 
    match i with
    | 0 | 1 -> k i
    | _ -> loopk (i-1) (fun r -> k (i * r))
  in loopk n (fun r -> r)