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

Question

有没有办法让我的阿克曼功能创建一个堆栈溢出是为相对较小的数字，即（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正等着要处理，我们返回的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同时保持最优化就留给读者做练习:)

顺便说一句，我在测试这个太心急了，所以我做了一个使用阿克曼函数的已知特性，当米的作弊形式小于3：

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)回报：

这是正确的结果。所使用的堆栈结构永远不会抛出，所以剩下的唯一限制就是堆（当然还有时间，如果输入足够大，则必须使用“宇宙生命周期”作为度量单位......）。

，因为它的使用方式类似于一个图灵机的磁带，我们想起的是可以足够大的图灵机上计算任何可计算函数论文。

Answer 2

使用记忆化。喜欢的东西：

private static Dictionary<int, int> a = new Dictionary<int, int>(); 

private static int Pack(int m, int n) { 
return m * 1000 + n; 
} 

private static int Ackermann(int m, int n) { 
    int x; 
    if (!a.TryGetValue(Pack(m, n), out x)) { 
    if (m == 0) { 
     x = n + 1; 
    } else if (m > 0 && n == 0) { 
     x = Ackermann(m - 1, 1); 
    } else if (m > 0 && n > 0) { 
     x = Ackermann(m - 1, Ackermann(m, n - 1)); 
    } else { 
     x = -1; 
    } 
    a[Pack(m, n)] = x; 
    } 
    return x; 
} 

然而，这个例子只能说明这个概念，它仍然没有给出阿克曼（4,2），作为int的方式太小，无法容纳结果正确的结果。你需要一个65536位的整数，而不是32位。