רקורסיה
הוצג| English | משמעות |
|---|---|
| recursive/rɪˈkɜːsɪv/ | רקורסיבי |
| base case/beɪs keɪs/ | מקרה בסיסי |
| recursive case/rɪˈkɜːsɪv keɪs/ | מקרה רקורסיבי |
| call stack/kɔːl stæk/ | ערימת קריאות |
| stack frame/stæk freɪm/ | מסגרת ערימה |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | שפע ערימה |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | ממוחזור |
הגדרה המכילה את עצמה
- איך אומרים מה הוא איל? ההורה שלך הוא איל. גם האיל של ההורה שלך הוא איל. שתי המשפטים הללו מגדירים שרשרת בלתי מוגבלת, והמשפט השני משתמש במילה שהוא מגדיר.
- זוהי לא ערעור מעגלי, משום שהמשפט הראשון מספק נקודת עצירה לשרשרת. ללא כך, ההגדרה הייתה מתפרקת לנצח.
- תוכניות יכולות להיכתב באותו אופן, ובמקרים שבהם הבעיה דומה לשרשרת זו, פתרון רקורסיבי קצר משמעותית ממלולך (loop).
- שיעור זה עוסק ב-מקרה הבסיס וב-מקרה הרקורסיבי, בעקבת צירוף רקורסיבי ובמה שמבצע ערמת הצירופים (call stack) בתחתית.
שני המקרים
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- ה-מקרה הבסיס הוא גרסה של הבעיה הקטנה מספיק כדי לענות עליה ישירות, ללא צירוף נוסף. הוא מה שעוצר את הרקורסיה.
- ה-מקרה הרקורסיבי מרחיק צירוף חדש של הפונקציה עם כניסה קטנה יותר, וקדמה לעבר המקרה הבסיס.
- שניהם נדרשים. רקורסיה ללא מקרה בסיס לעולם לא תיגמר; אחת שבה הכניסה אינה מצטמצמת לעולם לא תגיע למקרה הבסיס.
לכל אלגוריתם רקורסיבי חייב להיות מקרה בסיסי כי:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
המקרה הבסיסי הוא התנאי שמסתיים את שרשרת הקריאות; ללאו, הרקורסיה רצה לנצח.
רקורסיה מתאימה באופן טבעי לבעיות בעלות חזרה על עצמן (עצים, פירוק-ושליטה), אך כל קריאה מוסיפה מסגרת סטאק — ולכן ללא מקרה בסיסי זה גורם להתפרצות זיכרון בסטאק.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לולאת ספירה פשוטה היא נקייה יותר עבור איטרציה רגילה; רקורסיה זווחה כאשר הבעיה מכילה עותקים קטנים של עצמה.
מה חייב להיוות פרוצדורת רקורסיבית כדי שהיא תסתיים? סמן את כולן האפשרויות החלות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
מקרה בסיסי לבדו אינו מספיק: אם הקלט מעולם לא מתקטן, המקרה הבסיסי לעולם לא ייגש ומסגרות מצטברות עד להתפרצות זיכרון בסטאק.
דוגמה פתורה: עקיבת רקורסיה
- עקוב אחר
Factorial(4). - ריכוז:
Factorial(4)זקוק ל-4 * Factorial(3), שזקוק ל-3 * Factorial(2), שזקוק ל-2 * Factorial(1). עדיין לא进行了 כפל כלשהו; כל צירוף מחכה. - מקרה בסיס:
Factorial(1)מחזיר 1 ללא ביצוע צירופים נוספים. - פירוק:
2 * 1 = 2מחזיר ערך, ולאחר מכן3 * 2 = 6, ולאחר מכן4 * 6 = 24. - יש להציג את שני הכיוונים. עקבה שולכת רק למטה או רק חוזרת, מאבדת חצי מהנקודות.
ריקורסיה מתפרקת מהעלים כלפי מעלה
עבור את fib(4) בסדר שבו הקריאות למעשה נגמרות: העלים (מקרים בסיסיים) נפתרים תחילה, ולאחר מכן כל אב משלב את הילדים שלו. שים לב ש-fib(2) מחושב פעמיים — העבודה המוחזרת הזו היא הסיבה שהריקורסיה פשוטה איטית.
מה Factorial(4) מחזיר?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
4 × 3 × 2 × 1 = 24.
מה המכונה עושה
- לכל צירוף נדרשת העתכה משלו של הפרמטרים והמשתנים המקומיים שלו, מכיוון ש-
Factorial(3)ו-Factorial(2)הם צירופים שונים עם ערכים שונים שלn. - העתכות אלו נמצאות ב-מסגרת ערמה (stack frame) ב-ערמת הצירופים: מסגרת אחת לכל צירוף正在 ביצוע, המכילה את הפרמטרים, המשתנים המקומיים ואת כתובת החזרה.
- מסגרת נדחפת (pushed) בכל צירוף ומוסרת (popped) כאשר היא מחזירה ערך. זוהי הסיבה לכך שהערכים חוזרים בסדר הפוך לסדר הצירופים: ערכת הצירופים היא ערמה, בדיוק כמו ADT מהנושא 10.
סדר את אירועי הערכת Factorial(4).
Difficulty 3/5 · 200 coins + a small bonus on first completion today
אין כפל בדרך כלפי מטה; כל שיחה ממתינה. הכפלות מתבצעות כולן כאשר הגרעית נפרשת.
מה עלול לקלקל
- אין מקרה בסיס, או מקרה בסיס שמעולם לא מושג: הרקורסיה לעולם אינה נפסקת, הפריימים מצטברים והסטק של הקריאות מתמלא. זהו גלישת סטק.
- רקורסיה עמוקה: גם רקורסיה נכונה בעומק של מיליון רמות דורשת מיליון פריימים, ולכן יכולה לגרום לניצול זיכרון שבו לופ יתבצע ללא שימוש בזיכרון נוסף.
- עבודה חוזרת: אלגוריתם פיבונאצי רקורסיבי תמיטי מחשבב מחדש את אותם ערכים מספר פעמים אקספוננציאליות. ניתן לפתור זאת עם לופ, או עם זיכרון מעטפת (Memoisation), על ידי אחסון כל תוצאה בפעם הראשונה שהיא מחושבת.
התאם כל מונח הקשור לרקורסיה למשמעותו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
רקורסיה זקוקה למקרה בסיסי כדי להפסיק ולמקרה רקורסיבי כדי לצמצם את הבעיה; כל שיחה מוסיפה מסגרת גרעית.
מסגרת גרעית עבור שיחת פונקציה מכילה:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל מסגרת שומרת את הפרמטרים, המשתנים המקומיים והיכן להמשיך של השיחה שלה — כך שהשיחות אינן דוחקות זו את זו.
כל שיחה בתהליך שמירה על הפרמטרים והמשתנים המקומיים שלה במסגרת ____ משלה על גרעית השיחות.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
נדחפת בעת השיחה, מופקת בעת החזרה. זהו הסיבה לכך שערכים חוזרים בסדר הפוך מהסדר שבו הועשו השיחות.
רקורסיה מול איטרציה
- רקורסיה מתאימה לבעיות חוזרות-עצמי, בהן הבעיה מכילה העתק קטן משלה: טרברסיה על עצים, גישת "חלק-וקה" כגון חיפוש בינארי ושייף מיזוג, והשרשרת האבות המוזכרת למעלה.
- איטרציה מתאימה לכל שאר המקרים, ואינה דורשת זיכרון נוסף עבור ההתחזרות.
- כל בעיה שניתן לפתור באמצעות רקורסיה ניתנת לפתרון באיטרציה, והדבר נכון גם להפך. הבחירה היא בין מה שמתאר את הבעיה בצורה ברורה יותר, לבין עלות הזיכרון של הסטק.
תוכנית רקורסיבית קורסת בשל גביעת סטק. איזה הסבר הוא נכון?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
גביעת סטק היא עניין של מסגרות, לא אריתמטיקה. מספר גדול מדי עבור הרגיסטר שלו הוא גביעה אריתmetic, דבר שונה לחלוטין.
דוגמה מפורטת: ציינו את הסיכונים
- תלמיד כותב פונקציה רקורסיבית והיא קורסת בגלישת סטק. ציינו שתי סיבות אפשריות.
- אין מקרה בסיס, או שהמקרה הבסיסי לעולם לא מושג כי הקלט אינו הופך לקטן בכל קריאה, ולכן הקריאות ממשיכות לנצח והפריימים מצטברים.
- הרקורסיה נכונה אך עמוקה מדי: כל אחת מקריאות הרבות מאוד שומרת על פריימת הסטק שלה, והסטק של הקריאות מתמלא בזיכרון לפני שהמקרה הבסיסי מושג.
- שתי הסיבות עוסקות במצטברות פריימים. ציינו מה מצטבר ומדוע המצטבר הזה אינו מפסיק.
סימונים נופלים מהיד
- לרקורסיה דורשים שניהם: מקרה בסיס וקלט הופך לקטן. ציון מקרה בסיס בלבד הוא חצי מהתנאי.
- בטרייס, הדגימו את הקריאות מתקדמות ואת הערכים חוזרים. שני הכיוונים מובילים לציון.
- לכל קריאה יש פרמטרים ומשתנים מקומיים משלו בתוך פריימת סטק משלו. זוהי הסיבה לכך שרקורסיה דורשת זיכרון שאיטרציה אינה דורשת.
- גלישת סטק היא ספק בזיכרון הסטק עקב too many frames, ולא גלישה אריתמטית.
הבנתך מושלמת
- פונקציה רקורסיבית דורשת מקרה בסיס שפתור ישירות ומקרה רקורסיבי שמקרא את עצמו עם קלט קטן יותר
- לבצע טרייס בשני הכיוונים: קריאות מתקדמות למקרה הבסיס, ולאחר מכן ערכים חוזרים בחזרה
- לכל קריאה יש פריימת סטק משלה על סטק הקריאות, שנדחפת בקריאה ונשלפת בחזרה, דבר שמסביר מדוע רקורסיה דורשת זיכרון
- סיכונים: מקרה בסיס שאינו מושג גורם לרקורסיה אינסופית וגלישת סטק, רקורסיה עמוכה מזהרת זיכרון, ועבודה חוזרת דורשת לופ או זיכרון מעטפת