את בעיית מגדלי האנוי ניתן לפתור בקלות יחסית באמצעות רקורסיה. ניסיון לפתור את בעיית מגדלי האנוי מבלי להשתמש ברקורסיה יסתיים קרוב לוודאי בקוד ארוך משמעותית שקשה להבינו.
מהי בעיית מגדלי האנוי?
בבעיית מגדלי האנוי יש 3 עמודים (מקובל למספר אותם: 1, 2 ו-3). על אחד העמודים מונחות דיסקיות בגדלים שונים (באופן שבו כל דיסקית נמצאת בהכרח – ישירות או בעקיפין – מעל דיסקיות גדולות ממנה). האתגר הוא להעביר את כל הדיסקיות מהעמוד שעליו הן נמצאות לאחד העמודים האחרים, כאשר בכל שלב מותר להעביר דיסקית אחת בלבד, ובשום שלב אסור שדיסקית תהיה מעל (ישירות או בעקיפין) דיסקית אחרת קטנה ממנה.
כבר בהסתכלות ראשונית על בעיית מגדלי האנוי ניתן להסיק שככל שמספר הדיסקיות גדול יותר כך הבעיה מורכבת יותר. כמו כן, ניתן די בקלות להסביר את הפיתרון כאשר יש דיסקית אחת, שתי דיסקיות, ושלוש דיסקיות. בשלב זה, רוב הסטודנטים עושים את אחת הטעויות הגדולות בניסיונם להתמודד עם הבעיה, ומנסים לתאר לעצמם כיצד ייראה הפיתרון כאשר יש ארבע דיסקיות, חמש דיסקיות, ויותר. ניסיון לדמיין את הפיתרון כאשר מספר הדיסקיות גדול משלוש גורם לתסכול מתמשך.
המאפיינים של בעיות תכנותיות שפותרים באופן רקורסיבי
לרוב בעיות התיכנות שאנו פותרים באופן רקורסיבי יש מאפיין שאפשר להצביע עליו כעל דרגת הקושי (במקרה של מגדלי האנוי, מספר הדיסקיות שאנו נדרשים להעביר מעמוד מסויים לעמוד אחר הוא גם דרגת הקושי), ניתן לתאר את הפיתרון לבעיה מדרגת קושי n תוך שימוש בפיתרון לבעייה כשדרגת הקושי היא n-1 (בהמשך נסביר כיצד זה ייעשה בפיתרון לבעיית מגדלי האנוי), וקיים פיתרון ברור כאשר דרגת הקושי היא הנמוכה ביותר (במקרה של מגדלי האנוי דרגת הקושי הנמוכה ביותר היא 1. כאשר יש דיסקית אחת בודדת שנדרשים להעבירה מעמוד מסויים לעמוד אחר הפיתרון מאד פשוט).
הפיתרון לבעיית מגדלי האנוי באופן רקורסיבי
נניח, למשל, שעל עמוד 1 יש 4 דיסקיות, ויש צורך להעבירן לעמוד 3. במקרה כזה, בהנחה שקיים פיתרון לבעיית ההעברה של 3 דיסקיות מעמוד 1 לעמוד אחר (לעמוד 2, למשל) אפשר יהיה להשתמש בפיתרון זה כדי להעביר 3 דיסקיות מעמוד 1 לעמוד 2, את הדיסקית שנותרה נעביר לעמוד 3, ואז נשתמש שוב בפיתרון שקיים להעברת 3 דיסקיות כדי להעביר את 3 הדיסקיות מעמוד 2 לעמוד 3. כעת, נתייחס לבעיית ההעברה של 3 דיסקיות מעמוד 1 לעמוד אחר כבעיה שאותה נוכל לפתור באמצעות הפיתרון להעברת 2 דיסקיות מעמוד 1 לעמוד 3, ומייד אחר כך נעביר דיסקית נוספת לעמוד 2, ומייד אחר כך נעביר את 2 הדיסקיות מעמוד 3 לעמוד 2, וכך תושלם ההעברה של 3 דיסקיות מעמוד 1 ל-2. בשלב הבא אפשר להתייחס לבעיית ההעברה של 2 דיסקיות כבעיה שניתן לפתור באמצעות הפיתרון הפשוט להעברת דיסקית בודדת.
הפיתרון לבעייה מדרגה n תוך שימוש בפיתרון לבעיה מדרגה n-1
כיוון ששלוש העמודים מוספרו במספרים 2,1 ו-3, וכיוון שסכום המספרים הוא 6, ניתן לסכם ולומר שכאשר יש צורך להעביר דיסקית (או דיסקיות) מעמוד שמספרו x לעמוד שמספרו y, המספר של העמוד הנותר הוא התוצאה של החסרת x ו-y מ-6. כעת ניתן לנסח את הפיתרון לבעייה מדרגה n באופן הבא:
moving n-1 disks from x to 6-x-y
move 1 disk from x to y
moving n-1 disks from 6-x-y to y
בפונקציה הרקורסיבית שניצור אנחנו נעשה שימוש בפיתרון זה תוך קריאה להפעלת אותה פונקציה בכל אחד משלושת השלבים. הפונקציה תיבנה בצורה כזו כך שמייד עם הפעלת ייבדק האם n שווה ל-1, כיוון שבמקרה ש-n שווה ל-1 אז הפיתרון מאד פשוט (אין צורך להשתמש בפיתרון לבעיה מדרגה n כפי שניסחנו). בווידאו שבקישור https://youtu.be/zfE81wCbNCo?si=y4jzh8BJc4Vt_gUe ניתן למצוא הסבר מפורט תוך שימוש בשפת התכנות #C.
במידה שגם אתם סובלים מתסכול רב מניסיונות חוזרים ונשנים להבין את הפיתרון לבעיית מגדלי האנוי אני ממליץ בשלב ראשון לשאוף לכך שתצליחו להסביר בהיקף ובפירוט כפי שמוסבר בווידאו. אני ממליץ לצפות בווידאו ולוודא שכל הסבר קטנטן שמופיע בו מובן באופן מלא.
