Comment puis-je exprimer un n factoriel! avec une fonction F #, récursive ou non?

Question

Une factorielle d'un nombre naturel (n'importe quel nombre supérieur ou égal à 0) est ce nombre multiplié par la factorielle de lui-même moins un, où la factorielle de 0 est définie comme 1.

Par exemple:

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

Une autre façon d'écrire consiste à multiplier tous les nombres naturels entre 1 et n pour n!:

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

Comment puis-je exprimer avec une fonction récursive en F # ? Et devrait Je le fais avec une fonction récursive?

//Factorials! 
let factorial n = 
    result = ? 

Answer 1

Comment, l'option 1:

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

Comment, l'option 2 (queue récursive, compilé dans une boucle):

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

Si: non, voir ma réponse à:

While or Tail Recursion in F#, what to use when?

où je préconise souvent éviter à la fois l'itération et la récursivité en faveur des fonctions d'ordre supérieur. Mais si vous commencez tout juste, ne vous inquiétez peut-être pas trop de ce conseil. (Mais voir par exemple @ réponse de ChaosPandion, ou par exemple

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

---

Ou encore:

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

Answer 2

Comment puis-je déclarer une fonction récursive pour cette

d'abord? de tous, pour définir une fonction récursive, vous utiliseriez let rec au lieu de let (beca utilisez let ne vous permet pas de faire référence à la fonction que vous définissez récursivement).

Pour définir la fonction factorielle récursivement, la méthode la plus simple (mais pas la plus efficace) consiste à utiliser la définition mathématique standard de la fonction factorielle.

Une approche plus efficace consisterait à définir une fonction auxiliaire récursive en queue prenant un deuxième argument qui stocke le résultat calculé jusqu'à présent.

Answer 3

Voici un autre exemple:

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

Cet exemple pourrait être un peu plus clair:

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

Answer 4

réponses de Brian sont les plus pratiques, mais voici la solution dans le style qui passe de continuation:

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 5

Ma solution F # préférée pour les séquences récursives est ... infinie, retour-de-queue ive séquences !:

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 

J'utilise BigIntegers ici puisque la séquence factoriel croît si vite (allez-y, essayez le terme 20.000e). Je suis généralement d'accord avec le conseil de Brian d'utiliser des fonctions d'ordre supérieur par rapport aux boucles itératives ou aux boucles récursives (récursion de la queue + accumulateur) autant que possible. Mais je pense que dans ce cas, une séquence infinie comme je l'ai montré est plus flexible puisqu'elle produit tous les termes de la séquence factorielle jusqu'au terme désiré (factTake), et chaque terme ne nécessite qu'un seul pas de multiplication (n * (n -1)). Considérant que, si vous vouliez les n premiers termes en utilisant une solution de pli, chaque calcul serait fait indépendamment et ne bénéficierait pas du calcul précédent.

Answer 6

Voici une implémentation plus simple

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

Et pour tester

bfact(50) 

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