العودية
مُقدَّم| 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) unwinds from the base case up
fact(0) returns 1 (base case); each parent multiplies: 1, 1, 2, 6.
A recursive method is one that...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Recursion = a method calling itself.
The base case is...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The base case stops the recursion.
A recursion with no reachable base case causes...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
It recurses forever until the stack overflows.
The recursive case must call itself on...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Each call must shrink toward the base case.
If factorial(0)=1 and factorial(n)=n*factorial(n-1), what is factorial(3)?
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
3 * 2 * 1 * 1 = 6.
Each recursive call keeps its own copy of its parameters until it returns.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Calls stack independently, then unwind.