Python中的修改的Ackermann函數分割錯誤

Question

所以我嘗試創建基本Ackermann函數的修改版本，該函數使用字典來存儲已經計算的值，以便下次當程序遇到類似的函數調用時它可以使用已經計算出來的價值，這似乎大大加快了這個過程。這裏是代碼：

import sys 
sys.setrecursionlimit(100000) 

resultset ={} 

def ackermann(m, n): 
    """Computes the Ackermann function A(m, n) 

    See http://en.wikipedia.org/wiki/Ackermann_function 

    n, m: non-negative integers 
    """ 
    if (m,n) in resultset: 
     return resultset[(m,n)] 
    if m == 0: 
     ans = n+1; 
    elif n == 0: 
     ans = ackermann(m-1, 1) 
    else: 
     ans = ackermann(m-1, ackermann(m, n-1)) 
    if m != 0: 
     resultset[(m,n)] = ans 
    return ans; 

for i in range(0,10) : 
    for j in range(0,10) : 
     print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j))) 

現在我遇到的問題是，它會在很短的時間後停止執行。輸出是這樣的：

ackermann(0, 0): 1 
ackermann(0, 1): 2 
ackermann(0, 2): 3 
ackermann(0, 3): 4 
ackermann(0, 4): 5 
ackermann(0, 5): 6 
... 
... 
... 
ackermann(3, 2): 29 
ackermann(3, 3): 61 
ackermann(3, 4): 125 
ackermann(3, 5): 253 
ackermann(3, 6): 509 
ackermann(3, 7): 1021 
ackermann(3, 8): 2045 
ackermann(3, 9): 4093 
ackermann(4, 0): 13 
ackermann(4, 1): 65533 
Segmentation fault 

我的系統是酷睿i5與12 GB的RAM，且到達MEM限制，可能是什麼問題，在此之前程序退出方式？

我也嘗試使用貨架而不是字典，以便它將數據存儲在磁盤上。這裏是代碼爲：

我也嘗試使用貨架而不是字典，以便我可以看到磁盤上的使用情況。這裏是代碼..

import sys 
sys.setrecursionlimit(100000) 

import shelve 
resultset = shelve.open("file.o") 

def ackermann(m, n): 
    """Computes the Ackermann function A(m, n) 

    See http://en.wikipedia.org/wiki/Ackermann_function 

    n, m: non-negative integers 
    """ 
    if str((m,n)) in resultset: 
     return resultset[str((m,n))] 
    if m == 0: 
     ans = n+1; 
    elif n == 0: 
     ans = ackermann(m-1, 1) 
    else: 
     ans = ackermann(m-1, ackermann(m, n-1)) 
    if m != 0: 
     resultset[str((m,n))] = ans 
    return ans; 

for i in range(0,6) : 
    for j in range(0,6) : 
     print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j))) 

輸出文件來到正好6MB和python崩潰。有人知道爲什麼嗎？

Answer 1

好了很多的試驗和錯誤，我能夠理解的問題是，由於遞歸，程序運行的堆棧空間不足。我能夠通過將堆棧大小設置爲無限來解決這個問題。不幸的是，我不認爲在Windows上有類似的解決方案。下面是我所做的代碼..

import resource, sys 
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY)) 
sys.setrecursionlimit(10**8) 

resultset ={} 

def ackermann(m, n): 
    """Computes the Ackermann function A(m, n) 

    See http://en.wikipedia.org/wiki/Ackermann_function 

    n, m: non-negative integers 
    """ 
    if (m,n) in resultset: 
     return resultset[(m,n)] 
    if m == 0: 
     ans = n+1; 
    elif n == 0: 
     ans = ackermann(m-1, 1) 
    else: 
     ans = ackermann(m-1, ackermann(m, n-1)) 
    if m != 0: 
     resultset[(m,n)] = ans 
    return ans; 

for i in range(0,6) : 
    for j in range(0,6) : 
     print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j))) 

這兩條線是神奇在哪裏發生了：

resource.setrlimit（resource.RLIMIT_STACK，（resource.RLIM_INFINITY，resource.RLIM_INFINITY） ）sys.setrecursionlimit（10 ** 8）

無論如何感謝您的嘗試。 :)

Answer 2

Ackermann函數變得非常大，非常快......下一步（4,2）的值是2.00352993040684646497907235156025575044782547556975141 ...×10^19728。

如果你看一下內存設計缺陷，你可能得到的東西是這樣的：

python[4413]: segfault at 7fff2bae5ff8 ip 000000000052185f sp 00007fff2bae6000 error 6 in python2.7[400000+2bd000]

錯誤6指示頁面寫入失敗。