Option 2: F# Tail calls
One option is to rewrite your method so that you use recursive tail calls. From the prior (Wikipedia) link:
A tail recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. F# and many other functional languages can optimize tail recursive functions; since no extra work is performed after the recursive call, there is no need for the function to remember where it came from, and hence no reason to allocate additional memory on the stack.
F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can recurse indefinitely without consuming stack space.
There is a caveat - Mono does not fully support tail recursive calls - what you should do is to test first in the .Net runtime, and then see if the code will run in Mono.
Here is your sample function re-written using a tail recursive call - it does work in both .NET (using Visual Studio 2010) and Mono (Mono version 3.2.0, F# 3.0):
let f i =
let rec loop acc counter =
// display progress every 10k iterations
let j = counter % 10000
if j = 0 then
printf "Got up to %d\n" counter
stdout.Flush ()
if counter < 1000000000 then
// tail recursive
loop (acc + 1) (counter + 1)
else
acc
loop 0 i
For input value 1:
let result = f 1
printf "result %d\n" result
The output:
Got up to 10000
Got up to 20000
Got up to 30000
...
Got up to 999980000
Got up to 999990000
Got up to 1000000000
result 999999999
For input value 999,999,998:
let result = f 999999998
printf "result %d\n" result
The output:
Got up to 1000000000
result 2
The code above uses two variables to keep track of progress:
acc - the accumulator, which stores the result of the calculation
counter - is simply the number of recursive calls
Why is your sample code not tail recursive?
Paraphrasing the How To Write Tail-Recursive Functions section of the Wikipedia article, we can rewrite this line of your code:
if i = 1000000000 then 0 else 1 + f (i+1)
as
if i = 1000000000 then 0
else
let intermediate = f (i+1) // recursion
let result = 1 + intermediate // additional operations
result
The very definition of tail recursion says that there cannot be additional operations after the recursive call. As we can see in the rewritten version of your code, there are additional operations required to produce the result.
Resources
