7

自然数的阶乘（任何大于或等于 的数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 = ?
4

6 回答 6

28

如何，选项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
于 2010-11-06T00:12:04.497 回答
8

这是另一个例子：

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
于 2010-11-06T00:21:24.070 回答
5

布赖恩的答案是最实用的，但这里是延续传递风格的解决方案：

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)
于 2010-11-06T00:30:18.040 回答
3

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

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

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

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

于 2010-11-06T00:13:28.497 回答
3

我最喜欢的递归序列 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 项，则每个计算都将独立完成，并且不会从先前的计算中受益。

于 2010-11-06T02:40:35.647 回答
0

这是一个更简单的实现

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
于 2016-04-13T13:41:42.420 回答