Java

רקורסיה

מהי רקורסיה?

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

דוגמה קלאסית: עצרת

עצרת (factorial) של n, מסומנת n!, היא:

n! = n * (n-1) * (n-2) * ... * 1
5! = 5 * 4 * 3 * 2 * 1 = 120

אפשר להגדיר את זה גם רקורסיבית:

n! = n * (n-1)!
0! = 1

ב-Java:

public static int factorial(int n) {
    if (n <= 1) return 1;           // מצב בסיס
    return n * factorial(n - 1);    // קריאה רקורסיבית
}

איך זה רץ?

factorial(5)
  5 * factorial(4)
      4 * factorial(3)
          3 * factorial(2)
              2 * factorial(1)
                  1          ← מצב בסיס
              2 * 1 = 2
          3 * 2 = 6
      4 * 6 = 24
  5 * 24 = 120

שני מרכיבים חובה

כל פונקציה רקורסיבית חייבת שני חלקים:

1. מצב בסיס (Base Case)

תנאי עצירה - איפה הרקורסיה מפסיקה לקרוא לעצמה. בלי זה - לולאה אינסופית ו-StackOverflowError.

if (n <= 1) return 1;   // מצב בסיס

2. קריאה רקורסיבית

הקריאה לעצמה, עם פרמטר "קטן יותר" - כזה שמתקרב למצב הבסיס.

return n * factorial(n - 1);   // n-1 קטן יותר מ-n

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

דוגמאות נוספות

פיבונאצ'י

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

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

אזהרה: זה רקורסיבי, אבל מאוד לא יעיל! מחשב את אותם ערכים מיליון פעמים. עדיף איטרטיבי בבעיה הזו.

סכום מספרים 1..n

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

// sum(5) = 5 + 4 + 3 + 2 + 1 = 15

חזקה

public static int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

// power(2, 10) = 1024

היפוך מחרוזת

public static String reverse(String s) {
    if (s.length() <= 1) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}

// reverse("hello") = "olleh"

חיפוש בינארי רקורסיבי

public static int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;   // לא נמצא

    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;

    if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

איך זה עובד בזיכרון?

כל קריאה רקורסיבית יוצרת מסגרת חדשה ב-stack. המסגרות נערמות אחת על השנייה עד שהרקורסיה מתחילה להחזיר.

factorial(3) → stack frame
 factorial(2) → stack frame
  factorial(1) → stack frame  (מצב בסיס - מחזיר)
 ← מחזיר 1, stack frame נמחק
← מחזיר 2, stack frame נמחק
← מחזיר 6

StackOverflowError

אם הרקורסיה לא נעצרת (אין מצב בסיס או שהפרמטר לא מתקטן), ה-stack מתמלא:

public static void bad() {
    bad();   // StackOverflowError!
}

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

טוב לרקורסיה:

• בעיות שמוגדרות באופן טבעי רקורסיבית (עצים, גרפים, מבני Tree)
• בעיות "הפחת וכבוש" (Divide and Conquer)
• מיון כמו Merge Sort ו-Quick Sort
• חיפוש בעומק בגרפים
• בעיות קומבינטוריות (Tower of Hanoi, חלוקת תת-קבוצות)

פחות טוב לרקורסיה:

• בעיות איטרטיביות פשוטות (סכום, לולאה)
• בעיות שיוצרות אותה תת-בעיה הרבה פעמים (כמו פיבונאצ'י)

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

רוב הבעיות אפשר לפתור בשתי הדרכים. לדוגמה:

עצרת איטרטיבית

public static int factorialIter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

עצרת רקורסיבית

public static int factorialRec(int n) {
    if (n <= 1) return 1;
    return n * factorialRec(n - 1);
}

טיפים

1. תמיד שאל את עצמך: מה מצב הבסיס? איך הקריאה הרקורסיבית מתקרבת אליו?
2. תאמין בתהליך: הנח שהקריאה הרקורסיבית "עובדת" ופותרת את הבעיה הקטנה יותר.
3. חשבו על העץ: ציירו את עץ הקריאות על נייר.
4. אל תתעקשו על רקורסיה - אם יש פתרון איטרטיבי ברור ופשוט, הוא עדיף.