F# using accumulator, still getting stack overflow exception

Question

In the following function, I've attempted to set up tail recursion via the usage of an accumulator. However, I'm getting stack overflow exceptions which leads me to believe that the way I'm setting up my function is't enabling tail recursion correctly.

//F# attempting to make a tail recursive call via accumulator
let rec calc acc startNum =
 match startNum with
 | d when d = 1 -> List.rev (d::acc)
 | e when e%2 = 0 -> calc (e::acc) (e/2)
 | _ -> calc (startNum::acc) (startNum * 3 + 1)

It is my understanding that using the acc would allow the compiler to see that there is no need to keep all the stack frames around for every recursive call, since it can stuff the result of each pass in acc and return from each frame. There is obviously something I don't understand about how to use the accumulator value correctly so the compiler does tail calls.

• Marcelo Cantos: If you are doing this in Mono, you are out of luck, since Mono doesn't optimise tail-calls yet, even for F#.
• TechNeilogy: I don't have a Mono system to check it one, but looking at the reflected output under Windows .NET shows that the tailcall optimization has been made for that version.
• Stephen Swensen: Your function is properly tail-recursive. If you are using Visual Studio and compiling in Debug mode, tail recursion will be turned off by default (to enable a better debugging experience): stackoverflow.com/questions/1416415/…
• Brian: @Marcelo, this will run fine on Mono, the F# compiler turns tail recursion into loops, and does not require any platform support. The more general case of tail calls (to arbitrary functions, other than the current one) is different.

Answer 1

Stephen Swensen was correct in noting as a comment to the question that if you debug, VS has to disable the tail calls (else it wouldn't have the stack frames to follow the call stack). I knew that VS did this but just plain forgot.

After getting bit by this one, I wonder if it possible for the runtime or compiler to throw a better exception since the compiler knows both that you are debugging and you wrote a recursive function, it seems to me that it might be possible for it to give you a hint such as

'Stack Overflow Exception: a recursive function does not 
tail call by default when in debug mode'

• J D: "I knew that VS did this but just plain forgot". Yes, I find it really annoying.

Answer 2

It does appear that this is properly getting converted into a tail call when compiling with .NET Framework 4. Notice that in Reflector it translates your function into a while(true) as you'd expect the tail functionality in F# to do:

[CompilationArgumentCounts(new int[] { 1, 1 })]
public static FSharpList<int> calc(FSharpList<int> acc, int startNum)
{
 while (true)
 {
 int num = startNum;
 switch (num)
 {
 case 1:
 {
 int d = num;
 return ListModule.Reverse<int>(FSharpList<int>.Cons(d, acc));
 }
 }
 int e = num;
 if ((e % 2) == 0)
 {
 int e = num;
 startNum = e / 2;
 acc = FSharpList<int>.Cons(e, acc);
 }
 else
 {
 startNum = (startNum * 3) + 1;
 acc = FSharpList<int>.Cons(startNum, acc);
 }
 }
}

Your issue isn't stemming from the lack it being a tail call (if you are using F# 2.0 I don't know what the results will be). How exactly are you using this function? (Input parameters.) Once I get a better idea of what the function does I can update my answer to hopefully solve it.