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

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


תחשבו עצים

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

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

גם כאן פעלה רקורסיה

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


לכל כלל יש יוצא מהכלל

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

עץ תיקיות ותיקיות משנה

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

מחיקת-תיקיה-רקורסיבית (שם-תיקיה-למחיקה):
1. עבור כל תיקית משנה של שם-תיקיה-למחיקה בצע:
1.1 הכנס את שם-תיקיה-למחיקה + שם תיקית המשנה למשתנה תיקיה-זמנית
1.2 מחיקת-תיקיה-רקורסיבית (תיקיה-זמנית)
2. מחק את התיקיה שם-תיקיה-למחיקה

את אותה המשימה בדיוק יכול לבצע גם הקוד הלא-רקורסיבי הבא:

מחיקת-תיקיה-סתם (שם-תיקיה-למחיקה):
1. הכנס את שם-תיקיה-למחיקה למשתנה תיקיה-זמנית
2. כל עוד יש לתיקיה תיקיה-זמנית תת-תיקיות, הוסף ל-תיקיה-זמנית את שם תת-התיקיה הראשונה של תיקיה-זמנית
3. מחק את התיקיה תיקיה-זמנית
4. אם תיקיה-זמנית שונה משם-תיקיה-למחיקה חזור לשלב 1, אחרת סיים.

תיקיית X

דמיינו את פעולת הקוד על תיקיה בשם X, שיש לה שלוש תת-תיקיות B, A ו-C ולכל אחת מאלה שלוש תת-תיקיות בשם 1, 2 ו-3. אנו מתחילים בקריאה למחיקת-תיקיה-סתם עם הערך "X". בשלב 1, המשתנה הזמני יקבל את הערך "X". בשלב 2 יתווספו אליו הערכים "A" ואחריו "1", ונקבל "XA1". לתיקיה זו אין תת-תיקיות, ולכן היא תימחק בשלב 3. התהליך יתחיל מהתחלה, והפעם נגיע ל-"XA2". אחרי שהיא ו-"XA3" ימחקו, התהליך יעצור ב-XA מכיוון שמחקנו את כל תת-התיקיות שלה, וכשגם היא תימחק נגיע ל-XB1 וכן הלאה. בסופו של דבר לא יישארו ל-X תת-תיקיות, היא תימחק בשלב 3, ומכיוון ששם התיקיה הזמני שווה עכשיו ל-"X", תנאי הסיום שבשלב 4 ייצא מהפונקציה.

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


כללי אצבע נוספים

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

נניח שיש לנו פונקציה שפותרת תרגילי חשבון פשוטים, ללא סוגריים, כמו 1+2 או 3*7^2 (כאשר הסימן ^ מסמל חזקה). אנחנו צריכים לפתור בעזרתה תרגיל שמכיל סוגריים, כמו ((1+2) * (3+4)) ^ 2. איך עושים את זה? גם כאן יש לנו קינון של סוגריים אלה בתוך אלה, ואיננו יכולים לדעת מראש עד לאיזה עומק נצטרך לרדת כדי להגיע לתרגילים הבסיסיים. אם נפתח קוד שמסוגל לזהות זוגות סוגריים מתאימים, הוא יוכל לפתור את התרגיל בעזרת רקורסיה: הוא יקרא לעותק של עצמו עם תת-התרגיל (1+2) * (3+4) – התוכן של הסוגריים הראשונים – והעותק הזה של הפונקציה יקרא לעותקים של עצמו פעמיים, פעם עם 1+2 ופעם עם 3+4. התשובה לתרגילים הפשוטים הללו תוזן בחזרה למחרוזת שבעותק הקורא, כך: 3 * 7, והתשובה של התרגיל הפשוט הזה תוחזר למחרוזת שבה התחיל כל העסק, כך: 21 ^ 2. מכאן אין שום בעיה להגיע לתשובה הסופית.

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


תהנו :]


תודה ל- nana10.