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

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

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

הנה דוגמה פשוטה לספירה לאחור שמדגימה רקורסיה:

void countdown(int n) {
    if (n <= 0) {           // מקרה בסיס: עצור כאשר n מגיע ל-0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // צעד רקורסיבי: קרא לפונקציה עם n-1
}

כשקוראים ל־countdown(3), הפונקציה מדפיסה 3, ואז קוראת ל־countdown(2), שמדפיסה 2, ואז קוראת ל־countdown(1), וכך הלאה עד שהיא מגיעה למקרה הבסיס. כל קריאה לפונקציה ממתינה להשלמת הקריאה הבאה לפני שהיא מסתיימת, וכך נוצרת שרשרת של קריאות שבסופו של דבר חוזרת לאחור עד למי שקרא לפונקציה המקורית.