أنماط تصميم لتحويل الخوارزميات العودية إلى تلك التكرارية

Question

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

Answer 1

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

Answer 2

إن الأسلوب الشائع الذي أستخدمه حيث أكون في عملية استبدال خوارزمية متكررة من قِبل تقنية تكرارية هي بشكل عام لاستخدام مكدس ، ودفع المعلمات التي يتم تمريرها إلى الوظيفة العودية.

تحقق من المقالات التالية:

• استبدال العودية بمكدس
• أكوام والقضاء على العودية (بي دي إف)

Answer 3

الممارسة الشائعة لإدارة مكدس LIFO الذي يحتفظ بقائمة تشغيل لما لا يزال يتعين القيام به ", ، ولتعامل مع العملية برمتها في حلقة من الوقت والتي تستمر حتى تصبح القائمة فارغة.
مع هذا النمط ، يتم استبدال ما يمكن أن يكون دعوة عودية في نموذج العودية الحقيقية
- دفع "سياق" المهمة الحالية (الجزئية) على المكدس ،
- دفع المهمة الجديدة (المهمة التي دفعت العودية) على المكدس
- و "متابعة" (أي القفز إلى بداية) الحلقة. بالقرب من رأس الحلقة ، ينبثق المنطق في أحدث سياق تم إدراجه مؤخرًا ، ويبدأ العمل على هذا الأساس.

على نحو فعال هذه مجرد معلومات "التحركات" والتي كان من الممكن أن يتم الاحتفاظ بها في stackframes المتداخلة على مكدس "النظام" ، إلى حاوية مكدس التي يديرها التطبيق. ومع ذلك ، فهو تحسن ، يمكن تخصيص حاوية المكدس هذه في أي مكان (يرتبط حد العودية عادةً بالحدود في مكدس "النظام"). لذلك ، يتم تنفيذ نفس العمل بشكل أساسي ، لكن الإدارة الصريحة لـ "المكدس" تسمح لهذا الحدوث داخل بنية حلقة واحدة بدلاً من المكالمات العودية.

Answer 4

في كثير من الأحيان يمكن استبدال العودية العامة بتكرار الذيل ، من خلال جمع النتائج الجزئية في تراكم وتمريره مع المكالمة العودية. يعتبر عودة الذيل تكرارًا بشكل أساسي ، ويمكن تنفيذ المكالمة العودية كقفزة.

على سبيل المثال ، التعريف العودية العامة القياسية للمجموعة

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

يمكن استبداله

 factorial(n) = f_iter(n, 1)

و

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

وهو ذيل عودية. هو نفسه

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Answer 5

إلقاء نظرة على هذه الروابط لأمثلة الأداء

التكرار مقابل التكرار (الحلقات): مقارنة السرعة والذاكرة

و

استبدل التكرار بالتكرار

و

التكرار مقابل التكرار

س: هل النسخة العودية عادة ما تكون أسرع؟ ج: لا - عادة ما يكون أبطأ (بسبب النفقات العامة للحفاظ على المكدس)

  Q: Does the recursive version usually use less memory?
  A: No -- it usually uses more memory (for the stack).

  Q: Then why use recursion??
  A: Sometimes it is much simpler to write the recursive version (but

سنحتاج إلى الانتظار حتى ناقشنا الأشجار لرؤية أمثلة جيدة حقًا ...)

Answer 6

أبدأ عمومًا من الحالة الأساسية (كل وظيفة متكررة لها واحدة) وأعمل في طريقي للخلف ، وتخزين النتائج في ذاكرة التخزين المؤقت (صفيف أو علامات التصنيف) إذا لزم الأمر.

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

تتمثل الفكرة في البدء في الحالة الأساسية (أو الحالات الأساسية) واستخدام ذلك لإنشاء الحل للحالات الأكبر ، ثم استخدام تلك لبناء حالات أكبر وما إلى ذلك ، حتى يتم حل المشكلة بأكملها. هذا لا يتطلب كومة ، ويمكن القيام بها مع الحلقات.

مثال بسيط (في بيثون):

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

Answer 7

نمط واحد عودة الذيل:

يُقال إن استدعاء الوظيفة كانت عودية إذا لم يكن هناك شيء يجب القيام به بعد إرجاع الوظيفة باستثناء إرجاع قيمتها.

ويكي.