4

次の関数は、n = 5,000の場合に「スタックレベルが深すぎます（SystemStackError）」を生成します

def factorial(n)
  n == 0 ? 1 : factorial(n -1) * n
end

continuations / callccを使用してこのエラーを回避する方法はありますか？

ノート：

これは再帰なしで実装できることを私は知っています。例えば

def factorial2(n)
  (1..n).inject(1) {|result, n| result * n } 
end
4

3 に答える 3

5

もちろん。継続は何でもできます！ただし、ループまたは関数呼び出しの2つのうちの1つを再発明することになります。デフォルトで末尾呼び出しの最適化を行う私のマシンでは、call/ccを使用した末尾再帰は最適化されません。callccそれぞれが明らかにコールスタック全体をキャプチャするため、プログラムはすぐに停止します。そのコードは壊れています、ここにcall /ccループがあります：

def fact( n )
    (n, f, k) = callcc { |k| [ n, 1, k ] }
    if ( n == 0 ) then return f
    else k.call n-1, n*f, k
    end
end

注：以前は、call / ccが継続渡しチェーンを開始するだけではなく、再帰の必要性について混乱していたことを忘れていたため、以下のコメントを参照してください。

于 2010-03-17T01:35:51.317 に答える
1

ここtailcall_optimize :factorialから取得した、で末尾呼び出しの最適化を有効にできます。

class Class
  def tailcall_optimize( *methods )
    methods.each do |meth|
      org = instance_method( meth )
      define_method( meth ) do |*args|
        if Thread.current[ meth ]
          throw( :recurse, args )
        else
          Thread.current[ meth ] = org.bind( self )
          result = catch( :done ) do
            loop do
              args = catch( :recurse ) do
                throw( :done, Thread.current[ meth ].call( *args ) )
              end
            end
          end
          Thread.current[ meth ] = nil
          result
        end
      end
    end
  end
end

末尾再帰が有効になっているかどうかの判断については、この興味深い投稿を参照してください。

于 2010-03-17T00:38:23.990 に答える
0

問題は、関数がfactorial(n -1) * n式を返し、単一の再帰呼び出しがないことです。returnステートメントに関数呼び出しのみを含めることができた場合、その関数は末尾再帰と呼ばれ、優れたコンパイラー/インタープリター（Rubyがそれを実行できるかどうかはわかりません）は、の使用を回避するためにいくつかの最適化を行うことができます。スタック。

このような末尾再帰関数は次のようになりますが、私はRubyプログラマーではないため、構文にもインタープリターの機能にも慣れていないことに注意してください。しかし、あなたは自分でそれを試すことができるかもしれません：

def factorial(n, result=1)
    n == 0 ? result : factorial(n-1, result * n)
end
于 2010-03-17T00:34:12.050 に答える