هل يمكن التعبير عن جميع الخوارزميات التكرارية بشكل متكرر؟

Question

إذا لم يكن الأمر كذلك ، فهل هناك مثال مضاد جيد يوضح خوارزمية تكرارية لا يوجد فيها نظير متكرر؟

إذا كان الأمر كذلك ، يمكن التعبير عن جميع الخوارزميات التكرارية بشكل متكرر ، هل هناك حالات يصعب القيام بها؟

أيضا ، ما هو الدور الذي تلعبه لغة البرمجة في كل هذا؟ أستطيع أن أتخيل أن مبرمجي المخططات لديهم تكرار مختلف عن التكرار (= خلاصة الذيل) واستخدام المكدس من مبرمجي Java فقط.

Answer 1

هناك دليل مخصص بسيط لهذا. نظرًا لأنه يمكنك بناء لغة كاملة باستخدام هياكل تكرارية صارمة ولغة كاملة باستخدام الهياكل العودية فقط ، فإن الاثنين متكافئان.

Answer 2

هل يمكن التعبير عن جميع الخوارزميات التكرارية بشكل متكرر؟

نعم ، لكن الدليل غير مثير للاهتمام:

1. قم بتحويل البرنامج بكل تدفق التحكم في حلقة واحدة تحتوي break, return, exit, raise, ، وهلم جرا. قدم متغيرًا جديدًا (أطلق عليه "عداد البرنامج") الذي يستخدمه عبارة الحالة لتحديد الكتلة التي يجب تنفيذها بعد ذلك.

   تم اكتشاف هذا البناء خلال "حروب البرمجة المنظمة" العظيمة في الستينيات عندما كان الناس يجادلون بالقوة التعبيرية النسبية لمختلف بنيات التدفق.

2. استبدل الحلقة بوظيفة متكررة ، واستبدل كل متغير محلي قابل للتغيير بمعلمة لتلك الوظيفة. هاهو! تكرار يحل محله العودية.

هذا الإجراء يصل إلى كتابة مترجم للوظيفة الأصلية. كما قد تتخيل ، فإنه يؤدي إلى رمز غير قابل للقراءة ، وليس من المثير للاهتمام القيام به. لكن, ، يمكن أن تكون بعض التقنيات مفيدة للشخص الذي لديه خلفية في البرمجة الضرورية الذي يتعلم البرمجة بلغة وظيفية لأول مرة.

Answer 3

كما تقول ، يمكن تحويل كل نهج تكراري إلى نهج "متكرر" ، ومع مكالمات الذيل ، لن ينفجر المكدس أيضًا. :-) في الواقع ، هذه هي في الواقع كيف ينفذ المخطط جميع الأشكال الشائعة للحلقات. مثال في المخطط:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

هنا ، على الرغم من أن الوظيفة تبدو تكرارية ، إلا أنها تتكرر فعليًا على lambda الداخلية التي تأخذ ثلاث معلمات ، x, y, ، و i, ، ودعا نفسها بقيم جديدة في كل تكرار.

فيما يلي إحدى الطرق التي يمكن أن تكون بها الوظيفة موسعة للماكرو:

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

بهذه الطريقة ، تصبح الطبيعة العودية أكثر وضوحًا بصريًا.

Answer 4

تحديد التكرار على النحو التالي:

function q(vars):
  while X:
    do Y

يمكن ترجمتها على النحو التالي:

 function q(vars):
    if X:
      do Y
      call q(vars)

في معظم الحالات ، ستشمل زيادة عداد يتم اختباره بواسطة X. يجب تمرير هذا المتغير في "Vars" بطريقة ما عند السير في الطريق المتكرر.

Answer 5

كما لاحظت من قبل plinth في إجابتهم يمكننا بناء أدلة توضح كيف العودية والتكرار مكافئ ويمكن استخدام كلاهما لحل نفس المشكلة ؛ ومع ذلك ، على الرغم من أننا نعلم أن الاثنين يعادلان هناك عيوب لاستخدام واحد على الآخر.

في اللغات التي لم يتم تحسينها من أجل التكرار ، قد تجد أن الخوارزمية التي تستخدم تشكيلات التكرار بشكل أسرع من العودية والمثل ، حتى في اللغات المحسنة ، قد تجد أن الخوارزمية التي تستخدم التكرار المكتوبة بلغة مختلفة تعمل بشكل أسرع من التكرار. علاوة على ذلك ، قد لا تكون هناك طريقة واضحة لمكتوبة خوارزمية معينة باستخدام التكرار مقابل التكرار والعكس بالعكس. هذا يمكن أن يؤدي إلى رمز يصعب قراءة الأمر الذي يؤدي إلى مشكلات الصيانة.

Answer 6

Prolog هي لغة متكررة فقط ويمكنك أن تفعل كل شيء فيه إلى حد كبير (لا أقترح عليك القيام به ، ولكن يمكنك :))

Answer 7

الحلول العودية عادة غير فعال نسبيا بالمقارنة مع الحلول التكرارية. ومع ذلك ، تجدر الإشارة إلى أن هناك بعض المشكلات التي لا يمكن حلها إلا من خلال التكرار وقد لا توجد حل تكراري مكافئ أو معقد للغاية للبرمجة بسهولة (مثال على ذلك وظيفة Ackermann لا يمكن التعبير عنها بدون عودية) على الرغم من أن الأكرات أنيقة وسهلة الكتابة وفهم.