מסגרת להוראת רקורסיה

ג. פורד

Ford, Gary (1982). A framwork for teaching recursion. SIGCSE Bulletin 14(2), 32-39.

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

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

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

 

 

אודות המאמר

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

 

רשימת מושגים

w איטרציה - Iteration                

w זרימת בקרה – Flow of control

w מבני בקרה – Control structures         

w מיון בחירה – Selection sort

w מקרה פשוט ביותר –   Smallest instance

w פירוק בעייה – Problem decomposition

w פתרון בעיות – Problem solving

w רקורסיה - Recursion

הקדמה

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

בעת הצגת מושג תכנותי חדש, אנו נדרשים לענות על שתי שאלות:

1.                    מהו המושג?

2.                    כיצד משתמשים במושג?

בהמשך המאמר, מוצגות תשובות לשאלות אלה במקרה של המושג רקורסיה. 

מהי רקורסיה?

בתכנות פרוצדורלי ניתן להשתמש בשלושה סוגים של מבני בקרה:

(1) מבנה סדרתי – שבו משפטי התכנית מתבצעים על פי הסדר שבו הם רשומים.

(2) מבנה הסתעפות – המשמש לבחירה בין שני משפטים או יותר, או בין גושי משפטים (blocks).

(3) מבנה חזרה – המציין כי יש לחזור על ביצועו של משפט בתכנית או על ביצוע גוש של משפטים.

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

מבנה חזרה נראה כגוש של משפטים, שהאחרון בהם הוא משפט של החלטה האם לבצע שוב את הגוש אם לאו:

משפט-1

משפט-2

 .

 .

 .

משפט-n (החלטה אם לבצע שוב)

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

 

משפט (החלטה אם לבצע פעם אחת)

משפט-1

משפט-2

  .

  .

  .

משפט-n (החלטה אם לבצע שוב)

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

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

משפט-1

משפט-2

  .

  .

  .

משפט-k (החלטה אם לבצע שוב)

  .

  .

  .

משפט-n

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

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

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

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

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

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

כיצד משתמשים ברקורסיה?

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

 

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

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

(2)    ניתן לפתור בקלות את המקרים הפשוטים ביותר של הבעיה.

 

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

נדגים את העיקרון הנ"ל עבור מספר בעיות תכנותיות [המאמר המקורי מביא 7 בעיות, וכולל גם את המימוש בפסקל; בתקציר זה הסתפקנו ב-3 בעיות וויתרנו על המימוש – ד"ל].

דוגמה 1: המספר הגדול ביותר

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

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

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

דוגמה 2: הדפסת מערך מהסוף להתחלה

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

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

(2)               במקרה הפשוט שבו יש רק ערך אחד, קל מאד להדפיס אותו ישירות. 

דוגמה 3: מיון בחירה

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

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

(2)                 במקרה הפשוט שבו יש רק מספר אחד, המערך כבר ממוין.

 

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

לחזור או לא לחזור – זו השאלה

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

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

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

סיכום

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

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

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

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

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

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

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