الدرس 7 من 10
تلخيص درس الدالة الراجعة
الدرس باختصار
الدالّة الراجعة (Recursion) دالّة تحلّ المسألة بأن تستدعي نفسها مرّات عدّة، وفي كل استدعاء تعمل العمل نفسه على مُدخَل أصغر. نتعلّم هنا الحالة الأساسية (Base Case) التي توقف الاستدعاءات، وكتابة دالّة راجعة في بايثون، وتتبّع المكدس (Stack) خطوة خطوة.
مصطلحات الدرس
- الدالّة الراجعة (Recursion)
- دالّة تستدعي نفسها لحلّ مسألة، وتكرّر المهمة نفسها كل مرّة بمُدخَلات مختلفة.
- الحالة الأساسية (Base Case)
- الحالة التي لا تحتاج إلى استدعاء آخر فتُرجِع قيمة مباشرة وتوقف سلسلة الاستدعاءات.
- مضروب العدد (Factorial)
- حاصل ضرب العدد في كل الأعداد الصحيحة الموجبة الأصغر منه، ويُكتب ، ومنه .
- المكدس (Stack)
- بنية بيانات تعمل بمبدأ أنّ آخر ما يدخل هو أول ما يخرج.
- الإطار (Stack Frame)
- سجلّ يُنشأ لكل استدعاء ويحفظ مُعطياته ومتغيّراته المحلية والموضع الذي يُتابَع منه التنفيذ.
أهم الأفكار
فكرة الاستدعاء الذاتي
نقسّم المسألة إلى مسألة أصغر لها الشكل نفسه، فتحلّ الدالّة الجزء الصغير باستدعاء نفسها. مثال: و وهكذا حتى . هذا يجعل البرنامج أبسط وأوضح أحيانًا من الدوران والتكرار.
الحالة الأساسية لا غنى عنها
يجب أن تحتوي كل دالّة راجعة على حالة أساسية تُرجِع قيمة دون استدعاء جديد. من دونها تستمرّ الاستدعاءات بلا نهاية. في الصيغة العامة: نفحص شرط الحالة الأساسية بـ `if` ونُرجِع قيمتها، وإلا (`else`) نُرجِع استدعاءً للدالّة نفسها بمُدخَل أصغر مثل `recursive_call(N - 1)`.
المكدس وتتبّع الاستدعاءات
عند كل استدعاء يُنشأ إطار جديد يوضع في المكدس. بعد الوصول إلى الحالة الأساسية يبدأ الرجوع: آخر إطار دخل هو أول من يكتمل، فتُحسب النتائج عائدةً إلى الاستدعاء الأول. الإطارات الكثيرة تستهلك الذاكرة وقد توقف البرنامج إن تجاوزت المتاح.
مثال مجموع الأعداد
الدالّة `sum_recursion(N)` تُرجِع + مجموع ما قبله، وحالتها الأساسية أن يكون `N` غير موجب فتُرجِع . عند إدخال تُحسب النتائج بالترتيب لأنّ الجمع يبدأ فعليًا بعد الوصول إلى الأساس. الدالّة الجاهزة `math.factorial()` تحسب المضروب لكنها ليست دالّة راجعة.
متى نتجنّب الدالّة الراجعة
قد تستهلك الدالّة الراجعة ذاكرة ووقتًا كبيرين، وبخاصة إن تكرّر حساب القيم نفسها كما في فيبوناتشي. لذلك نختارها حين تجعل الحلّ أوضح، ونتجنّبها في الأنظمة المشتركة أو الحسّاسة إن كان استهلاكها مفرطًا، وقد يكون الدوران (`for`, `while`) أبسط أو أخفّ أحيانًا.
أمثلة محلولة
مثال 1: مضروب 5 بالاستدعاء الذاتي
دالّة `factorial(n)` تُرجِع عندما `n == 0` وإلا `n * factorial(n - 1)`. ما قيمة `factorial(5)`؟
اعرض الحل
- نكتب الاستدعاءات: `factorial(5) = 5 * factorial(4)` ثم `4 * factorial(3)` ثم `3 * factorial(2)` ثم `2 * factorial(1)` ثم `1 * factorial(0)`.
- `factorial(0)` هي الحالة الأساسية وقيمتها .
- نرجع إلى الخلف: ، ثم ، ثم ، ثم ، ثم .
الجواب:
مثال 2: مجموع الأعداد من 1 إلى 4
دالّة `sum_recursion(N)` تُرجِع إن كان `N` ليس موجبًا، وإلا `N + sum_recursion(N - 1)`. ما قيمة `sum_recursion(4)`؟
اعرض الحل
- تُنشأ الاستدعاءات: `sum_recursion(4)` ثم `(3)` ثم `(2)` ثم `(1)` ثم `(0)`، والأخير يُرجِع ويُزال إطاره.
- عند الرجوع: `sum_recursion(1)` ، ثم `sum_recursion(2)` .
- ثم `sum_recursion(3)` ، ثم `sum_recursion(4)` .
الجواب:
مثال 3: متتالية فيبوناتشي
في الدالّة `fib(n)` الحالتان الأساسيتان `fib(0) = 0` و `fib(1) = 1`، وإلا `fib(n - 1) + fib(n - 2)`. احسب `fib(6)`.
اعرض الحل
- نحسب الحدود بالترتيب: `fib(2) = 1 + 0 = 1`، `fib(3) = 1 + 1 = 2`، `fib(4) = 2 + 1 = 3`.
- `fib(5) = 3 + 2 = 5`.
- `fib(6) = fib(5) + fib(4) = 5 + 3 = 8`. هنا يستدعي كل استدعاء استدعاءين، ولهذا قد يتكرّر الحساب.
الجواب:
مثال 4: عكس كلمة
الدالّة `reverse_string(s)` تُرجِع `s` إن كان طولها ، وإلا `s[-1] + reverse_string(s[:-1])`. ما ناتج `reverse_string("abc")`؟
اعرض الحل
- `s[-1]` هو آخر حرف و `s[:-1]` هو الكلمة دون آخر حرف.
- `reverse_string("abc") = "c" + reverse_string("ab")` ثم `"b" + reverse_string("a")` ثم `"a" + reverse_string("")`.
- الحالة الأساسية: النص الفارغ يُرجِع نفسه. نجمع عائدين: `"a"` ثم `"ba"` ثم `"cba"`.
الجواب: `cba`
أخطاء شائعة
نسيان الحالة الأساسية أو كتابتها بشرط لا يتحقق أبدًا.
ليش غلط: هذا يمنع الدالّة من الوصول إلى الحالة الأساسية أو من فهم آلية المكدس.
الصح: تستمر الاستدعاءات بلا نهاية وتمتلئ الذاكرة بالإطارات فيتوقف البرنامج. اكتب الحالة الأساسية أولًا وتأكّد أنّ كل استدعاء يقرّب المُدخَل منها، مثل `factorial(-5)` الذي لا يصل إلى أبدًا.
استدعاء الدالّة بالمُدخَل نفسه دون تغيير، مثل `linear_search(lst, target)` مع نسيان تمرير `index + 1`.
ليش غلط: هذا يمنع الدالّة من الوصول إلى الحالة الأساسية أو من فهم آلية المكدس.
الصح: يجب أن يتغيّر المُعامل في كل استدعاء ليقترب من الحالة الأساسية، مثل `N - 1` أو `index + 1` أو اقتطاع حرف.
الظن أنّ `math.factorial()` دالّة راجعة، أو أنّ نتيجة الاستدعاء تُحسب عند النزول إلى المكدس.
ليش غلط: هذا يمنع الدالّة من الوصول إلى الحالة الأساسية أو من فهم آلية المكدس.
الصح: `math.factorial()` دالّة جاهزة ليست راجعة. وفي الدالّة الراجعة تُحسب النتائج عند الرجوع بعد الوصول إلى الحالة الأساسية، وآخر إطار دخل المكدس هو أول من يخرج.
اختبر حالك
1. باستخدام الدالّة `sum_recursion(N)` من الأمثلة، ما قيمة `sum_recursion(5)` أي مجموع الأعداد من إلى ؟
اعرض الجواب
الجواب:
، والحالة الأساسية تُرجِع .
2. باستخدام `fib(n)` ذات الحالتين الأساسيتين `fib(0)=0` و `fib(1)=1`، ما قيمة `fib(7)`؟
اعرض الجواب
الجواب:
المتتالية: ، فـ `fib(7) = fib(6) + fib(5) = 8 + 5 = 13`.
3. ما قيمة `factorial(6)` إذا كانت الدالّة `factorial(n)` تُرجِع عندما وإلا `n * factorial(n - 1)`؟
اعرض الجواب
الجواب:
.
4. ما ناتج `reverse_string("map")` علمًا أنّ الدالّة تُرجِع `s[-1] + reverse_string(s[:-1])` والحالة الأساسية النص الفارغ؟ اكتب النص دون علامات اقتباس.
اعرض الجواب
الجواب: `pam`
نأخذ الحرف الأخير ثم نعكس الباقي: `p` ثم `a` ثم `m`، فيصبح `pam`.
جاهز تتدرّب؟
19 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 19 سؤال من هالدرس مجانًا