פרק 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);
}

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

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

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

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

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

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

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

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

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

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

דוגמא 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 חזרה עם הקטנת 
}

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

א. שִׁיכְחַת מקרה בסיס – תגרום ל־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 עם הקריאה הרקורסיבית/הביטוי.
• חץ מלא = הלוך (קריאה), חץ מקווקו = חזור (החזרת ערך).

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

• שרטט/י מעקב עבור 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);
    }
}

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

השלבים של Reductible

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

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

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

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

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

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

public static Rev(int num, int result = 0)

תרגול וקישורים

כדי לתרגל את הנושא נפתור הרבה שאלות רקורסיביות. תוכלו למצוא תרגילים במערכת ההגשות. <!– ⬅ עברו לתרגיל סכום ספרות במספר

בנוסף, נסו לכתוב פונקציה שמחשבת עצרת באופן רקורסיבי. התנסו גם בפתרון איטרטיבי והשוו ביניהם. \(5! = 1·2·3·4·5\) –>

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

סרטונים

פלייליסט רקורסיה בקמפוס

מעקב באמצעות עץ מעקב. לא מומלץ