الدرس 15: الاستدعاء الذاتي وbacktracking ومقدمة إلى DP

لقد وصلت إلى الدرس الختامي — أحسنت! لنبدأ بدمية ماتريوشكا: دمية بداخلها دمية أصغر، وصولاً إلى الصغيرة جداً التي لم تعد تُفتح. هذا بالضبط هو 'الاستدعاء الذاتي': دالة تستدعي نفسها على نسخة أصغر من المسألة نفسها، والدمية التي لا تُفتح هي 'الحالة الأساسية' التي توقف كل شيء. على هذه الفكرة يبني الدرس أدا

الاستدعاء الذاتي مثل الدمية الروسية المتداخلة: كل دمية تفتح دمية أصغر، حتى تصل إلى الصغيرة جداً التي لا تُفتح (الحالة الأساسية). backtracking هو تجربة مسار، وإذا كان طريقاً مسدوداً — إغلاقه وتجربة آخر. memoization هو تدوين الإجابات التي حسبتها من قبل على ورقة، كي لا تحسبها مرة أخرى.

الاستدعاء الذاتي وbacktracking: الاستدعاء الذاتي: دالة تستدعي نفسها على مسألة فرعية أصغر حتى الوصول إلى حالة أساسية. Backtracking: جرّب خياراً، انزل بالاستدعاء الذاتي، وتراجع عن الخيار لاستكشاف كل الاحتمالات.
الحالة الأساسية: الشرط الذي يوقف الاستدعاء الذاتي ويعيد إجابة مباشرة دون استدعاء آخر — بدونه لا ينتهي الاستدعاء الذاتي أبداً.
memoization (تخزين النتائج): تخزين نتائج المسائل الفرعية في cache (مثلاً في dict) كي لا يُعاد حسابها — يتجنّب العمل المتكرر ويمكن أن يسرّع التنفيذ بشكل كبير (مثلاً Fibonacci الساذج من O(2ⁿ) إلى O(n)).