פרק 1 – רקורסיה | מבני נתונים עם גיא

רקורסיה היא טכניקה מרכזית במדעי המחשב שבה פונקציה פותרת בעיה על ידי פירוקה לגרסה קטנה יותר של אותה בעיה. חשוב להבדיל בין מקרה בסיסי שבו הפונקציה עוצרת, לבין מקרה רקורסיבי שבו היא קוראת לעצמה. הבנת עקרונות אלו תלווה אתכם לאורך הקורס .

מבוא לרקורסיה

רקורסיה מתארת תהליך שבו פונקציה קוראת לעצמה לצורך פתרון בעיה. למשל, קביעת סכום של מערך יכולה להתבצע על ידי סכימת האיבר הראשון עם סכום המערך החל מהאיבר השני. כדי להבטיח שהאלגוריתם מסתיים, עלינו להגדיר מקרה בסיס – תנאי, שבו הפונקציה מחזירה תוצאה ללא קריאה נוספת.

עדי גרין מסבירה לנו מהי רקורסיה

דוגמא לרקורסיה - סכום איברי מערך?

1
2
3
4
5
6
7
8
9
10
// סכום אלמנטים במערך באמצעות רקורסיה
public static int Sum(int[] arr, int index)
{
  // מקרה בסיס – הגענו לסוף המערך
  if (index == arr.Length)
      return 0;

  // מקרה רקורסיבי – מוסיפים את הערך הנוכחי לסכום שאר האיברים
  return arr[index] + Sum(arr, index + 1);
}

הבנת מחסנית הקריאות. או שלא...

הבנת מחסנית הקריאות

כל קריאה לפונקציה יוצרת רשומת קריאה חדשה במחסנית. כאשר אנחנו קוראים לפונקציה ברקורסיה, נוצרת שרשרת רשומות עד שמגיעים למקרה הבסיס. לאחר מכן הקריאות מסתיימות בסדר הפוך (LIFO), כמו במחסנית.

graph TD A["Sum(arr, 0)"] --> B["Sum(arr, 1)"] B --> C["Sum(arr, 2)"] C --> D["Sum(arr, 3)"] D --> E["Sum(arr, n)"] E --> F[0]

הדיאגרמה ממחישה כיצד הקריאות נערמות עד למקרה בסיס, ומסמנות חזרה עם הערך 0. כל קריאה מחכה לפתרון הקריאה העמוקה יותר לפני שהיא מחזירה את ערכה.

בקוד זה המקרה הבסיסי הוא כאשר index שווה לגודל המערך. המקרה הרקורסיבי מוסיף את האיבר הנוכחי לתוצאה של קריאה מחדש לפונקציה עם אינדקס מתקדם.

סיכום הרעיון. אז מה זה רקורסיה?

אלגוריתם רקורסיבי הוא אלגוריתם אשר על מנת לפתור בעיה מסוימת, מפעיל את עצמו על מקרים פשוטים יותר של הבעיה.

בכל אלגוריתם רקורסיבי תמיד יש:

תנאי עצירה
זימון רקורסיבי על קלט קטן יותר

אז למה להשתמש ברקורסיה?

בהרבה מקרים ההגדרה הרקורסיבית קצרה בהרבה מההגדרה האיטרטיבית.
במקרים מסויימים, ההגדרה הרקורסיבית היא ההגדרה הטבעית והנוחה ביותר של מה שרוצים לחשב.
כי זה למבחן.

✅ מקרים בסיסיים חשובים

א. מגדירים תנאי עצירה ברור (למשל, גודל אפס או אינדקס מחוץ לתחום).

ב. אסור לקרוא לפונקציה עצמה מתוך המקרה הבסיסי – אחרת נתקע בלולאה אינסופית.

ג. חשוב לזהות את מקרה הבסיס כפתרון הבעיה הפשוטה ביותר האפשרית.

דוגמא 1/תרגול: מכפלה של שני מספרים באופן רקורסיבי

כתבו את הפונקציה Mul(int a, int b) המחשבת כפל של \(a·b\) ברקורסיה.

הרעיון: \(a⨯b = a+a+ ... b פעמים\) נניח ש-\(b\) אינו שלילי.

הדרכה. חשבו על המקרה בו עלינו לכפול 4 ב-1, או בעצם, אפילו 4 ב-0, כעל המקרה הפשוט. זה ישמש תנאי עצירה

כיצד נחשב כפל של 4 ב-2 אם אנחנו יודעים כמה זה כפל ב-1?

פתרון

1
2
3
4
5
6
7
public static int Mul(int a, int b)
{
  if (b == 0)
    return 0; // תנאי עצירה

  return a + Mul(a, b - 1); // b חזרה עם הקטנת
}

מעקב בשיטת המלבנים

מעקב רקורסיה בשיטת המלבנים: בשורה העליונה – שם הפונקציה והארגומנטים, בשורה האמצעית – תנאי העצירה, ובשורה השלישית – ביטוי ה־ return.
בחיצים: → (חץ מלא) מציין קריאה רקורסיבית (הלוך), ו־-.-> (חץ מקווקו) מציין החזרת ערך (חזור). במעקב שלהלן הכפל \(4·3\)

❌ טעויות נפוצות ברקורסיה

א. שִׁיכְחַת מקרה בסיס – תגרום ל־StackOverflow.

ב. שינוי נתונים משותפים במיקום לא נכון – עלול לגרום לתוצאה שגויה. לא רלוונטי עבורנו. לא נשתף נתונים. לא נבצע Memoization.

ג. כתיבת קוד רקורסיבי כאשר פתרון איטרטיבי פשוט וברור יותר. לא רלוונטי עבורנו. ביקשו רקורסיה - יקבלו רקורסיה.

דוגמא 2/תרגול: מנה של חלוקה שלמה בחיסור חוזר : \(\lfloor (9/4) \rfloor = 2\)

רעיון: כמה פעמים ניתן לחסר את b מתוך a עד שהמספר קטן מ־b.

פתרון

1
2
3
4
5
6
7
public static int Div(int a, int b)
{
  if (a < b)
      return 0;       // תנאי עצירה

  return 1 + Div(a - b, b);  // b חזרה עם חיסור
}

מעקב בשיטת המלבנים

שיטת המלבנים (סיכום קצר):

שורה עליונה: שם הפונקציה והארגומנטים שקיבלה.
שורה אמצעית: תנאי העצירה (כאן עד ההגעה לבסיס הוא false).
שורה שלישית: return עם הקריאה הרקורסיבית/הביטוי.
חץ מלא = הלוך (קריאה), חץ מקווקו = חזור (החזרת ערך).

הרחבת ידע – האם באמת משתמשים ברקורסיה בעולם האמיתי?

כן. אבל לא בכל מקום

רקורסיה אינה “טובה יותר” מלולאה באופן כללי. היתרון הגדול שלה מופיע כאשר הבעיה או מבנה הנתונים עצמם בנויים בצורה רקורסיבית – כלומר, דבר שמכיל דברים נוספים מאותו סוג.

הדוגמה החשובה ביותר שנפגוש בהמשך היא עץ בינארי:

public class BinNode<T>
{
    private T value;
    private BinNode<T> left;
    private BinNode<T> right;
}

כל צומת מכיל שני עצים קטנים יותר: עץ שמאלי ועץ ימני.

לכן פעולה על עץ נכתבת באופן טבעי מאוד כך:

public static int CountNodes<T>(BinNode<T> node)
{
    if (node == null)
        return 0;

    return 1
        + CountNodes(node.GetLeft())
        + CountNodes(node.GetRight());
}

הרעיון הוא בדיוק הרעיון שלמדנו:

פתור את המקרה הנוכחי, ובקש משתי הקריאות הרקורסיביות לפתור את שתי הבעיות הקטנות יותר.

וזה קורה בתוכנות אמיתיות

Git שומר תיקיות וקבצים במבנה של עצים. בקוד של Git קיימת פעולה שסורקת עץ, וכאשר היא מגיעה לתת־עץ היא קוראת שוב לעצמה כדי לסרוק אותו.

מעניין במיוחד ש-Git גם מגביל את עומק העץ המרבי. כלומר, המפתחים משתמשים ברקורסיה – אבל לא נותנים לה לרדת לעומק בלתי מוגבל.

גם Clang, מהדר אמיתי של C ו-C++, משתמש במנגנון בשם RecursiveASTVisitor כדי לעבור על עץ התחביר (AST) של תוכנית.

גם בקוד של Python עצמו (CPython) קיימות פעולות רקורסיביות שעוברות על עצי תחביר, יחד עם מנגנונים שמגינים מפני עומק רקורסיה גדול מדי.

כלומר, רקורסיה אינה רק תרגיל לבגרות. היא נמצאת בתוכנות אמיתיות כאשר הנתונים עצמם בנויים כעץ או כמבנה מקונן.

ומה לגבי המעבד עצמו?

כאשר כתבנו:

return a + Mul(a, b - 1);

המעבד לא באמת מבצע כפל בצורה הזו באמצעות קריאות רקורסיביות.

אבל יש כאן רעיון אמיתי מאוד מעולם החומרה:

פעולה מסובכת יכולה להיבנות מרצף של פעולות פשוטות יותר.

אלגוריתמים לחילוק בינארי בחומרה מבצעים למשל שוב ושוב פעולות של הזזה, חיסור ובדיקה של שארית חלקית.

גם במעבדים היסטוריים של Intel נעשה שימוש באלגוריתם בשם CORDIC, שבו פעולות מתמטיות מורכבות מחושבות באמצעות סדרה של צעדים פשוטים החוזרים שוב ושוב.

בחומרה בדרך כלל קוראים לרעיון כזה recurrence – נוסחת נסיגה – ולא לרקורסיה של פונקציות, מפני שאין שם מחסנית קריאות כמו בתוכנית שלנו.

לכן Mul ו-Div שלנו אינם הדגם המדויק של יחידת הכפל והחילוק במעבד, אבל העיקרון של הקטנת בעיה ובניית התוצאה באמצעות צעדים פשוטים חוזרים הוא עיקרון אמיתי לחלוטין בעולם המחשבים.

ואם זה כל כך שימושי, למה לפעמים אוסרים על רקורסיה?

דווקא מפני שלרקורסיה יש מחיר.

כל קריאה מוסיפה מידע למחסנית הקריאות. אם עומק הרקורסיה אינו צפוי, קשה לדעת מראש כמה זיכרון היא תצרוך.

לכן בתוכנה שבה תקלה עלולה להיות מסוכנת במיוחד, לפעמים מחליטים לא להשתמש בה כלל. לדוגמה, כללי תכנות מסוימים של NASA/JPL לתוכנה קריטית אוסרים על רקורסיה ישירה ועקיפה, כדי שאפשר יהיה להוכיח מראש גבולות לזמן הריצה ולשימוש במחסנית.

חשוב לדייק: אין איסור כללי של ממשלת ארצות הברית על רקורסיה. מדובר בכללי תכנות מחמירים שנועדו לסוגים מסוימים של תוכנה קריטית.

המסקנה: רקורסיה אינה משהו שצריך “להאמין בו”, וגם לא משהו שצריך לפחד ממנו. כאשר מבנה הבעיה רקורסיבי – למשל עצים, עצי תחביר או מבני תיקיות – היא יכולה להיות הדרך הישירה והברורה ביותר לכתוב את האלגוריתם. כאשר עומק הקריאות עלול להיות גדול או בלתי צפוי, צריך להגביל אותו או לבחור פתרון אחר.

לתרגול עצמי של מעקב (בפעם אחרת)

שרטט/י מעקב עבור Mul(3,2) ו־Div(10,3) והוסיפ/י תוויות על ערכי ההחזרה בכל שלב.
כמה קריאות/חזרות יש בכל אחד מהמקרים? הסבירו בקצרה כיצד נובע המספר מהפרמטרים.

תרגול מעקב - שאלת קמפוס

קישור למקור בקמפוס

עקבו אחר קטע הקוד הבא. מה יוחזר עבור הקריאה Mystery(3)?

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int Mystery  (int n)
{
  if (n <= 0) // תנאי עצירה
      return 0;

  else
    {
      if (n % 3 == 0) // n הקריאות הרקורסיביות מקטינות את
        return Mystery (n - 1) + n;
      else
        return Mystery (n - 1);
    }
}

תרשים המלבנים של Mystery(3)

נסו לעקוב מה יודפס עבור Mystery(10)

סרטון על טכניקות לחשיבה רקורסיבית

השלבים של Reductible

מה המקרה הפשוט ביותר? הוא ישמש כתנאי העצירה
עבודה עם דוגמאות פשוטות, סמוכות למקרה הבסיס, ויזואליציה של הבעיה
קישור בין בעיה גדולה לבעיות קטנות יותר. כיצד ניתן לפתור מקרה אם ידוע מקרה קטן יותר?
הכללת הקשר שמצאנו
כתיבת קוד: תנאי העצירה ואחריו הקריאה הרקורסיבית.
עם הזמן מתגבשת חשיבה / אמונה, שאני (הפונקציה) רק צריכה לעשות את השלב שלי, והקריאה הרקורסיבית תחזיר תשובה נכונה.

רקורסיה מול איטרציה

בפעמים רבות ניתן לפתור בעיה הן בשיטה רקורסיבית והן בשיטה איטרטיבית. בשיטה רקורסיבית מקבלים קוד קריא ופשוט לעיתים, אך הוא עלול לבזבז זיכרון עקב שימור מצבי הקריאה במחסנית. אלגוריתם איטרטיבי משתמש בלולאות ויכול להיות יעיל יותר בזיכרון, במיוחד כאשר העומק הרקורסיבי גדול.

טבלה – השוואה בין רקורסיה לאיטרציה

מאפיין	רקורסיה	איטרציה
שימוש בזיכרון	כל קריאה מוסיפה רשומת מחסנית	לרוב שימוש קבוע בזיכרון
קריאות חוזרות	קריאה חוזרת לפונקציה עצמה	לולאה (for / while)
קריאות מקרה בסיס	חיוני לעצירת הקריאות	אין צורך במקרה בסיס
בהירות קוד	לעיתים קריא יותר	לעיתים נדרשים משתנים נוספים

דוגמא לרקורסיה במחרוזת: הפיכת מחרוזת

public static string StrReverse(string str)
{
   //null כדאי גם לבדוק 
   if (str.Length < 2) // תנאי עצירה: ריק או תו בודד
      return str;

   return StrReverse(str.Substring(1)) + str[0];
}

מעקב

דוגמא לרקורסיה: הפיכת מספר - ללא שימוש במחרוזת. כיוון לפתרון

הפיכת מחרוזת - קשה יותר מהפיכת מספר. הטכניקה שעליכם לחשוב עליה היא שימוש במשתנה עזר, והעברה שלו בתוך הקריאה הרקורסיבית. חישבו על מצב שבו עובדים עם 2 מספרים:

המספר שאתם מחלקים ב-10
והתוצאה שאנחנו בונים: זו שכופלים ב-10.
```
  public static Rev(int num, int result = 0)
```