الاستدعاء الذاتي للمبتدئين: التوقف وتصغير المسألة وعودة النتيجة

ما هو الاستدعاء الذاتي؟

كتابة دالة تستدعي نفسها سهلة؛ الأهم شرح لماذا تتوقف وكيف تستخدم النتيجة الصغيرة لبناء الإجابة الأصلية.

تتبع جمعًا صغيرًا

لعدد غير سالب n، يمكن وصف المجموع من 1 إلى n بأنه n مضافًا إلى المجموع حتى n - 1. وعند الصفر يكون المجموع صفرًا. المثال يستخدم القيمة الثابتة 5 ويعطي 15.

#include <stdio.h>

/* Teaching example: called only with the fixed input 5. */
int sum_to(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main(void) {
    printf("%d\n", sum_to(5));
    return 0;
}

أثناء العودة نحصل على 1 ثم 3 ثم 6 في هذا التتبع الأصغر. ومع 5 تمتد نفس الفكرة حتى 15.

لماذا تتوقف الدالة؟

القيمة غير السالبة تقل واحدًا في كل مرة حتى الصفر. نفحص حالة التوقف قبل الطرح التالي، فلا يتحول الصفر إلى قيمة unsigned كبيرة بسبب الالتفاف.

هذا مثال تعليمي صغير، لا واجهة تقبل أي إدخال. القيم الكبيرة قد تتجاوز نوع النتيجة أو تستهلك مساحة استدعاءات كبيرة. الاستخدام العام يحتاج حدودًا واضحة أو طريقة أخرى.

احسب المساحة غير الظاهرة

كل استدعاء نشط يحتفظ بحالته حتى تعود الدالة الأصغر. هذا المثال الخطي يستخدم O(n) من مساحة مكدس الاستدعاءات في النموذج المعتاد، وينفذ O(n) استدعاء.

قصر جسم الدالة لا يعني ثبات الذاكرة. ولا تفترض أن المترجم سيزيل الاستدعاءات؛ ما زالت هناك عملية جمع بعد عودة النتيجة.

هل الحلقة أفضل؟

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

الاستدعاء الذاتي ليس أفضل دائمًا ولا أسوأ دائمًا. يصبح طبيعيًا عندما يكون بناء المسألة ذاتيًا مثل المرور على فروع شجرة.

تمرين

ارسم الاستدعاءات والعودة عند n = 4، والناتج 10. حدد حالة التوقف والعمليات التي تنتظر عودة النتائج.

ثم اشرح ماذا يحدث لو حذفت حالة التوقف. ابدأ بأمثلة صغيرة ومحدودة قبل الانتقال إلى الأشجار والخوارزميات الأكبر.