אין כאן לולאה

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

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

אין כאן לולאה

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

טוב, בערך.

עם כזו חידה אני חושבת שאני יכולה להסתדר.

אז למה יש כאן אתגר?

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

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

היינו מעבירים את חלק החוט המסומן בחץ אדום קטן לאורך הקו המקווקו ומחלצים את החוט. עכשיו יש לנו ביד אלגוריתם^[2] קטן שיודע להעביר חוט מצד אחד של לולאה שתקוע לה צ'ופצ'יק באמצע, לצד השני שלה:

• העבר חוט מצד אחד לצד שני של הלולאה (A -> E)
  • העבר חוט מצד אחד לצד השני של הצ'ופצ'יק מתחת ללולאה (B -> C)
  • העבר חוט מצד אחד לצד השני של הצ'ופצ'יק מעל הלולאה (D -> E)

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

בעיה בתוך בעיה בתוך בעיה בתוך…

ההגדרה הוויקיפדית לרקורסיה היא:

רֵקוּרְסִיָּה (בעברית: נסיגה) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה, כך שהיא מתרחשת ומשתקפת בשלמותה בתוך עצמה שוב ושוב.

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

גם אלגוריתמים יכולים להיות רקורסיביים. אלגוריתם רקורסיבי, הוא אלגוריתם שעושה שימוש במופע של עצמו. אלגוריתם אריה במדבר הוא דוגמת בית-ספר קלאסית (אם כי דבילית במקצת), והוא הולך ככה:

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

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

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

אז איך הרעיון של רקורסיה עוזר לנו?

אם נחזור לבעיה שעל הפרק נשים לב שהיא בנויה בצורה רקורסיבית גם כן – בתוך הלולאה הראשונה תקועה לולאה נוספת, שבתוכה תקועה לולאה נוספת שבתוכה… עד לסף העצירה – בלולאה האחרונה תקוע צ'ופצ'יק ולא לולאה. אנחנו גם יודעים איך לפתור את החידה כשהיא "קטנה מספיק", כלומר – בנויה רק מלולאה וצ'ופצ'יק^[3].

עכשיו נעיף מבט קרוב יותר בצעצוע (קליק לתמונה בגודל סביר).

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

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

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

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

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

-=-

^[1] וכאן שאלה מעניינת – איך מפרמלים את הרעיון האינטואיטיבי ששתי צורות מורכבות הן לולאות שלובות ובונים אלגוריתם לגילוי צורות כאלה?
^[2] סדרת צעדים
^[3] הערה קטנה לקפדנים – למעשה, לולאה שתקוע בתוכה צ'ופצ'יק מייצגת שני שלבים ברקורסיה והבעיה הפשוטה ביותר היא צ'ופצ'יק בודד, אבל עזבו אתכם – אם לא שמתם לב, זה לא פוסט פורמלי במיוחד.