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