CODEWITHSUNDEEP
recursionf#tail-recursionfactorial
delete
delete

Reputation:

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

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 = ?

Upvotes: 9

Views: 10300

Answers (6)

merrais
merrais

Reputation: 401

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

Upvotes: 1

Brian
Brian

Reputation: 118895

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

Upvotes: 31

Stephen Swensen
Stephen Swensen

Reputation: 22307

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.

Upvotes: 3

Steve Rowe
Steve Rowe

Reputation: 19413

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)

Upvotes: 5

ChaosPandion
ChaosPandion

Reputation: 78282

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

Upvotes: 9

sepp2k
sepp2k

Reputation: 370417

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.

Upvotes: 3

Related Questions