الجلسة التطبيقية 8 (Recitation 8)

المصادر والنسبة والترخيص

المادة الأصلية: آنا بيل (Ana Bell)، MIT OpenCourseWare (MIT OCW)، معهد ماساتشوستس للتكنولوجيا، مقرر 6.100L: مقدمة في علوم الحاسوب والبرمجة باستخدام Python، خريف 2022 (Fall 2022).

• صفحة الجلسة الرسمية على OCW.

هذه ترجمة وتكييف عربي غير رسمي وفق رخصة CC BY-NC-SA 4.0: النسبة–غير التجاري–المشاركة بالمثل، ولا تعني اعتمادًا أو تأييدًا من MIT أو MIT OCW. شروط الاستخدام والاستشهاد.

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

ملاحظة المترجم: المصدر ملف PDF. كان سطر التعليق في المثال الأخير مكتوبًا على سطرين بسبب التفاف النصّ، فُجمعا في تعليق واحد، وعوّضت علامات التنصيص المنحنية « “ ” » بعلامات ASCII حتى تعمل الشيفرة كما كُتبت.

المحاضرة المرتبطة

تُرافق هذه الجلسة التطبيقية المحاضرة 16: الاستدعاء الذاتي على غير الأعداد (Recursion on Non-Numerics). ويعرض ملخّصها الاستدعاء الذاتي (Recursion) كما في المحاضرتين 15 و16.

تذكيرات (Reminders)

6.100L، الجلسة التطبيقية 8 — 4 نوفمبر 2022.

• مسابقة MQ8 يوم الاثنين 11/7.
• التسليم المرحلي في منتصف مجموعة المسائل PSET 4 مستحقّ الساعة 9 مساءً يوم الأربعاء 11/9.

المحاضرتان 15 و16: الاستدعاء الذاتي (Recursion)

ما هو الاستدعاء الذاتي (What is Recursion)؟

• طريقة برمجية تُستعمل غالبًا بدلًا من التكرار (iteration).
• من الناحية الخوارزمية، طريقة لتصميم الحلول بمبدأ «اقسم وغلب» (divide-and-conquer) — أي تحويل المسألة إلى نسخة أبسط من المسألة نفسها.
• من الناحية الدلالية، تقنية برمجية تستدعي فيها الدالة نفسها (لكن إلى أجل غير مميّد).
• إن لاحظت أنّك تحلّ المسألة نفسها مرارًا، فقد يكون استعمال الاستدعاء الذاتي أسهل.

علامات تدلّنا على استعمال الاستدعاء الذاتي

• ندرك أنّ أمامنا مسألة نحلّها عدّة مرّات.
• عدد التكرارات المطلوبة غير معروف.
• نريد حلًّا يبدو «أجمل» من الحل التكراري.

أمثلة على مهام يمكن أن تستعمل الاستدعاء الذاتي

• فيبوناتشي (Fibonacci).
• أبراج هانوي (Towers of Hanoi).
• المتتاليات (مثل الهندسية والحسابية إلخ…).
• ضرب أو جمع أو طرح متتاليات.

البنية العامة للاستدعاء الذاتي (General Recursive Structure)

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

يتكوّن برنامج استدعاء ذاتي عامّ من جزأين:

1. الحالة الأساس (Base Case)

• حين تصل إلى حالة بسيطة يمكن حلّها.
• يجب أن تصل إلى هذه الحالة دائمًا، وإلا فقد حصلت على استدعاء ذاتي لا نهائي.

مثلًا:

if a == 1:
    return 1
elif a == 0:
    return 0

2. الحالة الاستدعائية (Recursive Case)

• فكّر: كيف يمكنني تقليل المسألة في هذه الخطوة؟
• عادةً نستدعي دالتنا بمدخلات تجعل مسألتنا بسيطة أو أصغر.

مثلًا:

recurse(a-1) # -2 is our modification to "simplify" the problem.