7

自然数の階乗 ( より大きいか等しい任意の数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 = ?
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

再帰シーケンスに対する私のお気に入りの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）までの階乗シーケンスのすべての項を生成し、各項は1つの乗算ステップ（n *（n- 1））。一方、フォールドソリューションを使用して最初のn項が必要な場合、各計算は独立して実行され、前の計算の恩恵を受けません。

于 2010-11-06T02:40:35.647 に答える
3

このための再帰関数をどのように宣言しますか?

まず第一に、再帰関数を定義するには、let rec代わりに を使用しますlet(では再帰的に定義letしている関数を参照できないため)。

階乗関数を再帰的に定義するには、階乗関数の標準的な数学的定義を使用するのが最も簡単な (しかし最も効率的ではない) 方法です。

より効率的なアプローチは、これまでに計算された結果を格納する 2 番目の引数を取る末尾再帰ヘルパー関数を定義することです。

于 2010-11-06T00:13:28.497 に答える
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 に答える