למידה והוראה של רקורסיה

הכנה ועריכה: ד"ר דלית לוי

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

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

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

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

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

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

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

רקורסיה: מבט רב תחומי

רקורסיה מופיעה בתכניות הלימודים בדרך כלל בקורסים העוסקים ביסודות התכנות, לאחר לימוד כלים תכנותיים בסיסיים כמו משתנה, פרוצדורה ולולאה ולאחר הכרות עם מבני הנתונים הבסיסיים. המרכזיות של המושג רקורסיה במדעי-המחשב נובעת ממספר גורמים, וביניהם האפשרות לתת פתרון לבעיות אלגוריתמיות מסוימות, היכולת לבטא ולייצג מבני נתונים מורכבים, והכוח לתאר בפשטות תהליכים חישוביים מסובכים. בנוסף לגורמים הדיסציפלינריים, תורמים גם גורמים אינטרדיסציפלינריים להיות הרקורסיה מושג מפתח. מוסיף לכך המסתורין המיוחס למושג ואשר בא לידי ביטוי באמירות כמו "אלגוריתם מיון מיזוג הוא דוגמה טובה לעוצמה הכמעט-מסתורית ולאלגנטיות של רקורסיה" (היליס, 2000, עמ'  76) וכן "פלאיה של הרקורסיה במתמטיקה הם רבים מספור" (Hofstadter, 1979, p. 138).

בתוך הדיסציפלינה של מדעי-המחשב, המושג רקורסיה מבטא בדרך כלל את הרעיון של התייחסות עצמית ואת אפשרויות יישום הרעיון לאלגוריתמים ולתכניות מחשב (Harvey & Wright, 1994). ההגדרות המופיעות בספרי לימוד של מדעי-המחשב מתייחסות לרקורסיה כאל כלי תכנותי, או טכניקה תכנותית, כמו בהגדרה הבאה - "רקורסיה היא טכניקה שבה פונקציה או פרוצדורה קוראת לעצמה, ואלגוריתם רקורסיבי הוא כזה שבו תהליך מתייחס לעצמו" (Garland, 1987, p.321). אלגוריתם רקורסיבי מוגדר כ"אלגוריתם שאחד (או יותר) ממשימותיו הוא הפעלה חוזרת של אותו אלגוריתם על קלט פשוט יותר" (בן-ארי וחוב', 1998, עמ' 193). הגדרות אלה מבטאות את תיאור הפן התהליכי של מושג הרקורסיה. אולם חשיבותו של המושג "רקורסיה" במדעי-המחשב חורגת מההתייחסות לרקורסיה כאל טכניקה לכתיבת אלגוריתמים, והיא נוגעת במידה רבה גם למבנה העצמים המשמשים כנתונים לאלגוריתמים. ההתייחסות הכללית והמופשטת יותר למושג "רקורסיה" מתמקדת בתיאור המאפיינים של הגדרה רקורסיבית שעשויה להיות מיושמת הן על מבנים והן על תהליכים. כותב על כך היליס: "(ה)שיטה להגדרה רקורסיבית של דברים, מתברר, היא רבת עוצמה. רבים מסוגי הנתונים שאנו עושים בהם מניפולציות – וביחוד תכניות המחשב עצמן – הם בעלי מבנה רקורסיבי. ההגדרות הרקורסיביות נוחות מאין כמוהן לתיאור פעולות שיש לבצע בנתונים רקורסיביים" (היליס, 2000, עמ' 52).

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

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

 

א. הגדרה רקורסיבית של אלגוריתם מתמטי לביצוע פעולת האיחוד (ע"פ Gersting, 1996)

A1    A2      A1Ú A2

0      0        0

0      1        1

1      0        1

1      1        1          

 

1. A1 Ú A2 defined by the truth table    מקרה בסיסי פשוט ביותר                          

2. A1 Ú …. Ú An = (A1 Ú …. Ú An-1 ) Ú An for n > 2     קריאה רקורסיבית   

 

ב. הגדרה רקורסיבית של אלגוריתם לביצוע פעולת כפל בשפת התכנות Pascal (ע"פ Gersting, 1996)

 

function Product(m, n:integer): integer;

{recursively computes the product of m and n}

begin

   if n = 1 then

       Product := m     מקרה בסיסי פשוט ביותר

   else

       Product := Product (m, n - 1) + m;    קריאה רקורסיבית

end; 

 

 

ג. הגדרה רקורסיבית של אלגוריתם לסיכום אברי רשימה בשפת התכנות DrScheme (ע"פ לפידות, לוי ופז, 2001)

 (define  (sum-all  L)

(cond

                      [ ( empty?  L )   0  ]    מקרה בסיסי פשוט ביותר

                      [ else  ( +  ( first  L )  ( sum-all  (rest  L ) )  ] ) )   קריאה רקורסיבית

 

 

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

 

א.       הגדרה רקורסיבית של מבנה הנתונים "מזהה" בשפת תכנות (BNF)   (ע"פ Gersting, 1996)

 

<identifier> ::= <letter>|<identifier><letter>|<identifier><digit>   קריאה רקורסיבית

<letter> ::= a|b|c|…|z

<digit> ::= 0|1|…|9   מקרים בסיסיים פשוטים ביותר

 

 

ב. הגדרה רקורסיבית של מבנה הנתונים "עץ בעל שרשרת X" (ע"פ ברנדס וחוב', 1997)

 

       (1) עץ בעל שרשרת X במקרה הפשוט הוא עץ בינרי ריק      (מקרה בסיסי פשוט ביותר)

      (2) עץ בעל שרשרת X

      הוא עץ בינרי שתוכן השורש שלו הוא X

      ולפחות אחד מהתת עצים של הוא עץ בעל שרשרת X   (קריאה רקורסיבית)

 

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

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

Godel, Escher, Bach – An Eternal Golden Braid (Hofstadter, 1979)

 

 

 

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

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

 

תרשים 1: דגמים שונים של פרקטלים[1]

 

 

 

 

 

 

 

 

 


תרשים 2: שלבים ביצירת פתית השלג של קוך

 

 

 

 

 

 

 


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

למידת רקורסיה

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

אחת הסיבות לקשיים בהבנת רקורסיה מתוארת על-ידי לירון (1996). לירון טוען כי הן הכוח והן המורכבות של המושג רקורסיה נובעים שניהם מאותו מקור: יכולתה להפיק תיאורים פשוטים מאד לתופעות מורכבות מאד. ההסבר שהוא מציע לקושי עושה שימוש במונחי 'השלישיה החישובית' – התכנית שמפעילה את התהליך, שבסופו של דבר מפיק את התוצר[2]. במונחים אלה, הקושי המהותי בהבנת רקורסיה נובע מפער המורכבות בין תכניות והליכים רקורסיביים לבין התהליכים הנוצרים על ידם. התכנית הרקורסיבית היא בדרך כלל קצרה ופשוטה למראה, אולם היא יוצרת תהליך מורכב עד מאד, כמו למשל תהליכים רקורסיביים שפותרים את בעיית מגדלי הנוי או מסרטטים את הפרקטלים שתוארו בסעיף הקודם. התכנית הרקורסיבית הפשוטה למראה היא ייצוג סטטי (טקסטואלי) של התהליך, בעוד התהליך הוא הייצוג הדינמי של התכנית. הפער שבין הפשטות של הייצוג הסטטי לבין המורכבות של הייצוג הדינמי במקרה של רקורסיה, הוא אחת הסיבות לקשיים בהם נתקלים הלומדים. מזיהויו של פער זה נובע גם הפתרון: הואיל והמורכבות מסתתרת בעיקר בתהליך, ממליץ לירון (שם) להדחיק את החשיבה עליו. על השאלה "מה ההליך עושה?" יש לענות במונחים של התוצר, לא התהליך. במילים אחרות, עלינו לראות את התכנית כתיאור של התוצר, לא של התהליך.

ג'ורג' מתייחס אף הוא לפער שבין הייצוג הסטטי לבין הייצוג הדינמי (George, 2000a). לומדים רבים מפתחים, לטענתו, באופן טבעי מודל הפעלה טקסטואלי-סטטי שבו הפרוצדורות נתפסות כקטעים סטטיים של קוד התכנית, ואינם מסוגלים לפיכך לראות בעיני רוחם את התהליכים הדינמיים השונים המייצגים באופן לוגי את ביצוע הפרוצדורות. קושי מיוחד מתעורר אצל לומדים בנוגע להבנת התפקיד של השהיית החישוב (suspended computation), השהייה המהווה מרכיב מרכזי של כל אלגוריתם רקורסיבי (Bhuiyan, Greer & McCalla, 1994). קשיים אלה בהבנת רקורסיה הם חלק מבעייה כללית יותר של בניית מודל מנטלי אפקטיבי של הפעלת תת-תכניות. בספרות מופיעים פתרונות שונים לבעייה זו, כולל שימוש במודלים ויזואליים של רקורסיה (ראה המודל שמציע היינסHaynes, 1995) ) במאמרו המופיע בהמשך, מודל האנשים הקטנים (לוי 1991 Harvey, 1985;), מודל top-down המכונה גם מודל המסגרות (Harvey, 1985) והמודל הלוגי-דינמי אצל ג'ורג' (George, 2000a) ).

מרבית המחקרים שהתייחסו לקשיים של תלמידים התבצעו במסגרת תכנותית, דהיינו בהקשר של הבנת אלגוריתמים רקורסיביים הרשומים בניסוח פורמלי בשפת תכנות. באחד המקורות הראשונים שחקר קשיים של תלמידים בהבנת רקורסיה, נטען כי הקושי מתעורר בשל הצגת רקורסיה לאחר שתורגל השימוש במבני לולאה רגילים (Kurland & Pea, 1983). יש הטוענים כי הקשיים המדווחים בהוראת הנושא נובעים מהשילוב של רקורסיה בתכנות פרוצדורלי (אימפרטיבי), ומוסיפים כי לא מדווחים קשיים דומים בלמידת רקורסיה בהקשר של תכנות פונקציונלי (Valazquez-Iturbide, 2000). מקורות אחרים מציינים כי דווקא השילוב בין המושג המופשט "רקורסיה" למושג המופשט "פונקציה" הוא אחד ממקורות הקושי העיקריים (Troy & Early, 1992) . ואולם, למעט מחקריהן של חדשי (1996) ושל לוי (2001) שעוסקים בהוראה ולמידה בין-תחומית של רקורסיה, לא מדווח על מחקרים שנעשו בהקשר לא-תכנותי, ואשר בחנו עניינים הנוגעים להיבטים רחבים יותר של מושג הרקורסיה, כמו יכולת ראייה רקורסיבית, מיומנויות ניסוח רקורסיבי שהוא לאו דווקא ניסוח פורמלי, ושימוש ברקורסיה לפתרון בעיות לא אלגוריתמיות. זאת ועוד, אפילו המסגרת התכנותית אינה עוסקת במגוון ההיבטים התכנותיים של רקורסיה. כך למשל, ממחקרו של אהרוני  (1999) עולה כי אפילו סטודנטים למדעי-המחשב באוניברסיטה המגלים הבנה של המושג תהליך רקורסיבי, אינם מגלים הבנה הקשורה להיבטים אחרים של רקורסיה כמו למשל הבנה של המושג מבנה רקורסיבי. במלים אחרות, המסגרת התכנותית שבה מוצג בדרך כלל מושג הרקורסיה מתמקדת בעיקר בהיבטים תהליכיים. לפיכך היא לא תורמת להבנת היבטים תכנותיים אחרים של רקורסיה ובוודאי לא תורמת להבנת היבטים שאינם תכנותיים.  

עד כה הוצגו שלושה הגורמים המרכזיים המתוארים בספרות המחקרית, אשר תורמים לקשיים של לומדים במהלך לימוד רקורסיה במדעי-המחשב. הגורם הראשון קשור בפער המורכבות בין ההליך הרקורסיבי לתהליך הרקורסיבי; הגורם השני קשור בבניית מודלים מנטליים לא אפקטיביים המייצגים את תהליך הפעלתם של הליכים רקורסיביים; והגורם השלישי קשור בהצגת רקורסיה במסגרת תכנותית צרה. לגורמי קושי אלה ניתן להוסיף גם את הדרכים בהן מקובל להציג את מושג הרקורסיה הן בספרי הלימוד של מדעי-המחשב והן בשיטות ההוראה המסורתיות. בן-ארי ורייך (1996) מסבירים כי שתי הגישות המקובלות להצגת רקורסיה הן שימוש בעצמים מהעולם האמיתי כאנלוגיה (כמו בובות רוסיות או משחקים), ושימוש בדיאגרמות שמאפשרות לתלמיד לעקוב אחר ביצוע ההפעלות הרקורסיביות (כמו מחסנית). אלא שלטענתו, שתי הגישות לוקות בחסר ואינן מאפשרות התמודדות ממשית עם הקשיים של הלומדים, ובמיוחד עם קשייהם של לומדים מתחילים. זאת ועוד, גם כאשר משתמשים כאנלוגיה בדוגמאות מחיי היומיום, שימוש זה אינו רחב היקף ואינו מגוון דיו (צצקיס, 1985; לוי, 1991). בפרקים הבאים של סקר הספרות יובאו מאמרים העוסקים בעיקר בגורם השני לקושי, דהיינו במודלים מוצעים להסבר רקורסיה (המאמר של Haynes, 1994) ובקשר בין סוג המודלים לסגנון הקוגניטיבי של הלומדים (המאמר השלישי של Wu, Dale & Bethel 1998).

הוראת רקורסיה

בעקבות זיהוי הקשיים המלווים את תהליך הלמידה וההוראה של רקורסיה, מציעה הספרות החינוכית דרכי הוראה והמלצות למורים למדעי-המחשב המבקשים לשלב מושג זה במהלך הוראתם (Anderson, Pirolli & Farrel, 1988; (Harvey, 1985. חלק מההמלצות מופיעות גם במאמרים שיסקרו בהמשך, אולם הרשימה להלן כללית ומקיפה יותר ומבוססת גם על מקורות נוספים.

1.        מאחר והמורכבות העיקרית מסתתרת בתהליך הרקורסיבי, מומלץ ל'הדחיק את החשיבה על התהליך ולראות את ההליך הרקורסיבי כתיאור של התוצר ולא של התהליך (Leron , 1988).

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

(George, 2000-b; Bhuiyan, Greer & McCalla, 1994) .

3.        מומלץ להמחיז את התהליך הרקורסיבי על ידי הלומדים עצמם, באמצעות מודל האנשים הקטנים Harvey, 1985); לוי, 1991). גם בן-ארי משתמש ברעיון ההמחזה, וממליץ על צירוף בעיה מהעולם האמיתי שניתן להמחיזה, לבעיה תכנותית שפתרונה מקביל בדיוק להמחזה. ההמחזה משלבת לטענת בן-ארי הנאה מהלימוד יחד עם ויזואליזציה דינמית של התהליך הרקורסיבי (Ben-Ari, 1997).

4.        למעט ההמלצה הראשונה, ההמלצות שמובאות לעיל ממוקדות בהבנת התהליך הרקורסיבי. ואולם כדי להרחיב ולהעמיק את הבנת המושג "רקורסיה", מומלץ לעסוק גם בהיבטים נוספים שלו. בין השאר מופיעות בספרות המלצות לעסוק במהלך הלימוד במבני-נתונים רקורסיביים ובמבנים רקורסיביים מורכבים כמו פרקטלים (אהרוני, 1999), והמלצות להשתמש במספר שיטות שונות לבניית אלגוריתמים רקורסיביים ולניתוחם (Harvey & Wright, 1994).

5.        מומלץ להתחיל את לימוד המושג "רקורסיה" עם בעייה מתאימה. נהוג הוא להתחיל את לימוד הרקורסיה עם תכנית לחישוב עצרת, או לחישוב מספרי פיבונצ'י. שתי אלה בעיות מתמטיות, לראשונה יש גם פתרון איטרטיבי טריוויאלי והשנייה מממשת רקורסיה דו-ממדית ולכן קשה מדי עבור מתחילים (Ben-Ari, 1997). גם בעיית מגדלי הנוי המפורסמת מחייבת שימוש בשתי קריאות רקורסיביות. לצורך הקלה על קשיי הלומדים, במיוחד המתחילים שבהם, מומלץ לבחור כבעיה ראשונה בעיה עם רקורסיה ליניארית, ואשר אין עבורה פתרון איטרטיבי פשוט.

6.        רצוי לפתח אצל הלומדים מיומנויות כלליות של ראייה רקורסיבית וחשיבה רקורסיבית (Roberts, 1986), תוך שימוש במגוון רחב של  תופעות רקורסיביות מתחומי חיים שונים (חדשי, 1996; לוי, 1991; צצקיס, 1985).

חלק מההמלצות משתלבות במגמה כללית המאפיינת כיום את השינויים החלים בדרכי הוראת מושגים מתמטיים ומדעיים, ואשר מושפעים בין השאר מתפיסת עולם קונסטרוקטיביסטית של הלמידה, על פיה הלומד בונה את הידע שלו באופן פעיל, תוך כדי חתירה לתת משמעות להתנסויותיו האישיות. ההמלצות הללו היוו בסיס רעיוני לפיתוח חלק מחומרי הלימוד במדעי-המחשב במסגרת תכנית הלימודים החדשה לחטיבה העליונה בישראל, וניתן לראות להן ביטוי מפורש בחומרי הלימוד בהם משתמשים התלמידים ובגישות ההוראה בהם משתמשים המורים למדעי-המחשב. המושג רקורסיה נדון בתכנית הלימודים התיכונית בדגשים שונים וברמות קושי שונות, הן ביחידת הלימוד השניה "יסודות מדעי המחשב – 2" (בן-ארי וחוב', 1998), הן בחלופות של יחידת הלימוד השלישית "תכנות פונקציונלי" (לפידות, לוי ופז, 1999)  ו"תכנות לוגי" (שרץ, הברמן, בן-זקן וגלוברמן, 1996) והן ביחידת הלימוד הרביעית "עיצוב תכנה" (ברנדס וחוב', 1997).

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

 

תרשים 3: דרכים שונות לתיאור פונקציה רקורסיבית (ע"פ לפידות, לוי ופז 2001)

 

הפונקציהfact  מקבלת מספר n ומחזירה את העצרת שלו. לדוגמה:   (fact  3)   Þ   1 * 2 * 3 = 6

הגדרת הפונקציה 

 

      תאור מילולי של הפונקציה  עצרת   n!

 

(define  (fact  n)

 (cond

     [( =  n  0 )   1]

     [else   ( * n   (fact  (sub1  n )))] ))

 

 

הערך של עצרת  עבור מספר טבעי כלשהו n   הוא:

אם n   שווה ל – 0   הערך הוא  1 .

אחרת: הערך הוא המכפלה של  n 

                           בערך של עצרת עבור n - 1  .

 

 

 

מודל המסגרות  (Top-Down)

 

מודל ההצבה

 

 

( fact   4 ) =

( *   4   ( fact  3 )  ) =

( *   4    ( *  3  ( fact   2 )  )  ) =

( *   4    ( *  3  ( *   2    ( fact   1 )  ) ) ) =

( *   4    ( *  3  ( *   2    ( *  1  ( fact   0) ) ) ) ) =

( *   4    ( *  3  ( *   2    ( *    1    1 ) ) ) ) =

( *   4    ( *  3  ( *   2   1 )  )  ) =

( *   4    ( *  3    2   )  ) =

( *   4    6  ) =

24

 

 

 

על המאמרים שנבחרו לסקירה

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

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

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

במודלים כאלה, ובבחינת הקשר שביניהם לבין הסגנון הקוגניטיבי של התלמידים הנחשפים אליהם, עוסק גם המאמר השלישי – מודלים וסגנונות קוגניטיביים בהוראת רקורסיה (Wu, Dale & Bethel, 1998). חלק מהמודלים המוצגים במאמר זה מהווים חזרה על הגישות שהוצגו במאמר הקודם, אולם ההתמקדות כאן היא בשאלה עד כמה השימוש בסוג מוחשי או מופשט של מודלים קונספטואליים להסבר רקורסיה עשוי לעזור לתלמידים בעלי סגנון קוגניטיבי מוחשי או מופשט. מודלים מוחשיים, נטען במאמר, עוזרים יותר למתכנתים מתחילים.

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

המאמר החמישי והאחרון מביא אף הוא את הפן של הלומדים. המאמר כיצד לומדי תכנות פונקציונלי מפרשים פונקציות רקורסיביות (Segal, 1995) עוסק בלומדים הנדרשים לפענח פונקציות רקורסיביות. בעקבות סידרת מחקרים אמפיריים שהתבססו על תצפיות ועל ראיונות עם לומדים, זוהו שני קשיים עיקריים: הראשון קשור בתפיסה מוטעית של הלומדים אודות תהליכים רקורסיביים, והשני נובע מערבוב שהם עושים בין ההקשר המתמטי של המושג "משתנים" לבין ההקשר התכנותי שלו. במאמר נידונות האסטרטגיות שהלומדים מפעילים כדי להבין פונקציות רקורסיביות, והוא ממליץ על אסטרטגיה עדיפה – אסטרטגיה של "חישוב מושהה" (delayed evaluation). בחלקו הראשון של המאמר נסקרים בהרחבה היבטים שונים של רקורסיה, ומתוארים מספר מחקרים קודמים שעסקו בנושא. בכך מהווה מאמר זה גם סיכום לקובץ המאמרים כולו.

רשימת מקורות למבוא

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

אתר הבטים

גליון ינואר 2002

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

 



[1]  מקורות העוסקים בפרקטלים מצויים בשפע באינטרנט. למשל, באתר   http://home.att.net/~Novak.S/  .

[2]  באנגלית מכנה לירון מונחים אלהThe three P’s of computation – Procedure, Process and Product   .