(بايثون) الروتينات الفرعية. العودية

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

إذا كنت تتذكر الرياضيات ، فهناك يمكنك التعرف على مبدأ الاستقراء الرياضي . وهي كالتالي:
بعض العبارات صحيحة لكل n طبيعية إذا
نبسب ؛ نبسب ؛ 1. صالح لـ & nbsp؛ n = 1 & nbsp؛ and
نبسب ؛ نبسب ؛ 2. من صحة البيان لأي تعسفي طبيعي n = k & nbsp ؛ يترتب على ذلك أنه صحيح لـ & nbsp؛ n = k + 1.

في البرمجة ، تسمى هذه التقنية العودية.
نبسب ؛

العودية هي طريقة لتحديد مجموعة من الكائنات من حيث المجموعة نفسها ، بناءً على حالات أساسية بسيطة.

التكرار هو إجراء (وظيفة) يستدعي نفسه مباشرة أو من خلال إجراءات ووظائف أخرى. نبسب ؛

مثال <قبل> def Rec (a): إذا (a & gt؛ 0): Rec (a-1) طباعة (أ)
من الناحية التخطيطية ، يمكن تمثيل عمل العودية بواسطة مخطط انسيابي



يتم تنفيذ الإجراء Rec () مع المعلمة 3. ثم ، داخل الإجراء مع المعلمة 3 ، يتم استدعاء الإجراء مع المعلمة 2 ، وهكذا ، حتى يتم استدعاء الإجراء مع المعلمة 0. عندما يتم استدعاء الإجراء مع المعلمة 0 ، لن تحدث المكالمة العودية بعد الآن وسيؤدي الإجراء باستخدام المعلمة 0 إلى طباعة الرقم 0 والخروج. ثم يتم نقل التحكم مرة أخرى إلى الإجراء بالمعامل 1 ، كما أنه ينهي عمله بطباعة الرقم 1 ، وهكذا. قبل الإجراء مع المعلمة 3. نبسب ؛

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

العودية كبديل حلقة لقد رأينا أن العودية هي التنفيذ المتكرر للتعليمات الواردة في روتين فرعي. وهذا بدوره يشبه عمل الدورة. هناك لغات برمجة يكون فيها بناء الحلقة غائبًا تمامًا. على سبيل المثال ، Prolog. & nbsp؛
دعنا نحاول محاكاة عمل الحلقة لـ . & nbsp؛
تحتوي الحلقة لـ على متغير عداد الخطوة. في روتين فرعي متكرر ، يمكن تمرير مثل هذا المتغير كمعامل. <قبل> # الإجراء LoopImitation () مع اثنين من المعلمات # المعلمة الأولى & ndash؛ عداد الخطوة ، المعلمة الثانية & ndash ؛ العدد الإجمالي للخطوات def LoopImitation (أنا ، ن): print ("Hello N"، i) # بيان يتكرر لأي قيمة من i إذا كنت & lt ؛ n: # حتى يساوي عداد الحلقة القيمة n ، LoopImitation (i + 1، n) # استدعاء مثيل جديد للإجراء ، # مع المعلمة i + 1 (انتقل إلى القيمة التالية i)

العودية والتكرار

لفهم العودية ، تحتاج إلى فهم العودية ...
نبسب ؛

التكرار & nbsp؛ في البرمجة - خطوة واحدة لعملية معالجة البيانات الدورية. & nbsp؛
غالبًا ما تستخدم الخوارزميات التكرارية في الخطوة الحالية (التكرار) نتيجة نفس العملية أو الإجراء المحسوب في الخطوات السابقة. & nbsp ؛ أحد الأمثلة على هذه الحسابات هو حساب علاقات التكرار. & nbsp ؛
مثال بسيط على القيمة العودية هو العامل: \ (N! = 1 \ cdot 2 \ cdot 3 \ cdot \ ... \ \ cdot N \) .
حساب القيمة في كل خطوة (التكرار) هو \ (N = N \ cdot i \) . & nbsp؛ عند حساب قيمة \ (N \) ، نأخذ القيمة المخزنة بالفعل & nbsp؛ \ (N \) . <ر ​​/>
يمكن أيضًا وصف مضروب الرقم باستخدام الصيغة المتكررة :
\ (\ start {equation *} n! = \ begin {cases} 1 & amp؛ \ text {n & lt؛ = 1،} \\ (n-1)! \ cdot n & amp؛ \ text {n & gt؛ 1.} \ end {cases} \ end {equation *} \)

قد تلاحظ أن هذا الوصف ليس أكثر من وظيفة تكرارية.
هنا السطر الأول ( \ (n & lt؛ = 1 \) ) هو الحالة الأساسية (شرط إنهاء العودية) والسطر الثاني هو الانتقال إلى الخطوة التالية. نبسب ؛ <الجسم>

دالة عاملة متكررة	الخوارزمية التكرارية
عامل التعريف (ن): إذا ن & GT. 1: عودة ن * عاملي (ن - 1) آخر: نبسب ؛ العودة 1	س = 1 بالنسبة لـ i في النطاق (1 ، n + 1): س = س * ط ؛

يجب أن يكون مفهوماً أن استدعاءات الوظائف تنطوي على بعض النفقات الإضافية ، لذا فإن حساب العوامل غير العودية سيكون أسرع قليلاً. & nbsp؛

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

مهمة في أبجدية لغة القبيلة "تومبا يومبا" أربعة أحرف: "K" ، "L" ، "M" و & quot؛ N & quot ؛. من الضروري أن تعرض على الشاشة جميع الكلمات المكونة من أحرف n التي يمكن بناؤها من أحرف هذه الأبجدية

المشكلة هي مشكلة القوة الغاشمة العادية التي يمكن اختزالها إلى مشكلة أصغر.
سنقوم باستبدال الأحرف بالتسلسل.
يمكن أن يكون الموضع الأول للكلمة واحدًا من الأحرف الأربعة للأبجدية ( K ، L ، M ، N ).
أولاً ، ضع الحرف & # 39 ؛ K & # 39 ؛ أولاً. بعد ذلك ، من أجل الحصول على جميع المتغيرات بالحرف الأول & # 39 ؛ K & # 39 ؛ ، تحتاج إلى تعداد جميع مجموعات الحروف الممكنة في n-1 المناصب نبسب ؛ و. (انظر الصورة)

وهكذا ، توصلنا إلى حل تعاودي: في حلقة ، انتقل من خلال جميع الأحرف الأولى الممكنة (وضع كل حرف من الحروف الأبجدية بدوره في المقام الأول) ولكل حالة ، قم ببناء كل "ذيول" ممكنة ؛ الطول n-1 .
نبسب ؛

تكرار تكراري للأحرف تحتاج إلى إيقاف العودية وإخراج الكلمة النهائية عندما يكون الجزء المتبقي فارغًا ( n = 0 ) ، أي تم تحديد كافة الأحرف بالفعل. & nbsp؛
سيبدو الإجراء العودي بالشكل التالي: & nbsp؛ <قبل> def TumbaWords (كلمة ، أبجدية ، ن): إذا ن & lt ؛ 1: طباعة (كلمة) يعود لـ c بالأبجدية: TumbaWords (كلمة + ج ، أبجدية ، ن - 1)