What's the reason of marking a recursive function as rec in F#?

Question

I am not sure if this is a stupid question but I was going through the tutorial that comes with VS 2010 and there is a function like this:

let rec factorial n = if n=0 then 1 else n * factorial (n-1)

What's the reason of this recursive function to be marked with the rec keyword?

Is it so that the compiler is assured of it being recursive so can do certain optimizations?

What happens if you exclude it?

Answer 1

This might be instructive:

let Main() =
    let f(x) = 
        printfn "original f: %d" x
    let f(x) =
    //let rec f(x) =
        printfn "entered new f: %d" x
        if x > 0 then
            f(x-1)
        else
            printfn "done"
    f(3)
Main()

That prints

entered new f: 3
original f: 2

Now if we comment out let and uncomment let rec, then it prints

entered new f: 3
entered new f: 2
entered new f: 1
entered new f: 0
done

So from that point of view, it's just about name binding; let rec puts the identifier in scope immediately (in this example, shadowing the previous f), whereas let puts the identifier in scope only after its body is defined.

The motivation for the rule does stem from interactions with type inference.

Answer 2

According to Chris Smith (works on the F# team) -

It's to inform the type inference system to allow the function to be used as part of the type inference process. rec allows you to call the function before the type inference system has determined the function's type