רקורסיה - הסבר ודוגמאות לבגרות

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

שני החלקים של כל רקורסיה

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

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

דוגמה ראשונה - סכום המספרים מ-1 עד n

int Sum(int n)
{
    if (n == 0)          // תנאי עצירה
        return 0;
    return n + Sum(n - 1); // צעד רקורסיבי
}

הקריאה Sum(3) מתגלגלת כך: 3 + Sum(2) → 3 + (2 + Sum(1)) → 3 + (2 + (1 + Sum(0))) → 3 + 2 + 1 + 0 = 6. שימו לב שכל קריאה "ממתינה" לתוצאה של הקריאה הפנימית יותר.

דוגמה שנייה - עצרת (factorial)

int Factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * Factorial(n - 1);
}

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

מעקב אחר הרצה - הסעיף שמפיל נבחנים

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

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

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

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

רקורסיה ומבני נתונים

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

איך מתרגלים

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