代码之家  ›  专栏  ›  技术社区  ›  Kevin Won

使用累加器,仍然出现堆栈溢出异常

  •  3
  • Kevin Won  · 技术社区  · 15 年前

    在下面的函数中,我试图通过使用累加器来设置尾部递归。但是,我得到了堆栈溢出异常,这使我相信我设置函数的方式是不能正确地启用尾部递归。

    //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中并从每个帧返回。很明显,对于如何正确使用累加器值,以便编译器执行尾部调用,我有些不明白的地方。

    2 回复  |  直到 10 年前
        1
  •  3
  •   Kevin Won    15 年前

    Stephen Swensen在注释中指出,如果调试,VS必须禁用尾部调用(否则它将没有堆栈帧跟随调用堆栈),这是正确的。我 知道

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

    'Stack Overflow Exception: a recursive function does not 
    tail call by default when in debug mode'
    
        2
  •  1
  •   knocte    8 年前

    在使用.NETFramework4编译时,这似乎已正确转换为尾部调用。注意,在Reflector中,它将您的函数转换为 while(true) 正如您所期望的,F中的tail功能可以做到:

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