如何表达阶乘 n!使用 F# 函数、递归函数还是其他函数？

Question

自然数（大于或等于 0 的任何数字）的阶乘是该数字乘以自身的阶乘减一，其中 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# 中的While 或尾递归，什么时候使用什么？

我主张经常避免迭代和递归，而选择高阶函数。但如果您刚刚开始，也许还不用太担心这个建议。 （但然后参见@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)

Answer 4

我如何为此声明一个递归函数？

首先，要定义递归函数，您可以使用 let rec 而不是 let （因为 let 不允许您引用您递归定义的函数）。

要递归地定义阶乘函数，最简单（但不是最有效）的方法是使用阶乘函数的标准数学定义。

更有效的方法是定义一个尾递归辅助函数，它采用第二个参数来存储迄今为止计算的结果。

Answer 5

我最喜欢的递归序列 F# 解决方案是...无限尾递归序列！：

let factSeq =    
    let rec factSeq m n = 
        seq { let m = m * n
              yield m
              yield! factSeq m (n+1I) }
    seq { yield 1I ; yield 2I ; yield! (factSeq 2I 3I) }

let factTake n = factSeq |> Seq.take n //the first n terms
let fact n = factSeq |> Seq.nth (n-1) //the nth term

我在这里使用 BigIntegers，因为阶乘序列增长得如此之快（继续，尝试第 20,000 项）。

我总体上同意 Brian 的建议，即尽可能在迭代循环或递归循环（尾递归 + 累加器）上使用高阶函数。但我认为在这种情况下，我所展示的无限序列更加灵活，因为它生成阶乘序列的所有项，直到所需的项 (factTake)，并且每个项只需要一个乘法步骤(n*(n-1))。然而，如果您想要使用折叠解决方案的前 n 项，则每个计算都将独立完成，并且不会从之前的计算中受益。

Answer 6

这是一个更简单的实现

let rec bfact (n):bigint = 
    match n with
        | i when i<0 -> bigint.Zero
        | 0 | 1 -> bigint(1)
        | _ -> ( bfact(n-1) * bigint(n) )

并进行测试

bfact(50)

val bfact : n:int -> bigint
val it : bigint =
  30414093201713378043612608166064768844377641568960512000000000000