מה זה רקורסיה ולמה היא מבלבלת בהתחלה

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

מה זה בכלל רקורסיה

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

הדוגמה הכי פשוטה - עצרת

בואו נסתכל על עצרת של מספר, נגיד 5!, שזה 5 כפול 4 כפול 3 כפול 2 כפול 1. אפשר לחשוב על זה בשתי דרכים.

הדרך הרגילה - לולאה - אומרת "תעבור על כל המספרים מ-1 עד 5 ותכפיל אותם אחד אחרי השני".

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

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

איך זה עובד בפועל במחשב

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

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

למה בכלל להשתמש ברקורסיה אם יש לולאות

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

הטריק שבאמת עוזר להבין

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

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

תתחילו את קורס התכנות הבסיסי כאן

לסיכום

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

תקועים על תרגיל רקורסיה? זה בדיוק המקום להישאל בו, בדיסקורד שלנו.

הצטרפו לקהילה בדיסקורד