العودية – مكدس الاستدعاءات وشجرة الاستدعاءات

ماذا تعرض

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

طريقة الاستخدام

اختر «الدالة» واضبط n (أو «الهدف» في البحث الثنائي). اضغط «خطوة» لتنفيذ استدعاء أو إرجاع واحد في كل مرة، و«رجوع» للتراجع خطوة، أو «تشغيل» للعرض تلقائيًا وفق «السرعة» المختارة. راقب الشيفرة ومكدس الاستدعاءات وشجرة الاستدعاءات، واضغط عقدة لرؤية تفاصيلها. فعّل «حفظ النتائج» مع فيبوناتشي، أو ألغِ «تضمين الحالة الأساسية» لترى فيض المكدس. وقارن بنسخة الحلقة في الأسفل.

المعاملات القابلة للتغيير

• الدالة العودية المضروب n!, أعداد فيبوناتشي, مجموع قائمة, البحث الثنائي, لغز الأبراج (نقل الأقراص), الفرز بالدمج
• n (حجم المسألة) 0–8
• القيمة المطلوبة (البحث الثنائي) 0–100
• حفظ النتائج (فيبوناتشي)
• تضمين الحالة الأساسية
• اللغة Python, شبه الشيفرة
• سرعة التشغيل 0.5–10 خطوة/s

أسئلة للاستكشاف

1. كم مرة تُستدعى fib(2) عند حساب fib(6) دون حفظ النتائج، وكم مرة مع حفظها؟
2. ما أقصى عمق للمكدس في factorial(5)، وكم من المكدس تحتاج نسخة الحلقة؟
3. لماذا يسبب حذف الحالة الأساسية فيض المكدس بدلًا من إجابة خاطئة؟