C++: التعاود

آخر تحديث: 2026-08-26

التعاود هو دالة تستدعي نفسها.

يبدو غريبًا — كيف يمكن لدالة أن تستدعي نفسها؟ ألن تدور إلى الأبد؟

طالما كتبت "شرط خروج" مناسب، يعمل التعاود بشكل صحيح — ويمكنه حل العديد من المشاكل الصعبة الكتابة بالحلقات.

1. ما هو التعاود؟

(1) 1.1 التعاود في الحياة اليومية

الفكرة الجوهرية للتعاود: تقسيم مشكلة كبيرة إلى مشاكل أصغر من نفس النوع، حتى تصبح المشكلة صغيرة بما يكفي لحلها مباشرة.

(2) 1.2 شرطان للتعاود

كل دالة تعاودية يجب أن تملك:

1. حالة الأساس: شرط الخروج من التعاود (الحالة الأبسط)
2. حالة التعاود: تقسيم المشكلة إلى مشاكل أصغر من نفس النوع

2. مثال تعاودي: المضروب

(1) 2.1 تعريف المضروب

n! = n × (n-1) × (n-2) × ... × 1

التعريف التعاودي:

n! = n × (n-1)! （recursive case）
0! = 1 （base case）

▶ مثال 1: حساب المضروب بالتعاود (صعوبة ⭐⭐)

#include <iostream>

// Recursive function：Calculate n factorial
long long factorial(int n) {
 // Base case
 if (n == 0) {
 return 1;
 }
 // Recursive case
 return n * factorial(n - 1);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

الخرج:

Please enter a non-negative integer: 
! = 

نتيجة التشغيل:

Please enter a non-negative integer: 5
5! = 120

(2) 2.2 عملية الاستدعاء التعاودي (n=5)

factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1 ← base case reached, starts returning
= 5 × 4 × 3 × 2 × 1
= 5 × 4 × 3 × 2
= 5 × 4 × 6
= 5 × 24
= 120

💡 نقطة مهمة: أثناء الاستدعاء التعاودي، الدالة تتوقف عند السطر return n * factorial(n-1);، منتظرة factorial(n-1) لإرجاع نتيجته، ثم تحسب n * result.

3. مثال تعاودي: متتالية فيبوناتشي

(1) 3.1 تعريف متتالية فيبوناتشي

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n ≥ 2）

المتتالية: 0، 1، 1، 2، 3، 5، 8، 13، 21، ...

▶ مثال 2: حساب أعداد فيبوناتشي بالتعاود (صعوبة ⭐⭐)

#include <iostream>

int fibonacci(int n) {
 // Base case
 if (n == 0) {
 return 0;
 }
 if (n == 1) {
 return 1;
 }
 // Recursive case
 return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

الخرج:

Please enter a non-negative integer: 
F() = 

نتيجة التشغيل:

Please enter a non-negative integer: 10
F(10) = 55

💡 نصيحة: هذا التنفيذ التعاودي غير فعال جدًا (يعيد حساب العديد من القيم بشكل متكرر). لاحقًا ستتعلم كيفية تحسينه بالحلقات أو الحفظ.

4. التعاود مقابل الحلقات

(1) 4.1 المقارنة

(2) 4.2 إعادة كتابة المضروب بحلقة

#include <iostream>

long long factorial(int n) {
 long long result = 1;
 for (int i = 1; i <= n; i++) {
 result *= i;
 }
 return result;
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 std::cout << n << "! = " << factorial(n) << std::endl;
 
 return 0;
}

💡 نصيحة: إذا كان يمكن حل مشكلة بسهولة بحلقة، فضّل الحلقات. التعاود مناسب للمشاكل "التعاودية بطبيعتها" (مثل اجتياز الأشجار، الفرز السريع).

5. فخ التعاود: فيضان المكدس

(1) 5.1 ما هو فيضان المكدس؟

كل استدعاء دالة يشغل مساحة على مكدس الاستدعاءات. إذا ذهب التعاود عميقًا جدًا (مثل عشرات الآلاف من المستويات)، ينفد مكدس الاستدعاءات، مما يسبب فيضان المكدس.

#include <iostream>

void infiniteRecursion() {
 infiniteRecursion(); // ❌ No base case, infinite recursion
}

int main() {
 infiniteRecursion();
 return 0;
}

نتيجة التشغيل:

Segmentation fault (core dumped) // Linux

أو

Process finished with exit code -1073741571 // Windows: stack overflow

(2) 5.2 كيفية تجنب فيضان المكدس؟

1. تأكد من وجود حالة أساس، وأن حالة الأساس يمكن الوصول إليها بالتأكيد
2. تحكم بعمق التعاود (مثلًا، أعد الكتابة بحلقة)
3. استخدم تحسين التعاود الذيلي (ستُغطى لاحقًا، لكن ليس كل المترجمات تدعمه)

6. تطبيق: أبراج هانوي

▶ مثال 3: حل أبراج هانوي التعاودي (صعوبة ⭐⭐⭐)

المشكلة: هناك 3 أوتاد (A، B، C) وn أقراص. مبدئيًا، جميع الأقراص على الوتد A (الأصغر في الأعلى، الأكبر في الأسفل). انقل جميع الأقراص إلى الوتد C، مع تحريك قرص واحد فقط في كل مرة، ولا تضع أبدًا قرصًا أكبر فوق أصغر. أخرج الخطوات.

النهج التعاودي:

1. انقل n-1 قرصًا من A إلى B (باستخدام C)
2. انقل القرص رقم n من A إلى C
3. انقل n-1 قرصًا من B إلى C (باستخدام A)

#include <iostream>

void hanoi(int n, char from, char to, char aux) {
 if (n == 1) { // Base case：Only one disk
 std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
 return;
 }
 // Recursive case
 hanoi(n - 1, from, aux, to); // Move n-1 disks from source to auxiliary
 std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
 hanoi(n - 1, aux, to, from); // Move n-1 disks from auxiliary to target
}

int main() {
 int n;
 std::cout << "Please enter number of disks: ";
 std::cin >> n;
 
 std::cout << "========== Tower of Hanoi Steps ==========\n";
 hanoi(n, 'A', 'C', 'B');
 
 return 0;
}

الخرج:

Move disk 1 from  to 
Move disk  from  to 
Please enter number of disks: 
========== Tower of Hanoi Steps ==========

نتيجة التشغيل (n=3):

========== Tower of Hanoi Steps ==========
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

💡 نصيحة: الحل التعاودي لأبراج هانوي أنيق جدًا، لكن إذا حاولت كتابته بالحلقات، ستجده صعبًا جدًا. هذه هي قوة التعاود.

7. تحسين التعاود: الحفظ

(1) 7.1 المشكلة: التعاود الساذج غير فعال

دالة فيبوناتشي التعاودية السابقة تعيد حساب العديد من القيم:

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ...

fibonacci(2) تُحسب 5 مرات! عندما يكون n كبيرًا، الكفاءة منخفضة جدًا.

(2) 7.2 الحل: الحفظ

خزّن النتائج المحسوبة سابقًا وابحث عنها مباشرة في المرة القادمة.

#include <iostream>
#include <vector>

std::vector<long long> memo; // Memoization array

long long fibonacci(int n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 
 if (memo[n] != -1) { // If already calculated, return directly
 return memo[n];
 }
 
 memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // Calculate and store
 return memo[n];
}

int main() {
 int n;
 std::cout << "Please enter a non-negative integer: ";
 std::cin >> n;
 
 memo.resize(n + 1, -1); // Initialize memoization array
 
 std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
 
 return 0;
}

💡 نصيحة: أدخلت C++11 std::unordered_map، الذي يمكنه جعل الحفظ أكثر سهولة.

❓ أسئلة شائعة

📖 ملخص

• التعاود هو دالة تستدعي نفسها
• التعاود يجب أن يملك شرطين: حالة أساس (خروج) وحالة تعاود (استمرار)
• ميزة التعاود هي كود موجز؛ العيوب هي الكفاءة المنخفضة واحتمال فيضان المكدس
• للمشاكل سهلة الحل بالحلقات، فضّل الحلقات
• التعاود مناسب للمشاكل "التعاودية بطبيعتها"

📝 تمارين

1. أساسي (صعوبة ⭐): اكتب دالة تعاودية int sumDigits(int n) تحسب مجموع أرقام عدد صحيح.

Input: 123
Output: 1 + 2 + 3 = 6

(تلميح: حالة التعاود sumDigits(n) = n % 10 + sumDigits(n / 10)، حالة الأساس n == 0)

2. متوسط (صعوبة ⭐⭐): اكتب دالة تعاودية int power(int base, int exp) تحسب الأس أس exp.

Input: power(2, 5)
Output: 32

(تلميح: حالة التعاود power(b, e) = b * power(b, e-1)، حالة الأساس تُرجع 1 عندما e == 0)

3. تحدي (صعوبة ⭐⭐⭐): استخدم التعاود لحل مشكلة "صعود الدرج":
4. لنفترض أنك تحتاج لصعود n درجات، ويمكنك صعود درجة أو درجتين في المرة
5. كم عدد الطرق المختلفة للصعود؟
6. (تلميح: هذه نسخة أخرى من متتالية فيبوناتشي — f(n) = f(n-1) + f(n-2))
7. حسّن دالتك التعاودية بالحفظ

• الدالة التعاودية: تستدعي نفسها، تُحلل المشاكل ثم تدمج النتائج
• العناصر الثلاثة للتعاود: شرط الإنهاء، الاستدعاء التعاودي، دمج النتائج
• تعاود فيبوناتشي مثال كلاسيكي للمبتدئين
• التعاود مقابل الحلقات: التعاود كود موجز، الحلقات أداء أفضل
• التعاود الذيلي يمكن تحسينه بواسطة المترجم إلى حلقة

8. 🚀 الخطوة التالية

الآن بعد أن تعلمت التعاود، لنتابع إلى تحميل الدوال والمعلمات الافتراضية (الدرس 13) — تقنيات لجعل الدوال أكثر مرونة وسهولة في الاستخدام!

فريق Web-Tutorial التقني

منصة دروس برمجية يديرها عدة مطورين. كل درس يتم كتابته ومراجعته بواسطة مطورين متخصصين في المجال. نعمل على ضمان دقة وموثوقية المحتوى — إذا لاحظت أي مشكلة، فيرجى إخبارنا.

من نحن