פרק 10 - רקורסיה

עד עכשיו פתרנו בעיות חוזרות באמצעות לולאות (for ו-while). יש דרך נוספת, אלגנטית לפעמים יותר, לגרום לתוכנית לחזור על פעולה: לגרום למתודה לקרוא לעצמה. הכלי הזה נקרא רקורסיה (Recursion), והוא מופיע גם בשאלות שדורשות מעקב אחר קריאות פונקציה.

1. מהי רקורסיה?

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

2. שני חלקים חובה: תנאי עצירה וקריאה רקורסיבית

לכל פונקציה רקורסיבית תקינה חייבים להיות שני חלקים: תנאי עצירה (Base Case) - מקרה פשוט שבו הפונקציה מחזירה תשובה ישירות, בלי לקרוא לעצמה שוב; וקריאה רקורסיבית (Recursive Case) - קריאה לאותה פונקציה עם קלט קטן או פשוט יותר, שמתקדמת לכיוון תנאי העצירה.

static void countDown(int n) {
    if (n == 0) {
        System.out.println("Done");
        return;
    }
    System.out.println(n);
    countDown(n - 1);
}
            

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

3. עקבו אחרי הקריאות - סכום מ-1 עד n

דוגמה קלאסית נוספת: פונקציה שמחשבת את סכום כל המספרים השלמים מ-1 עד n.

static int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}
            

4. מחסנית הקריאות (Call Stack)

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

5. רקורסיה מול לולאה

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

6. דוגמה נוספת - סדרת פיבונאצי

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

static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
            

7. טעויות נפוצות

8. תרגול

static int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

public static void main(String[] args) {
    System.out.println(sum(3));
}

static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

public static void main(String[] args) {
    System.out.println(fib(5));
}