Ruby再帰の計算回数を減らしたい

Question

###実現したいこと
Rubyで正の整数nの全ての約数を配列で出力するプログラムを作りたいのですが、下記を実行するとm=5000付近でスタックオーバーフローになり、エラーになります。

＜条件＞
・ 少なくともm=10000まで、エラーにならず正常に実行してほしい
・ 再帰法の形を維持し、popやshiftといった配列クラスのメソッドを使わない
・ 整数論なども用いず、平易な計算で完結する

以上の条件のもと、計算回数を節約できるアルゴリズムがあればご教示くださいm(_ _)m

###該当のプログラム

def divisors_all(m)

  divisors_all_r(m, 1, Array.new(0), 0)

end

def divisors_all_r(m, k, divisors, count)

  if k > m
    divisors
  elsif m % k == 0
    divisors[count] = k
    divisors_all_r(m, k + 1, divisors, count + 1)
  else
    divisors_all_r(m, k + 1, divisors, count)
  end

end

Answer 1

スタックオーバーフローさせたくないというのであれば、下記のように書くことで回避は可能です。
(下記コードはRuby 2.3.1で確認しています。バージョンが古いとうまくいかないかもしれません)

# frozen_string_literal: true
RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

RubyVM::InstructionSequence.compile(<<EOS).eval

def divisors_all(m)
  divisors_all_r(m, 1, Array.new(0), 0)
end

def divisors_all_r(m, k, divisors, count)
  if k > m
    divisors
  elsif m % k == 0
    divisors[count] = k
    divisors_all_r(m, k + 1, divisors, count + 1)
  else
    divisors_all_r(m, k + 1, divisors, count)
  end
end

p divisors_all(10000)

EOS

やっていることは末尾呼び出し最適化という手法です。詳細は下記の記事を参考にしてください。
Ruby で末尾呼び出し最適化する方法 - おもしぇてっく

末尾呼び出し最適化は卑怯だ…でもやり方は変えたくないと言うのであれば、単純に次の約数を見つけるとすればいいかと思います。次の呼び出しは約数が見つかったときだけでもいいのですから。

# frozen_string_literal: true
def divisors_all(m)
  divisors_all_r(m, 1, [])
end

def divisors_all_r(m, k, divisors)
  d = (k..m).find { |i| m % i == 0 }
  return divisors unless d
  divisors_all_r(m, d + 1, divisors + [d])
end

p divisors_all(10000)

ただ、今回の「全ての約数を求める」ということだけが条件であれば、素因数分解して、全ての組合せをかけた物をリストにした方がいいかもしません。

# frozen_string_literal: true
require 'prime'

def divisors_all(m)
  [1].product(*m.prime_division.map { |n, e| (0..e).map { |i| n**i } })
     .map { |list| list.inject(:*) }
     .sort
end

p divisors_all(10000)

Answer 2

これ…計算回数という問題ではないですね。kがmの約数であろうがなかろうが再帰が起きるため、必ずm回再帰が発生する事になります。
「kがmの約数なら、m/kもmの約数である」のは自明なので、それを使えば√m回になりはします。
そもそも再帰の使い所がおかしい気もしますが。

Answer 3

少しだけ補足をします。

再帰呼び出しでは、メモリのスタック領域上に引数などが確保されることになります。スタック領域はヒープ領域に比べてサイズが小さいため、このような大きな再帰呼出しは実行できません。

また、再帰呼出しは状態記憶用の変数を用いることによってループで書くことができます。