רקורסיה
הוצג| English | משמעות |
|---|---|
| Recursion/rɪˈkɜːʃn/ | רקורסיה |
| base case/beɪs keɪs/ | מקרה בסיסי |
| recursive case/rɪˈkɜːsɪv keɪs/ | מקרה רקורסיבי |
| unwind/ʌnˈwaɪnd/ | פירוק רצף קריאות |
⟨⟩ שיטה הקוראת לעצמה
- רקורסיה היא מצב שבו שיטה קוראת לעצמה כדי לפתור גרסה קטנה יותר של אותו בעיה.
- לכל רקורסיה יש שני חלקים: מקרה בסיס ומקרה רקורסיבי.
- מקרה הבסיס עצור את הרקורסיה — כניסה קטנה שהשיטה עונה עליה ישירות.
- המקרה הרקורסיבי מקרא את השיחה שוב על כניסה קטנה יותר.
⟨⟩ מקרה הבסיס
- ללא מקרה בסיסי, שיטה קוראת לעצמה לנצח — זוהי
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.
שיטה רקורסיבית היא אחת ש...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
רקורסיה = שיטה קוראת לעצמה.
המקרה הבסיסי הוא...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מקרה הבסיס מסיים את הרקורסיה.
רקורסיה ללא מקרה בסיס נגיש גורמת ל-...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
היא רקורסיבית לנצח עד שהסטק מתמלא.
מקרה הרקורסיבי חייב לקרוא לעצמו על...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל קריאה חייבת לצמצם כיוונה למקרה הבסיס.
אם factorial(0)=1 ו-factorial(n)=n*factorial(n-1), מהי factorial(3)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
3 * 2 * 1 * 1 = 6.
כל קריאה רקורסיבית שומרת על העתק משלה של הפרמטרים שלה עד להחזרת התוצאה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הקריאות נערמות באופן עצמאי, ולאחר מכן מתפרקות.