如何防止我的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位。