如何防止我的Ackerman函数溢出堆栈？

Question

有没有办法保持我的Ackerman函数不会创建一个堆栈溢流是对相对较小的数字,即(4,2).这是错误

{无法计算表达式,因为当前线程处于堆栈溢出状态.}

private void  Button1Click(object sender, EventArgs e)
        {
            var t = Ackermann(4,2);
            label1.Text += string.Format(": {0}", t);
            label1.Visible = true;
        }

        int Ackermann(uint m, uint n)
        {
            if (m == 0)
                return  (int) (n+1);
            if (m > 0 && n == 0)
                return Ackermann(m - 1, 1);
            if (m > 0 && n > 0)
                return Ackermann(m - 1, (uint)Ackermann(m, n - 1));
            else
            {
                return -1;
            }
        }

Answer 1

要避免的最好方法StackOverflowException是不使用堆栈.

让我们摆脱负面情况,因为当我们打电话时它没有意义uint.或者,如果我们在考虑其他可能性之前将负测试作为方法中的第一件事,那么此后的内容也将起作用:

首先,我们需要一艘更大的船:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        if (m == 0)
            return  n+1;
        if (n == 0)
            return Ackermann(m - 1, 1);
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

现在,成功至少在数学上是可行的.现在,n == 0案例是一个足够简单的尾调用.让我们手工消除它.我们会使用goto它,因为它是暂时的,所以我们不必担心速龙或Dijkstra:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
    restart:
        if (m == 0)
            return  n+1;
        if (n == 0)
        {
            m--;
            n = 1;
            goto restart;
        }
        else
            return Ackermann(m - 1, Ackermann(m, n - 1));
    }

这已经需要更长的时间来吹掉堆栈,但是它会吹掉它.看一下这个表格,请注意,m永远不会通过递归调用的返回来设置,n有时候是.

扩展这一点,我们可以将其转换为迭代形式,而只需处理跟踪先前的值m,以及我们将以递归形式返回的位置,我们以n迭代形式分配.一旦我们用完m等待处理的s,我们将返回当前值n:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                stack.Push(m - 1);
                n = 1;
            }
            else
            {
                stack.Push(m - 1);
                stack.Push(m);
                --n;
            }
        }
        return n;
    }

在这一点上,我们已经回答了OP的问题.这将花费很长时间来运行,但它将返回所尝试的值(m = 4,n = 2).它永远不会抛出StackOverflowException,但它最终会耗尽内存上面的某些价值观m和n.

作为进一步的优化,我们可以跳过向堆栈添加一个值,只是在之后立即弹出:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

这对堆栈没有帮助,也没有对堆有意义的帮助,但是考虑到循环的数量,这个东西会用大值来做,我们可以剃掉的每一点都是值得的.

goto在保持优化的同时消除是留给读者的练习:)

顺便说一下,我对测试这个太不耐烦了,所以当m小于3时,我做了一个使用Ackerman函数的已知属性的作弊表:

    public static BigInteger Ackermann(BigInteger m, BigInteger n)
    {
        Stack<BigInteger> stack = new Stack<BigInteger>();
        stack.Push(m);
        while(stack.Count != 0)
        {
            m = stack.Pop();
        skipStack:
            if(m == 0)
                n = n + 1;
            else if(m == 1)
                n = n + 2;
            else if(m == 2)
                n = n * 2 + 3;
            else if(n == 0)
            {
                --m;
                n = 1;
                goto skipStack;
            }
            else
            {
                stack.Push(m - 1);
                --n;
                goto skipStack;
            }
        }
        return n;
    }

在这个版本中,我能得到的结果true对于Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3后一点在第二(黑白,发布版本,在酷睿i7运行).鉴于非作弊版本在返回这些值的正确结果时是一致的m,我认为这是前一版本正确性的合理证据,但我会让它继续运行并看到.

编辑:当然,我并不是真的希望以前版本能够在任何合理的时间范围内返回,但我认为无论如何我都会让它继续运行,看看它的内存使用情况如何.6个小时后,它的坐姿远低于40MiB.我很高兴虽然显然不切实际,如果在真机上有足够的时间,它确实会回归.

编辑:显然,有人认为,Stack<T>达到2³¹项目的内部限制也算作"堆栈溢出".如果我们必须,我们也可以处理:

public class OverflowlessStack <T>
{
    internal sealed class SinglyLinkedNode
    {
        //Larger the better, but we want to be low enough
        //to demonstrate the case where we overflow a node
        //and hence create another.
        private const int ArraySize = 2048;
        T [] _array;
        int _size;
        public SinglyLinkedNode Next;
        public SinglyLinkedNode()
        {
            _array = new T[ArraySize];
        }
        public bool IsEmpty{ get{return _size == 0;} }
        public SinglyLinkedNode Push(T item)
        {
            if(_size == ArraySize - 1)
            {
                SinglyLinkedNode n = new SinglyLinkedNode();
                n.Next = this;
                n.Push(item);
                return n;
            }
            _array [_size++] = item;
            return this;
        }
        public T Pop()
        {
            return _array[--_size];
        }
    }
    private SinglyLinkedNode _head = new SinglyLinkedNode();

    public T Pop ()
    {
        T ret = _head.Pop();
        if(_head.IsEmpty && _head.Next != null)
            _head = _head.Next;
        return ret;
    }
    public void Push (T item)
    {
        _head = _head.Push(item);
    }
    public bool IsEmpty
    {
        get { return _head.Next == null && _head.IsEmpty; }
    }
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
    var stack = new OverflowlessStack<BigInteger>();
    stack.Push(m);
    while(!stack.IsEmpty)
    {
        m = stack.Pop();
    skipStack:
        if(m == 0)
            n = n + 1;
        else if(m == 1)
            n = n + 2;
        else if(m == 2)
            n = n * 2 + 3;
        else if(n == 0)
        {
            --m;
            n = 1;
            goto skipStack;
        }
        else
        {
            stack.Push(m - 1);
            --n;
            goto skipStack;
        }
    }
    return n;
}

再次,调用Ackermann(4, 2)返回:

哪个是正确的结果.使用的堆栈结构永远不会抛出,因此剩余的唯一限制是堆(当然,当有足够大的输入时,您必须使用"Universe life"作为度量单位...).

由于它的使用方式类似于图灵机的磁带,我们想到的是,任何可计算的功能都可以在足够大小的图灵机上计算.