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

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

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

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

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

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