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

According to the MSDN, it's only a syntatic necessity:

Recursive functions, functions that call themselves, are identified explicitly in the F# language. This makes the identifer that is being defined available in the scope of the function.

http://msdn.microsoft.com/en-us/library/dd233232.aspx

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

Answer 3

It's necessary so that the function can be recursive. A non-rec function only knows about bindings at the place where it's defined, not after (so it doesn't know about itself).

Answer 4

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.