العودية
| English | العربية |
|---|---|
| Recursion/rɪˈkɜːʃn/ | العودية |
| base case/beɪs keɪs/ | الحالة الأساسية |
| recursive case/rɪˈkɜːsɪv keɪs/ | الحالة العودية |
| unwind/ʌnˈwaɪnd/ | التفكيك |
طريقة تستدعي نفسها
- التراجع (Recursion) هو عندما تقوم دالة باستدعاء نفسها لحل نسخة أصغر من نفس المشكلة.
- كل استدعاء تراجعي يحتاج جزأين: حالة أساسية وحالة تراجعية.
- الحالة الأساسية توقف التراجع — مدخل صغير تجيب عليه الدالة مباشرة.
- الحالة التراجعية تستدعي الدالة مرة أخرى على مدخل أصغر.
الحالة الأساسية
- بدون حالة أساسية، ستقوم الدالة باستدعاء نفسها لأبد — مما يسبب
StackOverflowError. - الحالة الأساسية تتعامل مع أصغر مدخل بدون استدعاء آخر.
- مثال:
factorial(0)تُرجع1مباشرة — لا مزيد من الاستدعاءات. - تحقق دائماً: هل تصل جميع المسارات في النهاية إلى الحالة الأساسية؟
الحالة التراجعية
- الحالة التراجعية تقوم ببعض العمل، ثم تستدعي نفسها على مدخل أصغر.
factorial(n)تُرجعn * factorial(n - 1)— المدخل يصغر بمقدار واحد في كل استدعاء.- كل استدعاء ينتظر أن يُرجع الاستدعاء الأصغر قبل أن يكتمل.
- تتراكم الاستدعاءات، تصل للحالة الأساسية، ثم تنحل للعودة للأعلى.
كيف تتراكم الاستدعاءات
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)تُرجع1؛ ثم تنحل المكدس:1, 1, 2, 6.- كل استدعاء يحتفظ بنسخته الخاصة من المعاملات حتى يرجع.
- تتبع التراجع يعني متابعة الاستدعاءات للأسفل، ثم الرجوعات للأعلى.
كل استدعاء تراجعي يحتاج لحالة أساسية توقفه — وكل استدعاء تراجعي يجب أن يتجه نَحْوَ تلك الحالة الأساسية (مدخل أصغر). ضيع الحالة الأساسية، أو استدعِ بنفس المدخل أو أكبر، وستستمر الدالة بالتراجع إلى ما لا نهاية حتى يحدث StackOverflowError. تابع عبر متابعة الاستدعاءات للأسفل نحو الحالة الأساسية، ثم الرجوع للأعلى.
مجموع sum(n) = 1 + 2 + … + n بالتراجع:
- الحالة الأساسية:
if (n == 0) return 0; - الحالة التراجعية:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
التراجع هو دالة تستدعي نفسها على مدخل أصغر. تحتاج إلى حالة أساسية (توقف مباشرة، لا مزيد من الاستدعاءات) وحالة تراجعية (تقوم بعمل بسيط، ثم تستدعي نفسها على مدخل أصغر). تتراكم الاستدعاءات للأسفل نحو الحالة الأساسية، ثم تنحل للعودة للأعلى. إذا ضيعت الحالة الأساسية ستحصل على StackOverflowError.
factorial(3) يُحلّ من الحالة الأساسية للأعلى
fact(0) تُرجع 1 (الحالة الأساسية)؛ كل أب يضرب: 1، 1، 2، 6.
الوظيفة العودية هي تلك التي...
العودية = دالة تستدعي نفسها.
الحالة الأساسية هي...
الحالة الأساسية توقف العودية.
العودية بدون حالة أساسية يمكن الوصول إليها تسبب...
تعود إلى الأبد حتى امتلاء المكدس.
يجب أن يحال الحالة العودية نفسها على...
يجب أن يتقلص كل استدعاء نحو الحالة الأساسية.
إذا كان factorial(0)=1 و factorial(n)=n*factorial(n-1)، فما هو factorial(3)؟
3 * 2 * 1 * 1 = 6.
يحافظ كل استدعاء عودي على نسخته الخاصة من معاملاته حتى يرجع.
المكدس يستدعي بشكل مستقل، ثم يُحل.