「アッカーマンの呪い」のスタックオーバーフローの対処方法

CodeIQ

数多くの方々の「アッカーマンの呪い」への挑戦ありがとうございます。


プログラムは再帰関数で解くのが答えとなっていますが、A(4,1), A(4,2)の計算あたりで、計算爆発が起こり、スタックオーバーフローのエラーが発生し、計算終了となってしまいます。
挑戦者からの解答も参考にしながら、対処法をいくつか、書いてみたいと思います。

A(4,1)は65533となります。
A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってします。プログラミング言語が19729桁まで表現できるかというのも、チェックする必要があります。


1. スタックオーバーフローの対処

アッカーマン関数の計算は再帰が深くなるので、スタックサイズをできるだけ増やす必要があります。

Rubyでは、2.0で環境変数RUBY_THREAD_VM_STACK_SIZEが導入されたので、4MB等に設定してみてはどうでしょうか。

Pythonでは下記のようにsys.setrecursionlimit()でスタックサイズを増やせます。

import sys
sys.setrecursionlimit(10**9)

私の環境では、これでもA(4,1)は計算できませんでした。


2. 計算結果を保持する方法

m✕nの格納場所を確保しておき、一度計算したA(m,n)の結果をメモリに保存しておくと、スタックも深くならず、計算速度も向上します。


3. m=3以下のものを公式で置き換える

この方法は挑戦者のだいじゅさんから頂いた解答です。下記のようにアッカーマン関数の公式があるので、m=3以下の場合について公式で置き換えます。
If m=0 or m=1 then A(m,n) = n + 1 + m
If m=2 then A(2,n) = 2 * n + 3
If m=3 then A(3,n) = 2^(n+3) – 3

import sys

sys.setrecursionlimit(5000)

def A(m, n):
    if m < 2:
        return n + 1 + m
    elif m == 2:
        return 2*n + 3
    elif m == 3:
        return (2 ** (n+3)) - 3
    elif n == 0:
        return A(m-1, 1)
    else:
        return A(m-1, A(m, n-1))
    
def do(m, n):
    try:
        return A(m, n)
    except RuntimeError:
        raise RuntimeError, "maximum recursion depth exceeded"
    except:
        print "Error"
#######################
print A(4, 2)

このプログラムですと、驚くほど早くA(4,2)が求まります。
A(4,3)については、私の環境では28GBのバーチャルメモリを食い、画面は固まったまま、三日後にエラーがでて終了しました。
A(4,2)は 2^65536 – 3 になり、19729桁の十進数です。そもそも全宇宙の水素原子の数が10^80個、つまり81桁だから、既に全宇宙の水素原子数を超えている。
A(4,3)=2^(2^65536) - 3 だから、途方もない数になります。なんか、くらくらしてきた。