רקורסיה: מהמחשה לתכנית
|
|
|
ד"ר מרדכי בן-ארי ונורית רייך |
|
|
המחלקה להוראת המדעים, מכון ויצמן למדע, רחובות, ישראל 76100 |
|
|
ntbenari@wis.weizmann.ac.il |
|
|
|
|
|
מבוא |
|
|
|
|
|
מורים למדעי המחשב פיתחו שיטות
המחשה רבות המיועדות לסייע לתלמיד בהבנת אלגוריתמים רקורסיביים מופשטים. השאלה
המטרידה אותנו היא: מה הקשר בין ההמחשות (למשל בובת המטרושקה) לבין האלגוריתמים
(למשל פונקצית העצרת)? לעתים יש לנו הרגשה שההמחשה מובנת, אך קשה לתלמידים ליישם
את הבנת ההמחשה בהבנת האלגוריתם. |
|
|
במסגרת הקורס "יסודות
מדעי המחשב", פיתחנו זוגות של המחשה + אלגוריתם, כאשר מבנה ההמחשה תואם
בדיוק את מבנה האלגוריתם. לאחר שנגמר ה"כיף" של משחק ההמחשה, ניתן
להסביר את האלגוריתם תוך התייחסות ישירה להמחשה המקבילה. |
|
|
|
|
|
ברצוננו לשתף את
הקוראים בשתי המחשות חדשות שפיתחנו: |
|
|
א. בניית שרשרת הממחישה
פונקציה רקורסיבית כגון חישוב פונקצית העצרת. |
|
|
ב. אכילת שוקולד הממחישה
אלגוריתם עם זימון רקורסיבי כפול כגון מיון Quicksort . |
|
|
המחשה ראשונה - בנית שרשרת |
|
|
|
|
|
גד, רחל, דינה ויוסי, ילדיה
המסורים של אימא החליטו להפתיע אותה בשרשרת שהכינו בעצמם. כל אחד מהילדים החזיק
חוליה אחת של השרשרת בידו, וידע לחבר חוליה זו לחוליה אחרת. מה עושים? כיצד
מרכיבים את השרשרת כולה? ישבו הילדים, חשבו וחשבו, ולבסוף מצאו עצה. |
|
|
הכריז גד : אם תהיה לי שרשרת בגודל 3 חוליות אז אחבר לשרשרת את החוליה שלי ונקבל
שרשרת בת 4 חוליות שאותה אתן לדן
. ובכן, רחל דאגי לי בבקשה לשרשרת
בת 3 חוליות. |
|
|
הכריזה רחל : אם תהיה לי
שרשרת בגודל 2 חוליות, אחבר אליה את החוליה שלי ונקבל שרשרת בת 3 חוליות שאותה
אתן לגד. ובכן דינה, דאגי בבקשה לשרשרת בת 2 חוליות. |
|
|
הכריזה דינה : אם תהיה לי
שרשרת בגודל 1 חוליה אז אחבר לשרשרת את החוליה שלי ונקבל שרשרת בת 2 חוליות
שאותה אתן לרחל. ובכן יוסי , דאג לי בבקשה לשרשרת בת 1 חוליה. |
|
|
הכריז יוסי : אם תהיה לי שרשרת בגודל 1 חוליה . . . אבל יש לי ! דינה, קחי בבקשה שרשרת בגודל 1 חוליה. |
|
|
שמחה דינה - חברה את החוליה שברשותה לשרשרת בת
1 חוליה ויצרה שרשרת בת 2 חוליות,
אותה העבירה לרחל. |
|
|
שמחה רחל - חברה את החוליה שברשותה לשרשרת בת
ה - 2 חוליות ויצרה שרשרת בת 3 חוליות, אותה העבירה לגד. |
|
|
שמח גד - חבר את החוליה שברשותו לשרשרת בת ה - 3 חוליות ויצר שרשרת בת 4
חוליות, אותה העביר לאימא בשם כל ילדיה. |
|
|
התלמידים יבצעו את ההמחשה תוך
בצוע האלגוריתם הבא: |
|
|
|
|
|
בנה-שרשרת-באורך ( N ) |
|
|
אם 1 = N אזי |
|
|
החזר חוליה |
|
|
אחרת |
|
|
שרשרת_חלקית
® בנה-שרשרת-באורך ( N-1 ) |
|
|
שרשרת_חלקית
® חבר שרשרת_חלקית + חוליה |
|
|
החזר
שרשרת_חלקית |
|
|
נשים לב לעובדה שכל תלמיד צריך
לבקש מחברו שיבצע תת משימה, והוא חייב להמתין עד לסיום ביצוע התת-משימה לפני
שהוא יכול להמשיך בבצוע המשימה שלו. מצב זה מקביל למצב ה"מוזר"
שבחישוב פונקצית העצרת, שלא ניתן להמשיך בחישוב הכפל לפני החזרה מהזימון
הרקורסיבי. |
|
ניתן להיעזר בתרשים הבא לשם
מעקב אחר מהלך האלגוריתם. תרשים במבנה זהה ישמש למעקב אחרי פונקציות רקורסיביות. |
|
בנה-שרשרת-באורך (4) אם N=1 . . { 4<>1 } אחרת שרשרת_חלקית ® בנה-שרשרת-באורך (3) אם N=1 . . { 3<>1 } אחרת שרשרת_חלקית
® בנה-שרשרת-באורך (2) אם
N=1 . .
{ 2<>1 } אחרת
שרשרת_חלקית ® בנה-שרשרת-באורך 1)) אם N=1 אזי { 1=1 }
החזר חוליה
שרשרת_חלקית ® שרשרת_חלקית +
חוליה
החזר שרשרת_חלקית שרשרת_חלקית ® שרשרת_חלקית +
חוליה החזר
שרשרת_חלקית שרשרת_חלקית ® שרשרת_חלקית + חוליה החזר שרשרת_חלקית |
|
|
|
|
|
המחשה שניה - אכילת שוקולד |
|
|
|
בעיה |
|
פתח אלגוריתם רקורסיבי שמקבל
כקלט חפיסת שוקולד ומפרק אותה לקוביות. ברגע שמתקבלת קובית שוקולד בודדת, יש
לאכול אותה. |
|
|
|
להלן אלגוריתם רקורסיבי לפתרון
הבעיה: |
|
|
|
אלגוריתם-לאכילת-קוביות-שוקולד |
|
|
|
אם יש רק קוביה אחת אזי |
|
אכול אותה |
|
אחרת |
|
שבור את
החפיסה לשתי חפיסות |
|
הפעל
את האלגוריתם-לאכילת-קוביות-שוקולד |
|
(על חפיסה קטנה אחת) |
|
הפעל
את האלגוריתם-לאכילת-קוביות-שוקולד |
|
(על חפיסה
קטנה שניה) |
|
|
|
באלגוריתם זה, כל שבירה של
חפיסת שוקולד מייצרת שתי תת-משימות חדשות הדורשות הפעלה רקורסיבית של האלגוריתם. |
|
בזמן הדגמת פירוק השוקולד לקוביות, יש להביא לתשומת לב הכתה
את המספר הרב של התלמידים שברשותם
חפיסות שוקולד חלקיות ביד הממתינים לתורם על מנת להמשיך במשימתם. מצב זה
מקביל למצב באלגוריתמים רקורסיביים כגון Quicksort . |
|
נשים לב שתלמיד אחד או שניים
יאכלו את כל הקוביות. בכתות מתקדמות ניתן לנצל עובדה זו על מנת להסביר את פעולת
המחסנית. (רצוי להביא חפיסות שוקולד נוספות וזאת על מנת שלא לקפח את שאר
התלמידים.) |
|
|
|
|
|
סיכום |
|
|
|
במאמר זה אנו מביאים שתי
המחשות המקבילות למבנה של אלגוריתמים רקורסיביים: אלגוריתם לחישוב פונקציה
ואלגוריתם המשתמש בזימון רקורסיבי כפול. המחשות אלה עוזרות משמעותית להבנת הנושאים האלה כי הן תואמות את מבנה
האלגוריתמים. מניסיונות שערכנו עם תלמידים ועם צוותי מורים נוכחנו כי שילוב המחשות אלה בחומר הלימוד עזר בהטמעת
הנושאים. |