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?

Maybe duplicate? http://stackoverflow.com/questions/900585/why-are-functions-in-ocaml-f-not-recursive-by-default — elmattic, Sep 17 '10 at 23:09
Possible duplicate of [Why are functions in Ocaml/F# not recursive by default?](https://stackoverflow.com/questions/900585/why-are-functions-in-ocaml-f-not-recursive-by-default) — Alex M., Sep 07 '18 at 14:49

score 31 · Accepted Answer · answered Sep 18 '10 at 07:54

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.

That's a very educative example on binding, shadowing, and scoping :-). — Édgar Sánchez Gordón, Sep 18 '10 at 20:19
+1 but "The motivation for the rule does stem from interactions with type inference" could do with some clarification. — J D, Dec 30 '10 at 02:00

score 12 · Answer 2 · answered Sep 17 '10 at 23:09

12

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

answered Sep 17 '10 at 23:09

Russ Cam

124,184
33
204
266

Otherwise the type inference system would go into an infinite loop? If that's why, then makes sense. – Joan Venge Sep 17 '10 at 23:13
1

Really, is that all? Taking this point in, I wonder if I can write a recursive function *without* `rec` if I explicitly define all of the types... experiment time! – sholsapp Sep 17 '10 at 23:27
4

Without `rec`, you'd also have to define the function itself beforehand. But you'd have to define the function first, since it wouldn't be available within its own scope. But first, you'd have to define the function. After you defined the function. Once the function was defined. Which would require defining the function. *ad infinitum.* – cHao Sep 17 '10 at 23:31
@cHao: Yeah this is what I was thinking as not doable. – Joan Venge Sep 17 '10 at 23:39
2

Baiscally it allows you to use it at the same time it is defined – BlackTigerX Sep 17 '10 at 23:52

score 8 · Answer 3 · answered Sep 17 '10 at 23:03

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

score 6 · Answer 4 · answered Dec 30 '10 at 02:04

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

To tell the compiler that any uses of the function name inside the body of the function refer to it recursively rather than to a previously-defined value of the same name.

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

No.

What happens if you exclude it?

You lose the ability for the function you are defining to refer to itself in its function body and gain the ability to refer to previously-defined values of the same name.

You've written several answers and comments on this topic across SO, but I find this one to be the most illuminating. Its haiku-like conciseness allows its content to be immediately grasped, a thing which is partly lost in your more verbose posts. — Alex M., Sep 07 '18 at 14:48

score 5 · Answer 5 · answered Sep 17 '10 at 23:17

5

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).

answered Sep 17 '10 at 23:17

Chuck

234,037
30
302
389

Thanks Chuck. What do you mean by bindings? Is it like scoping? – Joan Venge Sep 17 '10 at 23:20
3

@Joan Venge: a binding is basically a variable name and its associated value. In this case it means that you cannot use the function inside of itself, because it only gets bound to the name *after* the `let`. `let rec` makes the names that are being bound available *inside* the binding expression itself. – Jörg W Mittag Sep 17 '10 at 23:53

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

5 Answers5

Linked