כיצד להסביר רקורסיה ללומדים מתחילים

ס. היינס

Haynes, S.M. (1995). Explaning recursion to the unsophisticated. SIGCSE Bulletin Vol. 27, No. 3, 3-6.

התקציר המצורף נערך ע"י ד"ר דלית לוי

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

הוצאת "מחשבה" – מרכז המורים הארצי למדעי המחשב, 2001. עמודים 56-61.

 

אודות המאמר

במוקד המאמר הנוכחי עומדות גישות להסבר כיצד מתבצע אלגוריתם רקורסיבי נתון. נקודת המוצא של הכותב היא שהאלגוריתם הרקורסיבי, כאשר הוא נרשם באמצעות שפת תכנות, נותן למעשה ביטוי להגדרה אינדוקטיבית של בעייה כלשהי. אבל ההגדרה האינדוקטיבית הזו היא קומפקטית ומופשטת, כך שמתכנתים מתחילים מתקשים בהבנתה. לכן מתאר  הכותב מספר דרכים ידועות להסבר של אלגוריתם רקורסיבי נתון ומציע דרך אחת חדשה אותה הוא מכנה "גישת עץ ההפעלה". השימוש בגישת עץ ההפעלה נוסה על ידי הכותב בהצלחה עם סטודנטים מתחילים הלומדים מדעי המחשב. המאמר מתאר את הגישה ומדגים אותה באמצעות התייחסות לפונקציית אקרמן הרקורסיבית, הנתונה בשפת C. כמו כן מתייחס המאמר לאופן שבו ניתן לקשר בין הגישה המוצעת לבין יצירתן של הגדרות אינדוקטיביות. [הגדרה אינדוקטיבית היא המונח המוצע על-ידי הכותב עבור מה שכונה בחלק הראשון של סקר הספרות 'הגדרה רקורסיבית', ראו תרשים 1 במבוא,ד"ל].

 

רשימת מושגים

w אינדוקציה - Induction            

w טיול לעומק בעץ - Tree depth first traversal

w מחסנית הפעלה - Runtime stack

w מספרי פיבונצ'י –numbers   Fibonacci

w עץ הפעלה - Activation tree

w עץ, צמתים ועלים - Tree, nodes and leaves

w פונקצית אקרמן – ackermann function

w רשומת הפעלה - activation record

הגדרת הבעייה

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

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

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

 

גישות להסבר המושג רקורסיה

א. גישת האינדוקציה

בגישה זו מביאים את ההגדרה של הפונקציה, כלומר – הפונקציה מוגדרת במונחים שלה עצמה ושל מקרה בסיסי. ההגדרה של ביטויים בשיטת BNF היא דוגמה אחת כזו. ההגדרה האינדוקטיבית של סדרת פיבונצ'י היא:

Fib(k)=Fib(k-1) + Fib(k-2);

Fib(2)=1;

Fib(1)=1;

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

ב. גישת המחסנית

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

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

ג. גישת המעקב

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

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

ד. גישת העץ הרקורסיבי

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

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

ה. גישת עץ ההפעלה

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

דוגמה לשימוש בגישת עץ ההפעלה

כדי להסביר מהו עץ הפעלה, נשתמש באותו מתכון אותו ניתן לתת גם לתלמידים. ניקח לדוגמה את פונקציית אקרמן, הרשומה להלן בתחביר של שפת C [ובניסוח מתמטי מקובל – ד"ל].

int ack(int m, int n) {

      if (m==0) return (n + 1);                                                                                                n+1                         m=0

      if (n==0) return (ack (m-1,1) );                                            f(m,n) =           f (m-1,1)                 n=0

      return (ack (m –1, ack (m, n – 1) ) );                                                           f(m-1,f(m,n-1))

       }

הוראות:

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

1.     בנו תבנית של רשומת הפעלה. על התבנית להכיל את שם הפרוצדורה, הפרמטרים, והערך המוחזר.

           תבנית ack                                                                           תבנית כללית

 

 

 


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

int ack(int m, int n) {

      if (m==0) return (n + 1);

      if (n==0) return (ack1 (m-1,1) );

      return (ack2 (m –1, ack3 (m, n – 1) ) );

       }

3.     ציירו את עץ ההפעלה באמצעות מעקב אחר התכנית. התחילו עם ההפעלה הראשונה של הפרוצדורה, וציירו בשורש של העץ את התבנית עם הערכים המתאימים של הפרמטרים והמשתנים המקומיים.

4.     כל קריאה לפרוצדורה מיוצגת בעץ כצומת-בן של הצומת הנוכחי. כדי לבצע את הקריאה, יש לרדת למטה לצומת החדש.

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

לדוגמה: אם A מפעיל את B העץ נראה כך –

ואם A מפעיל את B ולאחר מכן את C ואת A, העץ נראה כך –

 

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

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

5.       החזרה מהפרוצדורה משמעותה מילוי הערך המוחזר בתבנית, ועלייה בעץ לצומת האב. העלים בעץ מייצגים פרוצדורות שאינן מפעילות פרוצדורות אחרות.

6.       הביצוע הדינמי של התכנית תואם את "הטיול לעומק" (depth-first traversal) בעץ ההפעלה.

 

כדי להשלים את  הדוגמה, ניתן להביא את המעקב אחר פונקצית אקרמן כאשר ערכי הפרמטרים ההתחלתיים שלה הם m=2 ו n=1. נתבונן לשם כך בהדפסות המעקב המובאות בעמוד הבא, ונשווה אותו לעץ ההפעלה המתאים המובא לצד המעקב. שימו לב לסימונים א,ב,ג,ד,ה במקומות תואמים בהדפסת המעקב ובעץ ההפעלה. 

[במאמר המקורי מתוארת דוגמה נוספת, של פונקציה לחישוב מספרי פיבונצ'י – ד"ל].

 

עץ הפעלה                                                                                    הרצת מעקב

> (ack 2 1)

Entering: ack, Argument list: (2 1)            -- א

  Entering: ack, Argument list: (2 0)        

    Entering: ack, Argument list: (1 1)  -- ב

      Entering: ack, Argument list: (1 0)

        Entering: ack, Argument list: (0 1) -- ג         

        Exiting: ack, Value: 2

      Exiting: ack, Value: 2

      Entering: ack, Argument list: (0 2)    

      Exiting: ack, Value: 3

    Exiting: ack, Value: 3

  Exiting: ack, Value: 3

  Entering: ack, Argument list: (1 3)

    Entering: ack, Argument list: (1 2) -- ד

      Entering: ack, Argument list: (1 1)

        Entering: ack, Argument list: (1 0)

          Entering: ack, Argument list: (0 1)

          Exiting: ack, Value: 2

        Exiting: ack, Value: 2

        Entering: ack, Argument list: (0 2)  

      Exiting: ack, Value: 3

      Entering: ack, Argument list: (0 3)

      Exiting: ack, Value: 4

    Exiting: ack, Value: 4

    Entering: ack, Argument list: (0 4) -- ה

    Exiting: ack, Value: 5

  Exiting: ack, Value: 5

Exiting: ack, Value: 5

 

המעבר לשימוש בגישת האינדוקציה

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

נתבונן למשל בעץ שיצוייר עבור ביצוע של חישוב האיבר השישי של מספרי פיבונצ'י. העץ מראה כיצד לצומת של הפעלת Fib 6 יש שני בנים, כלומר החישוב של הערך המוחזר מ- Fib 6  עושה שימוש בערכים המוחזרים מההפעלות של Fib 5 ו- Fib 4

[הדוגמה המקורית המובאת במאמר היא של הפעלת Fib 5. כדי למנוע בלבול בין הפרמטר של ההפעלה הזו לבין הערך המוחזר, בחרתי לתאר כאן את הפעלת Fib 6 שבה הפרמטר שונה מהערך המוחזר, ד"ל].

השימוש בתיבה מיוחדת עבור הערכים המוחזרים מכל הפעלה מקלה אף היא על הלומדים. עתה נותר רק להחליף את המקרה הפרטי של הפרמטר 6 בהפעלה של Fib 6 בפרמטר כללי n, ומבנה העץ כבר ממחיש את השימוש אותו Fib (n) עושה בערכים של Fib (n-1) ו- Fib (n-2). העלים של העץ תואמים כמובן למקרה הבסיסי - base case (או למקרים הבסיסיים) של ההגדרה האינדוקטיבית.

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

מסקנות

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

חזרה לאתר המרכז הארצי

חזרה להבטים ינואר 2002

חזרה לאתר סקר ספרות