אלגוריתים לפיתרון בעיית "מגדלי האנוי"

[assaf990]

א. מהו האלגוריתים לפיתרון בעיית מגדלי האנוי?

ב. יש דרך קצרה יותר ללא שימוש בריקורסיה?

[Qtec]

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

א. http://he.wikipedia.org/wiki/%D7%9E%D7%92%D7%93%D7%9C%D7%99_%D7%94%D7%90%D7%A0%D7%95%D7%99

[zurkin1232]

הרקורסיבית די פשוטה ומובנת.

האלגוריתם הוא:

בהינתן, למשל, מגדל בעל 5 קומות, הזז (ברקורסיה) את 4 הקומות העליונות מעמוד א' לעמוד ב'.

הזז את הקומה החמישית (התחתונה, שנשארה לבד) מעמוד א' לעמוד ג'.

הזז (שוב ברקורסיה) את 4 הקומות מעמוד ב' לעמוד ג' (על הגב של הקומה החמישית).

פשוט וקל, לא? כמה כיף שיש רקורסיה לפעמים

[שניצל]

סתם תיקון קטן - מגדלי האנוי.

[Boomerang]

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

[iceman90]

זה לא מה שהקומפיילר עושה, פשוט לא.

תהליך "הפוך לפתרון שהוא לא טכנית רקורסיה" נקרא פריסה ובמידה ולא משנים את האלגוריתם אין לו שום תועלת (מבחינת נוחות/יעילות)

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

קיצר... גלשנו..

מטי.

[Boomerang]

פשוט כן.

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

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

[sdfzxc]

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

[iceman90]

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

תודה.

מטי.

[Ghosthunter]

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

[zurkin1232]

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

[Boomerang]

ברוב המקרים ההבדל הוא לא משמעותי.

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

המקרה היחיד שבו הייתי להפוך רקורסיה ללולאה היה בתנאים לא סטנדרטיים (Stack מאוד קטן, ורקורסיית-זנב פשוטה יחסית).

[Holograph]

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

מקרה קצה שבו זה לא בהכרח הפיתרון העדיף הוא באלגוריתמיים רקורסיביים "מסוכנים": קח, לדוגמא, quicksort נאיבי שבוחר את האבר השמאלי כ-pivot, תן לו מערך ענק (נאמר, n=10000) ממויין מראש. תקבל עומק רקורסיה של 9999, שבקלות יכול לגרום ל-stack overflow. אחת הדרכים (הפחות אלגנטיות, לטעמי) להתמודד עם הבעיה הזו היא לממש את הרקורסיה באמצעות בלוק זיכרון שמתפקד כמחסנית - רקורסיה ידנית, בהיעדר תאור יותר מתאים - ולהגביל את הרקורסיה ע"י תנאי. כמובן שאפשר לממש את אותו פיתרון ע"י שליחת עומק הרקורסיה כפרמטר לפונקציה, אבל אז זה בזבזני אפילו יותר.