מהי רקורסיה ?

רקורסיה / Recursion היא אחד מהנושאים שיש לתרגל ולהשקיע בו היטב לפני שנגשים לפתור איתה בעיות.

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

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

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

ראשית, נתחיל בהגדרה היבשה.

רקורסיה - Recursion

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

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

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

זה נשמע כמו לולאה אינסופית, אבל זה לא. אחרת זו תהיה שגיאה תכנותית.

אז איך זה עובד? 

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

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

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

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

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

חישוב של סכום מספרים מ-1 עד ל-n.

עבור n=1 התשובה היא כמובן 1.
עבור n=2 התשובה היא 3 (1+2)
עבור n=3 התשובה היא 6 (1+2+3)

ראשית, נפתור את הבעיה באופן הרגיל, כך שיהיה ברור לנו שהבנו על מה מדובר.

כעת, נפתור את הבעיה בצורה רקורסיבית:

הסבר

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

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

מקרה בסיס (base case) - הפתרון הטריביאלי והגרעיני ביותר של הבעיה. למשל, בפונקציה רקורסיבית של עצרת (Factorial) נגדיר כאן מה הפונקציה תחזיר עבור n=0 או n=1.

צעד רקורסיבי - הגדרת החיבור הלוגי בין מקרה הבסיס אל הצעד הבא המוביל לפתרון הבעיה הרקורסיבית.


נקח את הדוגמא הפשוטה שלנו.

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

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

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

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

נתייחס למצב בו n=2.

במצב זה, מן הסתם, תנאי העצירה לא יפעל. הפונקציה תחזיר את הערך של n שזהו 2 ותנסה לקבל את הערך של עצמה כאשר n=1.

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

בקריאה הבאה, n יהיה 1 ואת זה אנחנו כבר זוכרים, הפונקציה תחזיר מיידית 1.

יוצא שהפונקציה בקריאה המקורית שלה קיבלה תשובה ל n=1 ועכשיו יהיא יכולה להחזיר תשובה והיא 2+1.


אני אחזור בזריזות על מקרה נוסף כי אני יודע שזה קשה לקלוט בהתחלה.

נתייחס למצב בו n=3.

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

עבור n=2 ועבור n=1.

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

בשביל שאנחנו לא נתבלבל, נקרא להם בשמות, כאשר פונקציה a היא פונקצית המקור שלנו.

עבור פונקציה a  המספר n=3. היא מחכה לתשובה עבור n=2 והיא קוראת לפונקציה b.
עבור פונקציה b המספר n=2. היא מחכה לתשובה עבור n=1 והיא קוראת לפונקציה c.
עבור פונקציה c המספר n=1. היא מחזירה תשובה - 1 ונסגרת.
פונקציה b מחזירה תשובה 2+1 ונסגרת.
פונקציה a מחזירה תשובה 3+3 שהיא בעצם התשובה הסופית.

למי שזה עדיין לא ברור, אני ממליץ להריץ את הקוד של הפונקציה דרך Debugger או דרך Visualizer כמו זה הנמצא באתר http://pythontutor.com

אני אנסה להכניס כאן קישור ישיר לבעיה, בתקווה שזה יעבוד.

יעילות ברקורסיה

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

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

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

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

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

מתי אפשר לוותר על רקורסיה

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

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

סיכום

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

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

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

למעוניינים להרחיב את הידע שלהם בנושא, אני ממליץ על הקורס הבא: Recursion and Backtracking

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