إزالة العودية في بيثون

مرحبا يا هبر! أقدم إليكم ترجمة المقال "إزالة العودية في بيثون ، الجزء 1" للمخرج إريك ليبيرت.

على مدار العشرين عامًا الماضية ، أعجبت بساطة بيثون وقوتها ، رغم أنني لم أعمل معها أبدًا أو أدرسها بالتفصيل.

في الآونة الأخيرة ، نظرت إليه عن كثب - واتضح أنها لغة لطيفة حقًا.

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

• اللاعب في خلية تعسفية في حقل مُرقّم ؛
• الهدف هو العودة إلى الخلية رقم 1 ؛
• إذا كان اللاعب على مربع متساوي ، فإنه يدفع عملة واحدة ويمضي نصف الطريق إلى الخلية رقم 1 ؛
• إذا كان اللاعب في مربع فردي ، فيمكنه دفع 5 عملات معدنية والانتقال مباشرة إلى المربع الأول أو دفع عملة واحدة واتخاذ خطوة واحدة إلى المربع رقم 1 - على مربع زوجي.

والسؤال هو: ما هو أقل مقدار من العملات التي تحتاج إلى دفعها للعودة من الخلية الحالية إلى الأولى.

المهمة لديها حل عودي واضح:

def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5) 

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

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

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

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

إن الأسلوب الذي سأعرضه ، بطبيعة الحال ، لا يتطابق تمامًا مع الطريقة التي يتم بها كتابة Python ، وربما يستخدم الحل على غرار Python المولدات أو ميزات أخرى من اللغة.

ما أريد أن أبينه هنا هو كيفية التخلص من التكرار باستخدام سلسلة من التحولات الصغيرة والآمنة ، مما يؤدي بالوظيفة إلى نموذج يسهل فيه استبدال العودية بتكرار.

للبدء ، دعنا نرى كيف نجلب البرنامج إلى هذا النموذج.

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

 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result) 

الخطوة الثانية التي أريد القيام بها هي حساب الوسيطة في دالة منفصلة:

 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result) 

في الخطوة الثالثة ، أرغب في إضافة وظيفة مساعدة ستحدد وظيفة المتابعة التي يتم استدعاؤها بعد العودة من التكرار.

لاحظ أن وظيفة المساعد تقوم بإرجاع دالة.

 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after  ! result = cost(argument) return after(result) 

نكتبها الآن بشكل عام وموجز:

 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument)) 

يمكن ملاحظة أن كل تغيير تم إجراؤه يحتفظ بمعنى البرنامج.

الآن يتم تنفيذ التحقق من تكافؤ الرقم مرتين ، على الرغم من أنه قبل التغييرات كان هناك فحص واحد.

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

لكن لا داعي للقلق بشأن هذا كجزء من هذه المهمة.

لقد قللنا من طريقة العودية إلى الشكل العام.

• في الحالة الأساسية:
  
  • احسب القيمة المراد إرجاعها ؛
  • إعادته.
• في حالة غير أساسية:
  
  • حساب وسيطة العودية ؛
  • إجراء مكالمة متكررة ؛
  • حساب القيمة المرجعة ؛
  • إعادته.

الشيء المهم الذي تحتاج إلى الانتباه إليه في هذه الخطوة هو أنه after ذلك يجب ألا يحتوي على مكالمات cost نفسه.

الطريقة التي أظهرها هنا تزيل مكالمة متكررة واحدة.

إذا كان لديك تكراران أو أكثر ، فسنحتاج إلى حل مختلف.

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

الحيلة هي تخيل ما يحدث في برنامج تكراري.

كيف نفعل نزولًا متكررًا: نسمي get_argument قبل استدعاء متكرر ونستدعي الدالة after بعد العودة من التكرار.

بمعنى ، تحدث كافة المكالمات إلى get_argument قبل كافة المكالمات إلى بعد .
لذلك ، يمكننا تحويل هذا إلى دورتين: أول استدعاء get_argument وتشكيل قائمة بعد الدوال ، والثاني يدعو كل بعد الدوال:

 #... def cost(s): #     "after".    #       # ,    . afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument #       "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result 

لا مزيد من العودية!

يبدو وكأنه سحر ، لكن كل ما نفعله هنا هو نفس الإصدار المتكرر للبرنامج ، وبالترتيب ذاته.

يعكس هذا المثال الفكرة التي كثيرا ما أكررها حول مكدس الاستدعاءات: الغرض منه هو توصيل ما سيحدث بعد ذلك ، وليس ما حدث بالفعل!

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

بدلاً من استخدام مكدس الاستدعاءات كطريقة غير فعالة ومرهقة لتخزين مكدس ما بعد ، يمكننا ببساطة تخزين مكدس ما بعد الوظيفة.

في المرة القادمة سوف ننظر إلى طريقة أكثر تعقيدًا لإزالة العودية في بيثون.