רקורסיה
יש בעיות שקל לפתור אם מניחים שכבר יודעים לפתור גרסה קטנה יותר שלהן. סכום הספרות של 4071 הוא הספרה 1 ועוד סכום הספרות של 407. שרשרת חוליות היא חוליה אחת ועוד שרשרת קצרה יותר. עץ בינרי הוא שורש ועוד שני עצים קטנים יותר. רקורסיה היא הדרך לכתוב את זה בקוד.
במדויק: פעולה רקורסיבית היא פעולה שקוראת לעצמה. יש בה תנאי עצירה (מקרה שבו מחזירים תשובה בלי קריאה נוספת) וקריאה רקורסיבית על קלט קטן יותר, שהתוצאה שלה משמשת לתשובה. בשאלון 899271 רקורסיה מופיעה על תור, על שרשרת חוליות ועל עץ בינרי: במעקב (מה הפעולה מחזירה), בהסבר (מה היא עושה), ביעילות ובכתיבת פעולה.
יעילות
שתי פעולות נכונות יכולות להיות שונות מאוד במהירות. בשאלון לא מודדים שניות: סופרים כמה צעדים הפעולה מבצעת, ובודקים איך המספר הזה גדל כשהקלט גדל.
במדויק: אורך הקלט n הוא מספר האיברים בתור, מספר החוליות בשרשרת או מספר הצמתים בעץ. סיבוכיות זמן הריצה היא סדר הגודל של מספר הצעדים כפונקציה של n, במקרה הגרוע ביותר, בכתיב O. בפעולה עם לולאות סופרים סיבובים; בפעולה רקורסיבית סופרים קריאות.
1. פעולה רקורסיבית: מקרה בסיס וצעד
פעולה רקורסיבית
כשכותבים פעולה רקורסיבית לא צריך לדמיין את כל הקריאות. מספיק לענות על שתי שאלות: מה התשובה לקלט הקטן ביותר, ואיך בונים את התשובה לקלט גדול אם סומכים על כך שהקריאה על הקלט הקטן יותר מחזירה תשובה נכונה.
במדויק: לכל פעולה רקורסיבית שלושה חלקים: תנאי עצירה (מקרה הבסיס) - מחזירים תשובה בלי קריאה; קריאה רקורסיבית על קלט קטן יותר (n / 10, n - 1, lst.getNext(), tree.getLeft()); וצירוף - מה עושים עם הערך שחזר. יש פעולות רקורסיביות שמחזירות ערך, ויש פעולות void שמשנות מבנה או מדפיסות.
שרשרת חוליות ועץ בינרי הם מבנים רקורסיביים: אחרי החוליה הראשונה יש שוב שרשרת, ומתחת לכל צומת יש שוב שני עצים. לכן כמעט כל פעולה עליהם נכתבת כקריאה על ההמשך (getNext) או על שני תתי-העצים (getLeft, getRight). ההרחבה לכל מבנה נמצאת בשיעורים על שרשרת חוליות ועל עצים בינריים.
תבנית: פעולה רקורסיבית שמחזירה ערך
public static int sumDigits(int n)
{
if (n < 10) // תנאי עצירה: ספרה אחת
return n;
return n % 10 + sumDigits(n / 10); // צעד: הספרה האחרונה + סכום שאר הספרות
}sumDigits(4071) מחזירה 12: 1 + sumDigits(407), כלומר 1 + 7 + 0 + 4. הקריאה האחרונה, sumDigits(4), עוצרת בתנאי העצירה.
מה מקטינים ומה תנאי העצירה, לפי הקלט
| קלט | הקריאה הרקורסיבית | תנאי עצירה נפוץ |
|---|---|---|
| מספר שלם | f(n / 10) או f(n - 1) | ספרה אחת (n < 10), או n == 0 |
| מספר שהשאלה מקטינה | what(q, n - 1) | התנאי שבשאלה, למשל mmm(q, n) מחזירה true |
| שרשרת חוליות | f(lst.getNext()) | lst == null (שרשרת ריקה) |
| עץ בינרי | f(tree.getLeft()) ו-f(tree.getRight()) | tree == null, או עלה (אין בן שמאלי ואין בן ימני) |
סוגי רקורסיה
| סוג | מה מאפיין אותו | בבגרות |
|---|---|---|
| רקורסיית זנב | הקריאה הרקורסיבית היא הדבר האחרון, והערך שלה מוחזר כמו שהוא | return what(q, n - 1); (899271 קיץ 2025) |
| רקורסיית הלוך-חזור | יש עבודה אחרי שהקריאה חוזרת | what(lst, x) מחברת את החוליה ל-temp אחרי הקריאה (899271 קיץ 2024) |
| רקורסיה כפולה | שתי קריאות רקורסיביות באותה קריאה | foo(tree.getLeft()) + foo(tree.getRight()) (899271 קיץ 2026) |
| רקורסיה הדדית | פעולה A קוראת ל-B, ו-B קוראת ל-A | - |
רקורסיית זנב אפשר לכתוב גם בלולאה: הפרמטר שמשתנה מקריאה לקריאה (כמו n) הוא משתנה הלולאה.
כתיבת פעולה רקורסיבית
null, עלה). בודקים מה השאלה מבטיחה: "עץ שאינו ריק" - אין קריאה על null, ולכן בודקים hasLeft() / hasRight() לפני כל קריאה.k - 1 כשיורדים שמאלה) ומה נשאר כמו שהוא (k כשיורדים ימינה, x בכל הקריאות).&&, ואפשר להחזיר false מיד; "קיים" = ||; ספירה וסכום = +.פעולה בלי תנאי עצירה, או עם קריאה שלא מקטינה את הקלט (למשל f(n) במקום f(n - 1)), לא נגמרת: הקריאות ממשיכות עד שהתוכנית קורסת. לפני שכותבים את הצעד, כותבים את תנאי העצירה.
כשתנאי העצירה הוא עלה ולא null, אסור לקרוא לפעולה על בן שאינו קיים. בפעולה foo של קיץ 2026 תנאי העצירה הוא עלה, ולכן על עץ ריק היא נכשלת; לכן השאלה מדברת על "עץ כלשהו שאינו ריק", והקוד בודק tree.getLeft() == null לפני כל קריאה.
דוגמה - בדיקה אם עץ הוא עץ K-שמאלי
"עץ K-שמאלי" הוא עץ בינרי ובו כל מסלול משורש העץ לעלה כלשהו מכיל לכל היותר K קשתות הפונות שמאלה (כלומר מקסימום K בנים שמאליים).
בעץ שבשאלה (נסמן את הצמתים באותיות): לשורש A בן שמאלי B ובן ימני C. ל-B רק בן ימני D (עלה). ל-C בן שמאלי E ובן ימני G (עלה). ל-E בן שמאלי F ובן ימני H (שניהם עלים). העץ הזה אינו "עץ 1-שמאלי", כי במסלול A → C → E → F יש שתי קשתות שמאליות; הוא "עץ 2-שמאלי".
כתבו פעולה חיצונית ששמה isLeftK בשפת Java או IsLeftK בשפת C#, המקבלת עץ בינרי root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא "עץ K-שמאלי", ואם לא - היא מחזירה false.
null. בעלה אין עוד קשתות: מחזירים true.k - 1; ירידה ימינה לא משנה את התקציב - k.public static boolean isLeftK(BinNode<Integer> root, int k)
{
if (root.hasLeft())
{
// ירידה שמאלה "צורכת" קשת שמאלית אחת
if (k == 0 || !isLeftK(root.getLeft(), k - 1))
return false;
}
if (root.hasRight())
{
// ירידה ימינה לא משנה את מספר הקשתות השמאליות
if (!isLeftK(root.getRight(), k))
return false;
}
return true;
}isLeftK(A, 2) מחזירה true; isLeftK(A, 1) מחזירה false: A → C עם תקציב 1, C → E צורכת קשת (נשאר 0), ו-E → F צריכה קשת נוספת כשהתקציב 0. גם isLeftK(A, 0) מחזירה false, כבר בבן השמאלי B.רקורסיה עם "תקציב" K: אם יש בן שמאלי - אם K == 0 מחזירים false, אחרת בודקים אותו עם K - 1; בן ימני - בודקים עם אותו K; עלה - true. יעילות O(n).
2. מעקב אחר פעולה רקורסיבית
מעקב אחר רקורסיה
כל קריאה רקורסיבית היא "עותק" נפרד של הפעולה, עם פרמטרים ומשתנים משלו. הקריאה שקראה מחכה עד שהקריאה הפנימית תחזיר ערך, ורק אז ממשיכה מהנקודה שבה עצרה.
במדויק: במעקב אחר רקורסיה כותבים שורה לכל קריאה: הפרמטרים שהיא קיבלה, איזה מקרה התקיים, החישוב שלה במונחים של הקריאות הפנימיות (foo(9) + 1), והערך שהיא מחזירה. בשאלון כתוב לדוגמה: "המעקב יכלול בכל קריאה את הערכים של q, n ואת הערך המוחזר". בסוף כותבים במפורש מה הקריאה הראשונה מחזירה.
זו טבלת המעקב המוכרת מלולאות, אבל במקום שורה לכל סיבוב יש שורה לכל קריאה. בפעולה על שרשרת חוליות שורה לכל חוליה (ועוד אחת ל-null); בפעולה על עץ שורה לכל צומת.
לפני הקריאה ואחרי הקריאה
public static void upDown(int n)
{
if (n > 0)
{
System.out.print(n + " "); // לפני הקריאה: בדרך למטה
upDown(n - 1);
System.out.print(n + " "); // אחרי הקריאה: בדרך חזרה
}
}upDown(3) מדפיסה 3 2 1 1 2 3.
| איפה ההוראה | מתי היא מתבצעת |
|---|---|
| לפני הקריאה הרקורסיבית | בדרך למטה: בסדר הקריאות, מהראשונה לאחרונה |
| אחרי הקריאה הרקורסיבית | בדרך חזרה: בסדר הפוך, מהקריאה האחרונה לראשונה |
בפעולה what של 899271 קיץ 2024 הקריאה what(lst.getNext(), x) באה לפני הטיפול בחוליה, ולכן החוליות מטופלות מהאחרונה לראשונה.
מעקב אחר רקורסיה: יורדים ואז עולים
foo(9) + 1), ופותחים שורה לכל קריאה פנימית.כשכתוב "אין צורך לעקוב אחר הפעולה mmm" או "אין צורך לעקוב אחר הפעולה what", משתמשים במה שמצאתם עליה בסעיף הקודם, בלי לפתוח אותה שוב. ב-what(q, 6) של קיץ 2025 מספיק לדעת ש-mmm בודקת רצף של לפחות n איברים שווים צמודים: mmm מחזירה false על 6, 5 ו-4 ו-true על 3, ולכן what(q, 6) מחזירה 3.
ב-&& ו-|| הצד הימני לא מחושב כשהתוצאה כבר ידועה. בפעולה goo של קיץ 2026, goo(tree.getLeft()) && goo(tree.getRight()): אם הקריאה השמאלית מחזירה false, הקריאה הימנית לא מתבצעת בכלל, ואין לה שורה במעקב.
פעולה שמוחקת חוליות ומחזירה את ראש השרשרת - התשובה היא השרשרת שהוחזרה. אחרי what(lst, 1) של קיץ 2024 המשתנה lst עדיין מפנה לחוליה 1 הראשונה, שנמחקה מהשרשרת שהוחזרה.
דוגמה א - רקורסיה כפולה על עץ בינרי
נתונה הפעולה foo בשפת Java או Foo בשפת C#:
public static int foo(BinNode<Integer> tree)
{
if (tree.getLeft() == null && tree.getRight() == null)
return 0;
if (tree.getLeft() == null)
return foo(tree.getRight()) + 1;
if (tree.getRight() == null)
return foo(tree.getLeft()) - 1;
return foo(tree.getLeft()) + foo(tree.getRight());
}העץ tree: השורש 5, ולו רק בן ימני 9. ל-9 רק בן ימני 7. ל-7 בן שמאלי 0 ובן ימני 3 (שניהם עלים).
בצעו מעקב אחרי הפעולה foo והעץ, וכתבו מה הפעולה מחזירה. יש להציג את המעקב.
foo(ימני) + 1; רק בן שמאלי - foo(שמאלי) - 1; שני בנים - סכום שתי הקריאות.| קריאה | מצב הצומת | חישוב | ערך מוחזר |
|---|---|---|---|
foo(5) | רק בן ימני (9) | foo(9) + 1 | 2 |
foo(9) | רק בן ימני (7) | foo(7) + 1 | 1 |
foo(7) | שני בנים | foo(0) + foo(3) | 0 |
foo(0) | עלה | - | 0 |
foo(3) | עלה | - | 0 |
foo(0) = 0 ו-foo(3) = 0, לכן foo(7) = 0 + 0 = 0; foo(9) = 0 + 1 = 1; foo(5) = 1 + 1 = 2.-1, ועלה או צומת עם שני בנים תורמים 0. כאן יש שני צמתים עם בן ימני בלבד (5 ו-9).הפעולה מחזירה 2.
דוגמה ב - רקורסיית הלוך-חזור שמוחקת חוליות
נתונה הפעולה what בשפת Java או What בשפת C#:
public static Node<Integer> what(Node<Integer> lst, int x)
{
if (lst == null)
return null;
Node<Integer> temp = what(lst.getNext(), x);
if (lst.getValue() == x)
return temp;
lst.setNext(temp);
return lst;
}נתונה שרשרת חוליות lst מטיפוס שלם: 1 → 3 → 5 → 3 → 1 → 9 → 4 → null (משמאל לימין: 1, 3, 5, 3, 1, 9, 4).
עקבו אחר הפעולה what(lst, 1), והציגו את השרשרת שהפעולה מחזירה.
what(lst.getNext(), x) באה לפני הבדיקה של החוליה. לכן הקריאות יורדות עד null, והחוליות מטופלות בדרך חזרה, מהאחרונה לראשונה.setNext(temp) ומחזירים את החוליה.| קריאה על חוליה | temp שחזר | הערך הוא 1? | מוחזר |
|---|---|---|---|
| null | - | - | null |
| 4 | null | לא | 4 |
| 9 | 4 | לא | 9 → 4 |
| 1 (החמישית) | 9 → 4 | כן | 9 → 4 |
| 3 (הרביעית) | 9 → 4 | לא | 3 → 9 → 4 |
| 5 | 3 → 9 → 4 | לא | 5 → 3 → 9 → 4 |
| 3 (השנייה) | 5 → 3 → 9 → 4 | לא | 3 → 5 → 3 → 9 → 4 |
| 1 (הראשונה) | 3 → 5 → 3 → 9 → 4 | כן | 3 → 5 → 3 → 9 → 4 |
3 -> 5 -> 3 -> 9 -> 4 -> null. ההרצה מראה גם ש-lst עצמו עדיין מתחיל בחוליה 1.הפעולה מחזירה את השרשרת 3 → 5 → 3 → 9 → 4 → null (שתי החוליות עם הערך 1 הוסרו).
3. יעילות: סיבוכיות זמן ריצה O
סיבוכיות של פעולה על מבנה נתונים
בשאלון 899271 כמעט כל שאלה על תור, שרשרת או עץ מסתיימת ב"מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם". התשובה היא סדר גודל אחד ונימוק של משפט-שניים.
במדויק: קובעים מה n (מספר האיברים בתור, החוליות בשרשרת, הצמתים בעץ), סופרים כמה צעדים בסיסיים מתבצעים כפונקציה של n, ובוחרים את המקרה הגרוע ביותר - הקלט שבו מתבצעים הכי הרבה צעדים. בלולאה סופרים סיבובים; ברקורסיה סופרים קריאות ומכפילים בעבודה של כל קריאה.
הדרך הכללית לשאלת יעילות (מה n, מחיר כל הוראה, כמה סיבובים, מכפילים ומחברים) ודוגמאות על תור נמצאות בנושא "הבגרות במדעי המחשב". כאן: מקרה גרוע וטוב, סכומים שחוזרים, ויעילות של רקורסיה.
מקרה גרוע ומקרה טוב בשאלות הבגרות
| פעולה | המקרה הגרוע | המקרה הטוב |
|---|---|---|
| guess (קיץ 2024): לכל חוליה מוחקת מההמשך את הכפולים שלה | כל הערכים שונים, אף חוליה לא נמחקת: O(n²) | כל הערכים שווים, הקריאה הראשונה מוחקת הכול: O(n) |
what(q, n) (קיץ 2025): יורדת מ-n עד אורך הרצף הארוך ביותר | אין שני איברים צמודים שווים, n קריאות: O(n²) | כל האיברים שווים, קריאה אחת: O(n) |
הסיבוכיות שעונים בשאלה היא של המקרה הגרוע. כותבים מהו הקלט הגרוע, ולמה הוא הגרוע.
סכומים שחוזרים בנימוק
| מה קורה | הסכום | סדר גודל |
|---|---|---|
| n סיבובים, O(1) בכל סיבוב | n · 1 | O(n) |
| n + 1 קריאות (אחת לכל חוליה ועוד אחת ל-null) | n + 1 | O(n) |
| k סבבים, בכל סבב מעבר על עד n איברים | k · n | O(k·n), ובמקרה הגרוע k = n: O(n²) |
| בכל סבב מעבר על מה שנשאר: n − 1, n − 2, ..., 1, 0 | n(n − 1) / 2 | O(n²) |
| חלקים שבאים זה אחרי זה: O(n²), ואחריו O(n), ואחריו O(n) | משאירים את הגדול | O(n²) |
גם כשבכל סבב עוברים על פחות איברים, הסכום (n − 1) + (n − 2) + ... + 1 הוא בערך חצי מ-n², ולכן O(n²) ולא O(n).
יעילות של פעולה רקורסיבית
| מבנה הקריאות | מספר קריאות | עבודה בכל קריאה | סיבוכיות | בבגרות |
|---|---|---|---|---|
| קריאה אחת על ההמשך | n + 1 | O(1) | O(n) | what(lst, x), קיץ 2024 |
קריאה אחת על n - 1 | עד n | קריאה לפעולה ב-O(n) | O(n²) | what(q, n), קיץ 2025 |
| קריאה אחת על ההמשך | n + 1 | קריאה לפעולה על ההמשך: n − 1, n − 2, ..., 0 | O(n²) | guess, קיץ 2024 |
| שתי קריאות, על שני תתי-העצים | כל צומת פעם אחת | O(1) | O(n) | isLeftK, קיץ 2025 |
רקורסיה כפולה על עץ היא עדיין O(n) כשכל צומת מבוקר פעם אחת: שתי הקריאות מתחלקות בצמתים, לא מכפילות אותם.
סיבוכיות של רקורסיה: קריאות כפול עבודה
קריאה לפעולה אחרת בתוך רקורסיה אינה צעד אחד. guess של קיץ 2024 קוראת בכל חוליה ל-what על ההמשך, ו-what עוברת על כל ההמשך. מי שסופר רק את n הקריאות של guess וכותב O(n) - טועה: הסיבוכיות O(n²).
הנימוק צריך לתאר את הקלט הגרוע. ב-uniteOrders של קיץ 2026: "המקרה הגרוע: כל ההזמנות של לקוחות שונים, ואז בכל סבב יוצאת מהתור הזמנה אחת בלבד". בלי זה לא ברור למה הלולאה החיצונית רצה n פעמים.
לרקורסיה יש גם מחיר: כל קריאה שעוד לא חזרה תופסת מקום בזיכרון, ויש עבודה בכל קריאה.
דוגמה א - סיבוכיות של רקורסיה על שרשרת
נתונה הפעולה what בשפת Java או What בשפת C#, שמוחקת משרשרת חוליות lst את כל החוליות שערכן x ומחזירה את ראש השרשרת:
public static Node<Integer> what(Node<Integer> lst, int x)
{
if (lst == null)
return null;
Node<Integer> temp = what(lst.getNext(), x);
if (lst.getValue() == x)
return temp;
lst.setNext(temp);
return lst;
}מהי סיבוכיות הפעולה what? נמקו את תשובתכם.
lst.getNext(). הקריאות יורדות חוליה אחר חוליה עד null: n קריאות על החוליות ועוד אחת על null, כלומר n + 1. כאן אין הבדל בין מקרה גרוע לטוב: תמיד עוברים על כל השרשרת.getValue(), השוואה, setNext(temp) ו-return - מספר קבוע של פעולות, O(1).O(n), כאשר n הוא מספר החוליות בשרשרת: קריאה רקורסיבית אחת לכל חוליה (ועוד אחת ל-null), ובכל קריאה עבודה קבועה.
דוגמה ב - לולאה שעוברת בכל סבב על מה שנשאר
נתונה המחלקה Order (הזמנה) עם התכונות id (מספר זהות של הלקוח) ו-count (כמות המוצרים). הפעולה uniteOrders בשפת Java או UniteOrders בשפת C# מקבלת תור הזמנות qOrder, שבו אותו לקוח יכול להופיע כמה פעמים, ומחזירה תור חדש שבו לכל לקוח הזמנה אחת עם סך כל המוצרים שלו:
public static Queue<Order> uniteOrders(Queue<Order> qOrder)
{
Queue<Order> result = new Queue<Order>();
while (!qOrder.isEmpty())
{
Order first = qOrder.remove(); // הזמנה של לקוח חדש
int total = first.getCount();
Queue<Order> temp = new Queue<Order>();
while (!qOrder.isEmpty()) // מעבר על שאר ההזמנות
{
Order o = qOrder.remove();
if (o.getId() == first.getId())
total += o.getCount(); // אותו לקוח - מצרפים
else
temp.insert(o); // לקוח אחר - שומרים לסבב הבא
}
qOrder = temp;
result.insert(new Order(first.getId(), total));
}
return result;
}מהי סיבוכיות זמן הריצה של הפעולה? נמקו את תשובתכם.
isEmpty(), remove(), insert(x) ופעולות get - כל אחת O(1).O(n²): לכל לקוח מעבר על כל ההזמנות שנותרו, (n − 1) + (n − 2) + ... + 1 במקרה הגרוע.