3

在以下函数中，我尝试通过使用累加器来设置尾递归。但是，我遇到了堆栈溢出异常，这让我相信我设置函数的方式没有正确启用尾递归。

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

我的理解是，使用acc编译器可以让编译器看到没有必要为每个递归调用保留所有堆栈帧，因为它可以将每次传递的结果填充到 acc 并从每个帧返回。显然，我不明白如何正确使用累加器值，因此编译器会进行尾调用。

4

2 回答 2

4

斯蒂芬·斯文森（Stephen Swensen）正确地指出，如果您调试，VS 必须禁用尾调用（否则它不会有堆栈帧跟随调用堆栈）。我知道VS 做到了这一点，但只是忘记了。

在被这个咬住之后，我想知道运行时或编译器是否有可能抛出更好的异常，因为编译器知道你正在调试并且你写了一个递归函数，在我看来它可能会给你一个提示，比如

'Stack Overflow Exception: a recursive function does not 
tail call by default when in debug mode'
于 2010-11-06T02:01:33.480 回答
1

在使用 .NET Framework 4 编译时，这似乎正确地转换为尾调用。请注意，在 Reflector 中，它会将您的函数转换为 a while(true)，正如您期望 F# 中的尾函数所做的那样：

[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);
        }
    }
}

您的问题不是因为缺少尾调用（如果您使用的是 F# 2.0，我不知道结果会是什么）。你究竟是如何使用这个功能的？（输入参数。）一旦我对函数的作用有了更好的了解，我就可以更新我的答案以希望解决它。

于 2010-11-06T01:43:49.757 回答