How can I express a factorial n! with an F# function, recursive or otherwise?

Question

A factorial of a natural number (any number greater or equal than 0) is that number multiplied by the factorial of itself minus one, where the factorial of 0 is defined as 1.

For example:

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

Another way of writing this is to multiply all natural numbers between 1 and n for n!:

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

How can I express this with a recursive function in F#? And should I do it with a recursive function?

//Factorials!
let factorial n = 
    result = ?

Answer 1

How, option 1:

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

How, option 2 (tail recursive, compiled into a loop):

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

Should: no, see my answer to:

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

where I advocate often avoiding both iteration and recursion in favor of higher-order functions. But if you're just getting started, maybe don't worry too much about that advice yet. (But then see e.g. @ChaosPandion's answer, or e.g.

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

---

Or even:

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

Answer 2

Here is another example:

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

This example might be a bit clearer:

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

Answer 3

Brian's answers are most practical, but here is the solution in continuation passing style:

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

How would I declare a recursive function for this?

First of all, to define a recursive function, you'd use let rec instead of let (because let does not allow you to refer to the function you're defining recursively).

To define the factorial function recursively, the easiest (but not most efficient) way would be to use the standard mathematical definition of the factorial function.

A more efficient approach would be to define a tail-recursive helper function taking a second argument which stores the result calculated thus far.

Answer 5

My favorite F# solution to recursive sequences is... infinite, tail-recursive sequences!:

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

I'm using BigIntegers here since the factorial sequence grows so quickly (go ahead, try the 20,000th term).

I generally agree with Brian's advice to use higher-order functions over iterative loops or recursive loops (tail-recursion + accumulator) whenever possible. But I think in this case, an infinite sequence as I've shown is more flexible since it produces all terms of the factorial sequence up to the desired term (factTake), and each term only requires only one multiplication step (n*(n-1)). Whereas, if you wanted the first n terms using a fold solution, each calculation would be done independently and wouldn't benefit from the previous calculation.

Answer 6

Here is a simpler implementation

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

And to test

bfact(50)

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