التكرار الذاتي

طريقان إلى نفس الفكرة

قبل أن تبدأ

الفكرة الجوهرية: حالة أساس + استدعاء ذاتي

لفهم التكرار فهمًا حقيقيًا، يجب أن تراه كأسلوب تعريف لحل المسألة لا كأسلوب حل خطوة بخطوة: الدالة التكرارية لا "تشرح" كيف تُحل المسألة، بل تُعرّف حلّها بالاستناد إلى حلّ نسخة أصغر منها، تمامًا كما يُعرَّف العدد الطبيعي رياضيًا بالاستقراء (induction): حالة أساس واحدة (عادة الصفر) زائد قاعدة تبني كل عدد من العدد الذي قبله. وبالضبط كما يحتاج البرهان بالاستقراء ركيزتين لا يكتمل بدونهما، أي دالة تكرارية (recursive) صحيحة تحتاج ركيزتين لا غنى عنهما:

1حالة الأساس (Base Case)

هي الحالة الأبسط التي تُحل مباشرة دون أي استدعاء إضافي، نظير حالة "n = 0" في برهان الاستقراء. وظيفتها الحقيقية مزدوجة: فهي أولًا نقطة التوقف الفعلية التي تمنع الاستدعاءات من الاستمرار إلى ما لا نهاية؛ وهي ثانيًا المصدر الوحيد لقيمة "جاهزة" يمكن البناء عليها، كل الاستدعاءات الأخرى لا تملك قيمة جاهزة، بل تنتظر قيمة استدعاء أصغر منها. لو كانت حالة الأساس غائبة تمامًا، أو مكتوبة بشرط لا يتحقق أبدًا لمدخل معيّن (مثل استدعاء factorial(-3) على دالة تتحقق فقط من n <= 1 بينما المُدخل سالب ويتباعد عن الصفر بدل أن يقترب منه)، فستستمر الاستدعاءات بلا توقف: كل استدعاء ينتظر نتيجة استدعاء لم يحدث بعد، وتتكدّس الإطارات في الذاكرة حتى تستهلك المساحة المحجوزة لمكدس الاستدعاءات بالكامل، غالبًا 8 ميجابايت لكل خيط تنفيذ (thread) بشكل افتراضي على أنظمة Linux، فينهار البرنامج بخطأ Stack Overflow.

2الخطوة التكرارية (Recursive Step)

هي الاستدعاء الذي تقوم به الدالة لنفسها، لكن مُدخله ليس "أصغر" بمعنى حدسي غامض فقط، يجب أن يكون أصغر بمقياس محدد يضمن الوصول لحالة الأساس بعد عدد خطوات منتهٍ. في factorial هذا المقياس هو قيمة n نفسها: كل استدعاء يُمرّر n - 1‏، فتقل القيمة بمقدار واحد بالضبط في كل مرة، ولأنه لا توجد سلسلة لا نهائية من الأعداد الصحيحة بين أي عدد موجب والصفر، فالوصول لـ n <= 1 مضمون رياضيًا. الخطأ الدقيق الذي يسقط فيه كثيرون هو كتابة استدعاء "يبدو" تكراريًا شكليًا لكنه لا يُقرّب المُدخل فعليًا من حالة الأساس، كاستدعاء الدالة بنفس القيمة n بدل n - 1 (خطأ طباعي سهل الحدوث)، أو بقيمة تتباعد عن حالة الأساس بدل الاقتراب منها؛ في كل هذه الحالات الكود "تكراري" في الشكل فقط، لكنه عمليًا حلقة لا نهائية لا تختلف جوهريًا عن غياب حالة الأساس تمامًا.

شكل 1، كل استدعاء ينتظر نتيجة الاستدعاء الذي بعده قبل أن يكمل حسابه الخاص؛ هذا هو سبب وجود "مرحلتين": النزول (كل استدعاء يستدعي التالي) ثم الصعود (كل استدعاء يُرجع قيمته للي استدعاه).

الرسمان السابقان يوضحان لماذا تحتاج الركيزتين معًا لا كل واحدة بمفردها: حالة الأساس وحدها بلا خطوة تكرارية لا تحل إلا الحالة البسيطة فقط؛ والخطوة التكرارية وحدها بلا حالة أساس لا تتوقف أبدًا. والضمان الحقيقي للصحة هنا يشبه تمامًا برهان الاستقراء الرياضي: إذا صحّت حالة الأساس، وإذا كانت كل خطوة تكرارية تبني النتيجة الصحيحة بافتراض أن الاستدعاء الأصغر منها صحيح (وهذا بالضبط ما يسمى "الافتراض الاستقرائي")، فالنتيجة صحيحة لكل مُدخل ممكن، وهذا ما يحدث حرفيًا في factorial(n)‏: بافتراض أن factorial(n - 1) يُرجع القيمة الصحيحة، فإن n * factorial(n - 1) هي بالضرورة القيمة الصحيحة لـ factorial(n)‏.

أنماط التكرار المختلفة

3التكرار الذيلي (Tail Recursion)

الاستدعاء التكراري هو آخر عملية في الدالة، لا يوجد شيء ينتظر بعد عودته. الفرق الحاسم: بما أنه لا توجد عملية حسابية معلقة بعد الاستدعاء، فبعض المترجمات (compilers) تستطيع تحويله لحلقة عادية تلقائيًا (tail call optimization)، فتتجنب تكدّس الإطارات تمامًا. في C، مترجم GCC مع -O2 يفعل ذلك غالبًا.

4التكرار الشجري (Tree Recursion)

الدالة تستدعي نفسها أكثر من مرة في كل استدعاء، كحساب فيبوناتشي: fib(n-1) + fib(n-2)‏. النتيجة شجرة استدعاءات تتفرع بسرعة هائلة، وعدد الاستدعاءات ينمو أسيًّا (exponentially) مع حجم المُدخل، هذا النمط يحتاج تقنيات مثل التذكّر (memoization) لتجنب إعادة حساب نفس القيم آلاف المرات.

مقارنة: التكرار الذاتي مقابل الحلقات التكرارية

كيف يعمل، خطوة بخطوة: مكدس الاستدعاءات (Call Stack)

كل استدعاء دالة، تكراري أو غير تكراري، يحصل على "إطار" (stack frame) خاص به في الذاكرة، يُنشأ تلقائيًا عند الدخول للدالة ويُزال تلقائيًا عند الخروج منها. هذا الإطار ليس صندوقًا مجردًا: فعليًا يحتوي عنوان العودة (return address)، أي مكان الكود الذي يجب أن ينتقل له المعالج بعد انتهاء هذا الاستدعاء تحديدًا، بالإضافة إلى نسخة هذا الاستدعاء الخاصة من مُدخلاته (parameters) ومتغيراته المحلية (local variables)، وغالبًا مؤشرًا محفوظًا لإطار الاستدعاء الذي قبله (saved base/frame pointer) يُستخدم لإيجاد ذلك الإطار السابق بسرعة عند العودة. مكدس الاستدعاءات بأكمله مساحة ذاكرة محجوزة سلفًا بحجم ثابت لكل خيط تنفيذ، غالبًا 8 ميجابايت افتراضيًا على أنظمة Linux، وكل استدعاء جديد "يدفع" (push) إطاره فوق الإطار السابق، فيتحرك مؤشر المكدس (stack pointer) تلقائيًا ليحجز المساحة اللازمة. في التكرار، هذه الإطارات تتكدّس فوق بعضها بلا أي استثناء لكون الدالة نفسها، لأن كل استدعاء لـ factorial(n)‏، حتى لو حمل نفس اسم الدالة بالضبط، هو كيان مستقل تمامًا بعنوان عودة ونسخة n خاصة به لا يشاركها أي استدعاء آخر:

شكل 2، كل مستوى في هذا الرسم إطار مستقل تمامًا في الذاكرة: يحمل نسخته الخاصة من n وعنوان العودة الذي سيُرجع له قيمته بالضبط؛ الإطارات الأربعة موجودة معًا في الذاكرة في آنٍ واحد فقط عند الوصول لحالة الأساس: وهذا العمق المتزامن هو تحديدًا ما قد يستهلك المساحة المحدودة المحجوزة للمكدس إن تكرر آلاف المرات.

int factorial(int n)
{
    if (n <= 1)          /* حالة الأساس */
        return (1);
    return (n * factorial(n - 1));  /* الخطوة التكرارية */
}

شكل 3، لاحظ أن الضرب n * factorial(n - 1) لا يمكن حسابه إلا بعد أن يُرجع الاستدعاء الداخلي قيمته: وهذا بالضبط ما يجبر المكدس على الانتظار قبل الانحلال.

مثال تطبيقي: مجموع عناصر مصفوفة تكراريًا

نفس النمط (حالة أساس + خطوة تكرارية) ينطبق على أي مسألة قابلة للتفكيك لنسخة أصغر من نفسها:

int sum_array(int *arr, int size)
{
    if (size == 0)                  /* حالة الأساس: مصفوفة فارغة */
        return (0);
    return (arr[0] + sum_array(arr + 1, size - 1));
}

كل استدعاء يأخذ "بقية" المصفوفة (بتحريك المؤشر خطوة وتقليل الحجم)، حتى تصل لحجم صفر فتتوقف. المصفوفة نفسها لا تُنسخ أبدًا: arr + 1 هو تعبير حسابي على المؤشر (pointer arithmetic) يُحرّك المؤشر بمقدار عنصر واحد من نوع int (أي 4 بايتات غالبًا)، فيُعيد إشارة جديدة تبدأ عند العنصر الثاني من نفس المصفوفة في الذاكرة، وليس مصفوفة منفصلة. في الوقت نفسه، size - 1 يُخبر الاستدعاء الجديد أن "عالمه" الآن أصغر بعنصر واحد. تحريك المؤشر للأمام وتقليل الحجم معًا هما ما يضمنان أن كل استدعاء يرى جزءًا أصغر فعليًا من نفس المصفوفة، فتصل السلسلة لحجم صفر (حالة الأساس) بعد عدد خطوات محدود يساوي طول المصفوفة تمامًا.

شكل 4، كل استدعاء يستقبل مؤشرًا متحركًا خطوة واحدة للأمام (arr+1، arr+2...) وحجمًا أصغر بواحد في كل مرة؛ بما أن الحجم يقل باستمرار بخطوات ثابتة، فالوصول لحجم صفر (حالة الأساس) مضمون بعد عدد محدود من الاستدعاءات، بالضبط كما حدث مع factorial في الرسم السابق.

خرافة مقابل حقيقة

تطبيقات عملية

تعمّق: تصميم التكرار الذاتي وتكلفته

فهمنا آلية مكدس الاستدعاءات؛ هنا نحوّل الفهم إلى منهج تصميم: كيف تقرر أن مسألة تُحلّ بالتكرار الذاتي، وكيف تصمّمه، وكيف تعرف أنه تكلفة لا تستحق.

وصفة تصميم: أربعة أسئلة

شكل 5، وصفة تصميم التكرار الذاتي: الثقة في الاستدعاء الأصغر هي سر البساطة.

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

أنماط شائعة

قيدا "لا حلقات ولا متغيرات ساكنة" يفرضان فكرة جميلة: كل الحالة يجب أن تنتقل عبر الوسائط وقيم الإرجاع. فإن احتجت لعدّاد، فاجعله وسيطًا إضافيًا، وغالبًا تغلّفه دالة أخرى تبدأ به من الصفر.

التكلفة: متى يصبح التكرار الذاتي سيئًا؟

لكل استدعاء إطار على المكدس يحمل الوسائط والمتغيرات المحلية وعنوان العودة. عمق N يعني ذاكرة تتناسب مع N، والمكدس محدود (غالبًا بضعة ميغابايتات على Linux)، فعمق كبير جدًا يسبب انهيارًا بفيض المكدس. وهناك تكلفة أخفى: التكرار الساذج قد يعيد حساب المسألة الفرعية نفسها مرارًا. مثال كلاسيكي هو متتالية فيبوناتشي المكتوبة بنداءين متفرعين: لحساب fib(5) يُحسب fib(3) مرتين و fib(2) ثلاث مرات، ويتضاعف العمل تقريبًا مع كل زيادة في المُدخل (نمو أسّي). الحل بحفظ النتائج السابقة (memoization) أو بالتحويل إلى حلقة.

شكل 6، شجرة استدعاءات فيبوناتشي الساذجة: العقد المكررة (fib(3) و fib(2)) هي العمل المهدور.

جرّب بنفسك

بطاقات مراجعة سريعة

تحقق من فهمك