ما معنى recurrence equations ولماذا تُحيلك إلى recurrence relation؟

إذا صادفت في قاموس أو مرجع للخوارزميات عبارة «recurrence equations: see recurrence relation»، فالمقصود بسيط: المصطلحان مترادفان تمامًا، والعبارة مجرد إحالة قاموسية تقول لك «ابحث عن المعنى تحت مدخل العلاقة التكرارية». أي أن «معادلة التكرار» و«العلاقة التكرارية» اسمان لنفس الشيء، والمرجع يفضّل توحيد الشرح في مكان واحد بدلًا من تكراره. فما هذا الشيء الذي يشيران إليه؟ إنه معادلة رياضية تُعرّف قيمة دالة عند مدخلٍ ما بدلالة قيمها عند مدخلات أصغر، ونستخدمها أساسًا لحساب زمن تنفيذ الخوارزميات العودية (recursive).

لماذا تظهر عبارة «see recurrence relation»؟

القواميس التقنية تتبع أسلوب المعاجم: تختار مصطلحًا واحدًا رئيسيًا يحمل الشرح الكامل، وتجعل مرادفاته مجرد إحالات إليه. لذلك عندما تقرأ «see X» فأنت لا تفوّت شيئًا، بل تُوجَّه إلى الصيغة القياسية للمصطلح. المصطلح المعتمد هنا هو recurrence relation (العلاقة التكرارية)، وما عداه (recurrence equation، أو recurrence اختصارًا) مجرد تسميات دارجة له. هذه ملاحظة مهمة عند البحث: اكتب "recurrence relation" لتصل إلى الشروح الأوفى.

ما هي العلاقة التكرارية بالضبط؟

هي معادلة تربط الحدّ رقم n بالحدود التي تسبقه. أشهر مثال خارج البرمجة هو متتالية فيبوناتشي:

F(n) = F(n-1) + F(n-2)، مع الشرطين الابتدائيين F(0) = 0 وF(1) = 1.

لاحظ أن أي علاقة تكرارية تحتاج حالة أساس (base case) توقف الاستدعاء، وإلا استمرّ إلى ما لا نهاية. وهذه الحالة الأساس هي نفسها التي تمنع الدالة العودية في شيفرتك من الدوران الأبدي وامتلاء الذاكرة (stack overflow).

أين نستخدمها في تحليل الخوارزميات؟

عندما تستدعي خوارزمية نفسها على جزء أصغر من المدخل، يصبح زمنها الكلي معبَّرًا عنه بعلاقة تكرارية. نكتب عادةً T(n) لزمن معالجة مدخل حجمه n، ثم نفكّكه. إليك أشهر الأنماط:

• البحث الثنائي: يقسم القائمة نصفين ويكمل في نصف واحد: T(n) = T(n/2) + O(1) ← الناتج O(log n).
• الفرز بالدمج (merge sort): يقسم المدخل نصفين ويعالج الاثنين ثم يدمج: T(n) = 2T(n/2) + O(n) ← الناتج O(n log n).
• مسح خطّي عودي (مثل حساب المضروب): T(n) = T(n-1) + O(1) ← الناتج O(n).
• فيبوناتشي الساذج بلا حفظ: T(n) = T(n-1) + T(n-2) + O(1) ← ينفجر أُسّيًا O(2^n) تقريبًا، وهذا سبب بطئه الشهير.

طرق حلّ العلاقة التكرارية

الهدف من «الحل» هو تحويل الصيغة العودية إلى صيغة مغلقة (closed form) أو رتبة نمو صريحة مثل O(n log n). توجد ثلاث طرق شائعة، ولكل منها موضعها:

الطريقة	الفكرة باختصار	الأنسب لـ	الحذر منه
شجرة التكرار	ارسم مستويات الاستدعاء واجمع تكلفة كل مستوى	تكوين حدس سريع عن aT(n/b)+f(n)	الجمع الخاطئ لعدد المستويات
التعويض (الاستقراء)	خمّن الحل ثم أثبته بالاستقراء الرياضي	تأكيد إجابة تظنّها صحيحة	نسيان إثبات ثابت الحدّ
مبرهنة الأساس	طبّق قاعدة جاهزة بمقارنة f(n) بـ n^(log_b a)	معادلات القسمة والغلبة القياسية	استخدامها خارج شروطها

مبرهنة الأساس (Master Theorem) — الأداة التي أغفلها كثيرون

هذه أسرع طريقة عمليًا لخوارزميات «فرّق تسُد» على الصورة T(n) = aT(n/b) + f(n)، حيث a عدد الاستدعاءات وb معامل تصغير المدخل. قارن f(n) بالمقدار n^(log_b a):

1. إذا كان f(n) أصغر نموًّا، فالزمن Θ(n^(log_b a)).
2. إذا كانا متساويين، فالزمن Θ(n^(log_b a) · log n).
3. إذا كان f(n) أكبر نموًّا (مع شرط الانتظام)، فالزمن Θ(f(n)).

طبّقها على الفرز بالدمج: هنا a=2 وb=2، فيكون n^(log_2 2) = n، وهو مساوٍ لـ f(n)=O(n)، فنقع في الحالة الثانية والنتيجة Θ(n log n). مطابق تمامًا لما نعرفه.

خطأ شائع يقع فيه المبتدئون

كثيرون يخلطون بين T(n) = 2T(n/2) + O(n) وT(n) = 2T(n/2) + O(1). الفارق في الحدّ غير العودي f(n) يقلب النتيجة: الأول O(n log n) والثاني O(n). نصيحة عملية جرّبتها كثيرًا: قبل تطبيق أي مبرهنة، حدّد بدقة a وb وf(n) من الشيفرة نفسها؛ عدّ الاستدعاءات العودية داخل الدالة (a)، وكم يتقلّص المدخل في كل استدعاء (b)، وتكلفة العمل خارج الاستدعاءات (f(n)). أغلب الأخطاء تأتي من قراءة خاطئة لأحد هذه الثلاثة، لا من المبرهنة ذاتها.

الأسئلة الشائعة

هل «recurrence equation» و«recurrence relation» شيء واحد فعلًا؟ نعم، مترادفان في سياق الخوارزميات، والإحالة «see recurrence relation» تؤكد ذلك فحسب.

هل يجب أن أحفظ مبرهنة الأساس عن ظهر قلب؟ يكفي أن تفهم منطق المقارنة بين f(n) وn^(log_b a). احتفظ بالحالات الثلاث في متناولك وطبّقها، فهي تغطي معظم خوارزميات فرّق تسُد.

ما الفرق بين العلاقة التكرارية والدالة العودية في الشيفرة؟ العلاقة التكرارية وصف رياضي للزمن أو للقيمة، بينما الدالة العودية هي التنفيذ البرمجي. العلاقة أداة تحليل، والدالة أداة تطبيق، وكلاهما يشترك في مبدأ الاستدعاء الذاتي مع حالة أساس.

متى لا تنفع مبرهنة الأساس؟ حين لا يكون المدخل يتقلّص بنسبة ثابتة (مثل T(n)=T(n-1)+n)، أو حين لا يقع f(n) ضمن أنماطها. هنا استعمل شجرة التكرار أو التعويض بدلًا منها.