最大反復深度を超えずに、Pythonでargs m> = 4およびn> = 1を持つ再帰的ackermann（m、n）関数を計算することは可能ですか？

Question

引数m>=4とn>=1を持つ合計計算可能な再帰関数ackermann(m,n)をpythonで最大再帰深度を超えないで計算することは可能ですか？

def ackermann(m,n): 

    if m == 0: 
     return n+1 
    if n == 0: 
     return ackermann(m-1,1) 
    else: 
     return ackermann(m-1,ackermann(m,n-1)) 

ackermann(4,1) 

Answer 1

このレベルの応答では、動的プログラミングを使用してください。関数をメモしてください。これは、以前の結果の表を保持することを意味します。すでに計算されている結果が見つかった場合は、それをテーブルから戻します。それが新しい呼び出しである場合にのみ、計算を行いますか？その場合、再帰呼び出しのほとんどまたはすべてがテーブルにあります。例えば：

import sys 
sys.setrecursionlimit(30000) 

memo = {} 

def ack(m, n): 
    if not (m, n) in memo: 
     result = (n + 1) if m == 0 else (
      ack(m-1, 1) if n == 0 else ack(m-1, ack(m, n-1))) 
     memo[(m, n)] = result 
    return memo[(m, n)] 

print ack(3, 4) 
print ack(4, 1) 
print ack(4, 2) 

あなたはまだによるメモリ使用にACK（4、2）、同じくらい大きなものに問題があるでしょう。

125 
65533 
Segmentation fault (core dumped) 

Answer 2

はい。アルゴリズムを改善するためにsys.setrecursionlimit以上の数学を使用することができます。 PythonコードについてはRosetta Code taskを参照してください。

注！

%timeit a2 = ack2(4,2) 
1000 loops, best of 3: 214 µs per loop 

len(str(a2)) 
Out[9]: 19729 

答えでほぼ20 桁です：

は、私はちょうどACK2を再実行しました。