المهارات الرقمية، الصف الثاني عشر · الخوارزميات والبرمجة

ورقة مراجعة: الدالة الراجعة

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

أهم الأفكار

  1. فكرة الاستدعاء الذاتي نقسّم المسألة إلى مسألة أصغر لها الشكل نفسه، فتحلّ الدالّة الجزء الصغير باستدعاء نفسها. مثال: 5!=5×4!5!=5\times4! و 4!=4×3!4!=4\times3! وهكذا حتى 1!=11!=1. هذا يجعل البرنامج أبسط وأوضح أحيانًا من الدوران والتكرار.
  2. الحالة الأساسية لا غنى عنها يجب أن تحتوي كل دالّة راجعة على حالة أساسية تُرجِع قيمة دون استدعاء جديد. من دونها تستمرّ الاستدعاءات بلا نهاية. في الصيغة العامة: نفحص شرط الحالة الأساسية بـ `if` ونُرجِع قيمتها، وإلا (`else`) نُرجِع استدعاءً للدالّة نفسها بمُدخَل أصغر مثل `recursive_call(N - 1)`.
  3. المكدس وتتبّع الاستدعاءات عند كل استدعاء يُنشأ إطار جديد يوضع في المكدس. بعد الوصول إلى الحالة الأساسية يبدأ الرجوع: آخر إطار دخل هو أول من يكتمل، فتُحسب النتائج عائدةً إلى الاستدعاء الأول. الإطارات الكثيرة تستهلك الذاكرة وقد توقف البرنامج إن تجاوزت المتاح.
  4. مثال مجموع الأعداد الدالّة `sum_recursion(N)` تُرجِع NN + مجموع ما قبله، وحالتها الأساسية أن يكون `N` غير موجب فتُرجِع 00. عند إدخال 77 تُحسب النتائج بالترتيب 1,3,6,10,15,21,281, 3, 6, 10, 15, 21, 28 لأنّ الجمع يبدأ فعليًا بعد الوصول إلى الأساس. الدالّة الجاهزة `math.factorial()` تحسب المضروب لكنها ليست دالّة راجعة.
  5. متى نتجنّب الدالّة الراجعة قد تستهلك الدالّة الراجعة ذاكرة ووقتًا كبيرين، وبخاصة إن تكرّر حساب القيم نفسها كما في فيبوناتشي. لذلك نختارها حين تجعل الحلّ أوضح، ونتجنّبها في الأنظمة المشتركة أو الحسّاسة إن كان استهلاكها مفرطًا، وقد يكون الدوران (`for`, `while`) أبسط أو أخفّ أحيانًا.

مصطلحات الدرس

الدالّة الراجعة (Recursion)
دالّة تستدعي نفسها لحلّ مسألة، وتكرّر المهمة نفسها كل مرّة بمُدخَلات مختلفة.
الحالة الأساسية (Base Case)
الحالة التي لا تحتاج إلى استدعاء آخر فتُرجِع قيمة مباشرة وتوقف سلسلة الاستدعاءات.
مضروب العدد (Factorial)
حاصل ضرب العدد في كل الأعداد الصحيحة الموجبة الأصغر منه، ويُكتب n!n!، ومنه n!=n×(n−1)!n!=n\times(n-1)!.
المكدس (Stack)
بنية بيانات تعمل بمبدأ أنّ آخر ما يدخل هو أول ما يخرج.
الإطار (Stack Frame)
سجلّ يُنشأ لكل استدعاء ويحفظ مُعطياته ومتغيّراته المحلية والموضع الذي يُتابَع منه التنفيذ.

من اُدرُس: odrosai.com/ar/subjects/JO-DIGI-G12/units/1/digi12-u1_l4_recursion

بدك تتأكد إنك فاهم؟

سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.