يمكن استمرارا أن تستخدم كبديل عن العودية?

Question

الدالة التالية يولد 'كومة مستوى عميق جدا (SystemStackError)' ن = 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

بالتأكيد.استمرارا يمكن أن تفعل أي شيء!ولكن عليك في نهاية المطاف إعادة اختراع واحد من أمرين:حلقة أو استدعاء دالة.على هذه الآلة التي لا ذيل استدعاء الأمثل افتراضيا ، ذيل العودية مع الدعوة/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 وهو التعبير و لا واحد دعوة متكررة.إذا كنت تدير فقط استدعاء دالة في بيان العودة ، ثم يتم استدعاء الدالة ذيل العودية, جيد مترجم / مترجم (أنا لست متأكدا مما إذا روبي هو قادر على ذلك) يمكن أن تفعل بعض التحسينات إلى تجنب استخدام المكدس.

هذا الذيل-وظيفة العودية قد تبدو مثل هذا ، ولكن يرجى ملاحظة أن أنا لست روبي مبرمج, لذلك أنا لا تستخدم بناء الجملة ولا ملامح مترجم.ولكن كنت قد تكون قادرة على محاولة ذلك بنفسك:

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