再帰法を使ってPerfect Numberを出力するプログラムを考えていますが、n>=5000でスタックオーバーフローになってしまいます。
新たなメソッドやクラス、ループ、メルセンヌ数などを使用せず、また下記の平易な再帰的アルゴリズムを維持したまま最低4つまで出力したいです。
m%2==0を用い計算回数を減らすための除法を導入するなど、試行錯誤しましたがなかなか上手くいきません。(やり方が悪かったのかもしれません...)
条件が多く恐縮ですが、知恵をお貸しください。
def perfect_numbers(n) perfect_numbers_r(n, 1, Array.new(0), 0) end def perfect_numbers_r(n, m, perfect_numbers, count) if m > n perfect_numbers elsif sod(m,m/2) == m perfect_numbers[count] = m perfect_numbers_r(n, m+1, perfect_numbers, count+1) else perfect_numbers_r(n, m+1, perfect_numbers, count) end end def sod(t, k) if k == 0 0 else if t % k == 0 t + sod(t, k-1) else sod(t, k-1) end end end
システムのコールスタック領域を拡大したり末尾再帰をしてくれる別のシステムを利用するといった方法ではなく、アルゴリズムを工夫することで「再帰呼び出しの深さを軽減する改善方法はあるか?」を考えておられるのですよね?そうなのであればその旨を明確に表明したほうがよいと思います。
titorさんの回答拝見しましたが上のコメントは蛇足でした。無視してくださいませ。
ご質問ありがとうございます。おっしゃる通り、アルゴリズムを工夫することで、再帰呼び出しの深さを軽減する改善方法を探索しています。もし良い案がございましたらご教示下さいませ。
そもそも、今のコードですと素数の配列が返ってくるようなのですが、少ない数での動作はあっているんですか?