アッカーマンの呪い - Mae向きなブログ

CodeIQの「アッカーマンの呪い」に挑戦してみました。本日、フィードバックをもらったのですが、未だにA(4, 1)の求め方が理解できずにいます。
以下に、自分が作成したRuby スクリプトと実行例を載せていますが、A(4, 1)は

stack level too deep (SystemStackError)

となり計算できていません。
この対処法は、

再帰を使わない方法で書き直す必要がある。
スタックの深さをOS側 or Ruby側で調整する。パラメータの変更で対応できる。
コンピュータを買い直す。
その他

のどんな方法なのでしょう。

solv.rb

#!/usr/bin/env ruby

$hash = Hash.new{|hash, value| hash[value] = Hash.new }

def ackerman(m, n)
  return $hash[m][n] if $hash[m][n]
  if m == 0
    $hash[m][n] = n + 1
  elsif n == 0
    $hash[m][n] = ackerman(m - 1, 1)
  else
    $hash[m][n] = ackerman(m - 1, ackerman(m, n - 1))
  end
  $hash[m][n]
end

p ackerman(3, 4)
p ackerman(4, 1)

実行結果

$ ruby -v
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-darwin11.4.2]
$ ruby solv.rb
125
solv.rb:6: stack level too deep (SystemStackError)

参考

設問6の解説：アッカーマンの呪い - スピード冒険野郎のブログ

追記(2013/07/29)

twitterで、@cielavenir さんに解決策を教えて頂きました。Ruby 2.0では、スタックサイズの変更ができるんだそうです。

$ export RUBY_THREAD_VM_STACK_SIZE=3000000
$ ruby solv.rb
125
65533

追記(2013/07/30)

出題者の id:infoarchitect さんが「「アッカーマンの呪い」のスタックオーバーフローの対処方法」という解説記事を書かれています。m=3以下を公式で置き換えたのが以下です。これだと、A(4, 2)も計算出来ますね。

solv_1.rb

#!/usr/bin/env ruby

$hash = Hash.new{|hash, value| hash[value] = Hash.new }

def ackerman(m, n)
  return $hash[m][n] if $hash[m][n]
  $hash[m][n] = if m == 0 || m == 1
                  n + 1 + m
                elsif m == 2
                  2 * n + 3
                elsif m == 3
                  (2 ** (n+3)) -3
                elsif n == 0
                  ackerman(m - 1, 1)
                else
                  ackerman(m - 1, ackerman(m, n - 1))
                end
  $hash[m][n]
end

p ackerman(3, 4)
p ackerman(4, 1)
p ackerman(4, 2)