التراجع: الحالة الأساسية والحالة المتراجعة
تحتاج هذه الصفحة إلى متصفح حديث (يدعم SharedArrayBuffer). يرجى تحديث Chrome أو Edge أو Firefox أو Safari إلى أحدث إصدار.
طريقة تستدعي نفسها
- الاستدعاء الذاتي هو عندما تقوم الطريقة باستدعاء نفسها لحل جزء أصغر من نفس المشكلة.
- في امتحان AP CSA، تتتبع الاستدعاء الذاتي في الغالب (تابع الاستدعاءات يدويًا). كتابة طرق استدعاء ذاتي صغيرة تساعدك على التتبع بشكل جيد.
- كل طريقة استدعاء ذاتي تحتاج جزأين: حالة أساسية وحالة استدعاء ذاتي.
الحالة الأساسية والحالة المتراجعة
- الحالة الأساسية: أبسط إدخال، حيث تعيد إجابة بدون استدعاء نفسك. هذا يوقف الاستدعاء الذاتي.
- حالة الاستدعاء الذاتي: تستدعي نفس الطريقة بإدخال أصغر، ثم تبني الإجابة.
- بدون حالة أساسية، ستستدعي الطريقة نفسها إلى ما لا نهاية وتتسبب في انهيار ( overflow في المكدس ).
مثال: المضروب
factorial(n)يعنيn * (n-1) * ... * 1. على سبيل المثالfactorial(4) = 24.- الحالة الأساسية:
factorial(1)تساوي1. - الحالة التكرارية:
factorial(n)هيn * factorial(n - 1).
English
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
كيف تنحني الاستدعاءات
- كل استدعاء ينتظر انتهاء الاستدعاء الأصغر. ثم يقوم بالضرب والإرجاع.
- تتبع
factorial(3). تذهب الاستدعاءات لأسفل، ثم تعود الإجابات لأعلى.
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
مثال: المجموع حتى n
sumTo(n)يضيف1 + 2 + ... + n. على سبيل المثالsumTo(4) = 10.- الحالة الأساسية:
sumTo(0)هي0(لا يوجد ما يضاف). - الحالة التكرارية:
sumTo(n)هيn + sumTo(n - 1).
English
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
التكرار عبر مصفوفة
- يمكننا أيضاً استخدام التكرار مع مؤشر يتجه نحو النهاية.
- الحالة الأساسية: عندما يكون المؤشر خلف آخر عنصر، أرجع
0. - الحالة التكرارية: أضف
a[i]إلى مجموع الباقي،arraySum(a, i + 1).
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- لجمع المصفوفة بأكملها، ابدأ من الفهرس
0:arraySum(a, 0). - كل استدعاء يعالج قيمة واحدة ويثق بالاستدعاء التالي للباقي.
أخطاء شائعة
- يحتاج التكرار إلى حالة أساسية، وإلا سيُطلق StackOverflowError.
- يجب أن يتحرك كل استدعاء نحو الحالة الأساسية.
الآن جرب بنفسك
- كل مهمة تعطيك هيكلاً لطريقة مع TODO. اكتب الحالة الأساسية والحالة التكرارية.
- مختبر مخفي يستدعي طريقتك بقيم متعددة ويتحقق من النتيجة.
- استخدم Check answer لترجمة كودك مع الاختبارات المرفقة وعرض النتائج. ابقِ واجهات الفئة والطريقة كما هي موضحة في Starter.
استكشف
التراجع: الحالة الأساسية + الحالة المتراجعة
الأدوات تنقسم حتى الحالة الأساسية، ثم تعود الإجابات للأعلى.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل factorial(int n) لإرجاع n * (n-1) * ... * 1 باستخدام التراجع. استخدم حالة أساسية لـ n <= 1. يختبر الفاحس عدة قيم.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أكمل sumTo(int n) لإرجاع 1 + 2 + ... + n باستخدام التراجع. استخدم حالة أساسية لـ n <= 0. يختبر الفاحس عدة قيم.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 4/5 · 280 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
أتمم arraySum(int[] a, int i) بحيث تُرجع مجموع a[i] إلى النهاية، باستخدام الاستدعاء الذاتي. الحالة الأساسية: عندما يكون i بعد آخر موقع، أرجع 0. يختبر الفاحص عدة مصفوفات.
اضغط تشغيل لرؤية المخرجات هنا.