CODEWITHSUNDEEP
.netf#functional-programming
user1385230
user1385230

Reputation:

Why doesn't infinite recursion hit a stack overflow exception in F#?

I know this is somewhat the reverse of the issue people are having when they ask about a stack overflow issue, but if I create a function and call it as follows, I never receive any errors, and the application simply grinds up a core of my CPU until I force-quit it:

let rec recursionTest x =
    recursionTest x

recursionTest 1

Of course I can change this out so it actually does something like this:

let rec recursionTest (x: uint64) =
    recursionTest (x + 1UL)

recursionTest 0UL

This way I can occasionally put a breakpoint in my code and see the value of x is going up rather quickly, but it still doesn't complain. Does F# not mind infinite recursion?

Upvotes: 6

Views: 885

Answers (3)

Pubby
Pubby

Reputation: 53067

This is an example of tail call optimization and so the compiler is optimizing it into a simple loop. See this: https://devblogs.microsoft.com/fsharpteam/tail-calls-in-f/

Try something like this:

let rec recursionTest x =
    recursionTest x + recursionTest (x * 2)

Upvotes: 2

t0yv0
t0yv0

Reputation: 4724

In general, F# emits the tailcall instruction that .NET honors:

http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.tailcall(v=vs.95).aspx

In some specific simple cases, like yours, F# rewrites programs that use recursion into equivalent programs using loops.

Upvotes: 3

Lee
Lee

Reputation: 144176

Your recursionTest function is tail recursive, which means all recursive calls occurs in the 'tail position' i.e. as the last action in the function. This means the F# compiler does not need to allocate a new stack frame for recursive calls, so no stack overflow occurs.

Tail recursion is a specific case of tail call, the tail call being to itself rather than some other function.

Upvotes: 8

Related Questions