継続は、再帰のための代替として使用することはできますか？

Question

は、以下の関数はのための '深すぎるスタックレベル（SystemStackError）' を生成し、N = 5,000

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

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

注：

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

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

Answer 1

確かに。継続は何もすることができます！ループまたは関数呼び出し：しかし、あなたは、2つのうちのいずれかを再発明する羽目になる。デフォルトでは、末尾呼び出しの最適化、コール/ CCに末尾再帰をして私のマシン上ではは最適化されません。各callccが明らかにコールスタック全体をキャプチャするように、プログラムはすぐにダウン湿原。そのコードが破壊され、ここでコール/ 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

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

。

Answer 2

現在のページのから取ら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

末尾再帰が有効になっているかどうかを判断する程度この興味深い記事を参照してください。

Answer 3

の問題は、機能が発現及び単一の再帰呼び出しであるfactorial(n -1) * nを返すこと、です。あなたがreturn文で唯一の関数呼び出しを持って管理する場合は、関数が呼び出されたのテールの再帰的な、良いコンパイラ/インタプリタ（私はRubyはそれが可能であるかどうかわからないです）、いくつかの操作を行うことができますスタックの使用を回避するために最適化ます。

このような末尾再帰関数は次のようになりますが、私はRubyのプログラマではないので、私はどちらの構文にも通訳の機能を使用しないことにしていますのでご注意ください。しかし、あなたはあなた自身でそれを試すことができるかもしれません。

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