רקורסיה: מקרה בסיס ומקרה רקורסיבי
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
שיטה הקוראת לעצמה
- רקורסיה היא כאשר שיטה קוראת לעצמה כדי לפתור חלק קטן יותר מאותו בעיה.
- במבחן AP CSA אתה בעיקר מעקב אחר רקורסיה (עוקב אחר הקריאות ביד). כתיבת שיטות רקורסיביות קטנות עוזרת לך לעקוב היטב.
- לכל שיטה רקורסיבית יש שני חלקים: מקרה בסיס ומקרה רקורסיבי.
מקרה בסיסי ומקרה רקורסיבי
- מקרה בסיס: הקלט הפשוט ביותר, שבו מחזיר תשובה ללא קריאה לעצמך. זה מעצור את הרקורסיה.
- מקרה רקורסיבי: אתה קורא לאותה שיטה עם קלט קטן יותר, ואז בונה את התשובה.
- ללא מקרה בסיס, השיטה קוראת לנצח ומגרושה (פלישת סטק).
דוגמה: פקטוריאל
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. כתוב את המקרה הבסיסי וגם את המקרה הרקורסיבי.
- Harness נסתר קורא למטהוד שלך עם ערכים שונים ובוחן את התוצאה.
- השתמשו ב-Check answer כדי לקמפיל את הקוד שלך עם הבדיקות הסופקות ולצפות בתוצאות. שמרו את ממשקי המחלקה והשיטה המוצגים בתחילת העבודה.
חקור
רקורסיה: מקרה בסיס + מקרה רקורסיבי
קריאות מתפצלות עד מקרה בסיס, ולאחר מכן התשובות חוזרות למעלה.
רמת קושי 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. הבוחן בודק מספר מערכים.
לחץ על הרץ כדי לראות את התוצא כאן.