阿克曼终止:根本原因分析

Question

可能不需要太多解释这是什么，它甚至完全按照我想要的方式工作。我真正的问题是项目终止。我已经输出跟踪了我的返回值和嵌套的for循环，我在我的主函数中使用它们来遍历值。我看不出发生这种情况的原因，但是在最后一次通过我的循环后，程序花了大约10分钟的时间才真正终止。虽然我的循环索引是递增的(因为预检查)，但我的Ackermann函数显然没有执行额外的迭代(反正我也不希望它这样做)。另一方面，唯一合乎逻辑的解释是循环没有中断，但如果是这种情况，我的Ackermann函数应该返回一个新的b值。我能想到的另一个原因是垃圾收集需要很长时间来清理数据结构和刷新内存堆。对于那些不熟悉的人来说，这里的思想是将传统上表现为超级麻烦的递归函数实现为迭代函数。递归:

给定正整数m和n:如果m = 0，返回n + 1;如果n = 0，返回Ackermann(m - 1,1);否则返回Ackermann(m - 1, Ackermann(m, n - 1))。因此，迭代的想法是使用堆栈来模拟递归函数调用，这样您就可以使用堆中的内存，而不依赖于调用堆栈的大小，这限制了执行时间。我担心我忽略了我的流程中的一些东西，这些东西导致了计算完成时间和程序到达用户干净退出的时间之间的长时间延迟。

下面是我的代码:

 static void Main(string[] args)
    {
        ulong i, j;
        i = j = 0;
        for (i = 1; i <= 3; i++)
            for (j = 1; j <= 15; j++)
                Console.WriteLine("[{0}] Ackermann({1},{2}) = {3}", DateTime.Now, i, j, Ackermann(i, j));
        Console.WriteLine("Press any key to continue...");
        Console.ReadKey();
    }
    static ulong Ackermann(ulong a, ulong b)
    {
        Stack<ulong> ackStack = new Stack<ulong>();
        ackStack.Push(a);
        while (ackStack.Count > 0)
        {
            a = ackStack.Pop();
            if (a == 0)
                b++;
            else if (b == 0)
            {
                ackStack.Push(--a);
                b = 1;
            }
            else
            {
                ackStack.Push(--a);
                ackStack.Push(++a);
                b--;
            }
        }
        return b;
    }

想法吗?注:这是c#，但这种行为也发生在使用MinGW编译的c++中。

Answer 1

非常感谢Pieter Witvoet!事实证明，我的Writeline中的求值顺序是错误的。只有在改变了它之后，我们才会清楚地看到，这会给整个游戏的整体运行时间增加多少时间!