2重の再帰はスタック配列を使わないとループに直せませんか？

Question

再帰関数saikiを再帰しないnot_saikiに直したらメモリ不足で落ちました。
配列を使わなければもっといけるような気がするのですが…
どうにかなりませんか？数学には疎いので…

#saiki.rb
def saiki a,b,c
  if c==1
    return a*b
  elsif b==1
    return a
  else
    return saiki a, saiki(a, b-1, c), c-1
  end
end

def not_saiki a,b,c
  stack = []
  loop do
    if c==1
      b *= a
      return b if stack.empty?
      c = stack.pop
    elsif b==1
      b = a
      c = stack.pop
    else
      b -= 1
      stack << c-1
    end
  end
end

puts not_saiki *ARGV.map{|s|s.to_i}

$ ruby saiki.rb 3 3 9

Answer 1

回答ではありませんが、すこし調べてみたことを書きます。

ruby saiki,rb 3 3 1 => 9 = 3 * 3 = 3 ^ 2
ruby saiki,rb 3 3 2 => 27 = 3 * (3 * 3) = 3 ^ 3
ruby saiki,rb 3 3 3 => 7625597484987 = 3 ^ 27 = 3 ^ (3 ^ 3)

確信はできませんが、 saiki(3, 3, 4) が 3 ^ (3 ^ (3 ^ 3)) となるとすると、
これ時点ですでに 通常のコンピュータ言語で扱える数の範囲を超えます。

7625597484987 を google 検索すると グラハム数というものが出てきます。

• グラハム数

ruby コードから 再帰性を取り除くだけでは この関数の 一般項は結果の数が大きくなりすぎ 計算できないと思います。
(関数が呼ばれる回数も大変なことになってます。
saikie 関数の先頭に puts "#{a}, #{b}, #{c}" をいれて プログラムを実行すると、とんでもない回数の呼び出しが発生することがわかります。

備考１
ruby saiki.rb 3 3 4 は私の環境では ... 7267 levels のエラーがでました。
おそらく再帰のネストの限界が 7264 なのだとおもわれます。
ruby の再帰の深さ制限は制御が可能です。
$ export RUBY_THREAD_VM_STACK_SIZE=100000000
$ ruby saiki.rb 3 3 4
とすると、... 694457 levels... のエラーになります。

質問；
この関数定義はどこから入手したものですか？
この関数定義には なんらかの背景があるものと思います。
その背景を知りたいです。

Comments

[jun68ykt]

こんにちは。自分も、saiki(3,3,3)を紙と鉛筆で追って、3^(3^3)にたどり着きました。グラハム数なんていうのがあるのですね。勉強になりました！

Answer 2

どちらをベストアンサーにしようか迷ったのですが、結局自分がしたかったのは、
saiki(3,3,9)を、途中まででいいのでできるだけ計算したかったのです。
数学的手法を使って、なんとかメモリ不足にならないように出来ないか・・・？と思って質問しました。

この再帰関数は適当に計算量が大きくなりかつ計算が終わりそうなものを考えました。

・・・ただ今、様々な試行錯誤の結果、saiki(a,b,c)=a→b→c、なことが判明しました。
ものすごく先を越されてましたしこのsaikiただの劣化版ですね。

Answer 3

この再帰関数は，ある値以上で極めて巨大な数になるというアッカーマン関数に似た関数になっています．
通常のコンピュータでは到底扱えないくらいの桁数の数を生成するので，
単に再帰でないものに書きなおせるとは思えません．

この問題で問われていることはなんでしょうか？