开发者

F# using accumulator, still getting stack overflow exception

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开发者_StackOverflow社区 =
    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.


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'


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜