המגדל הלוהט 2: הנקמה

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

רקורסיה, באופן כללי, היא פעולה שמוגדרת באמצעות עצמה - אבל כדי שלא תהיה לנו לולאה אינסופית, ההגדרה היא באמצעות גרסה “קצת יותר פשוטה” של עצמה, ועבור גרסה פשוטה מאוד של עצמה, היא מוגדרת ישירות. כך למשל סדרת פיבונאצ'י מוגדרת באמצעות רקורסיה: כל איבר בה שווה לסכום שני קודמיו פרט לשניים הראשונים, שמוגדרים להיות 0 ו-1 (או 1 ו-1, תלוי את מי שואלים). אם ה”פעולה” לא ברורה כל כך מההגדרה הזו, חישבו על הפעולה של “לחשב את האיבר ה-n בסדרת פיבונאצ’י” - כדי לבצע את הפעולה הזו, פרט למקרה הטריוויאלי שבו n=0 או n=1, תיאלצו לחשב קודם כל את שני האיברים הקודמים בסדרה - כלומר, לבצע את אותה הפעולה, אבל וריאציה “יותר פשוטה” עליה (בפועל אין בכך צורך כי יש נוסחה סגורה לסדרת פיבונאצ’י, אבל זה לא העניין כאן).

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

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

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

\( f(n)=n\cdot f(n-1) \)

\( f(0)=1 \)

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

function factorial(n)

if n=0 return 1

else return n*factorial(n-1)

end of function

אני מקווה שהקוד קריא גם לאלו שאינם מכירים כלל תכנות. השורה הראשונה היא הכותרת של הפונקציה: כתוב שם שהיא בכלל פונקציה, מה השם שלה (factorial), ומה הפרמטר שהיא מקבלת (n). בשורה הבאה בודקים האם מתקיים "תנאי ההתחלה" של \( n=0 \). אם כן - הפונקציה מחזירה את הערך 1. אם לא, הפונקציה מחזירה \( n \) כפול התוצאה של הפעלת עצמה על ערך מספרי קצת פשוט יותר - \( n-1 \).

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

1. העבר את n-1 הטבעות העליונות ממוט המקור למוט העזר.
2. העבר את הטבעת שנותרה במוט המקור למוט היעד.
3. העבר את n-1 הטבעות ממוט העזר למוט היעד.

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

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

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

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

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

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