מה מתכנתים 'טירונים' יודעים אודות רקורסיה?

ה. קהני

Kahney, H. (1989). What do novice programmers know about recursion? Soloway, E. & Sphorer, J.C. (eds), Studying the novice programmer, LEA publishers. 209-228.

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

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

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

 

אודות המאמר

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

 

רשימת מושגים

w מודלים אישיים - Idiosyncratic models                

w מודל ההעתקים – Copies model                         

w מודל הלולאה –  Loop model                                               

w מתכנת טירון – Novice programmer   

w מתכנת מומחה – Expert programmer

 

הקדמה

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

 

 

 

 

 

 

 

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

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

2.        קיים חלק ביצועי.

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

 

כיצד 'תתנהג' תכנית רקורסיבית בהתאם למודלים השונים

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

הבעייה שהוצגה בפני המתכנתים היתה:

"יש לכתוב תכנית שתבנה בסיס נתונים מתאים לתנאים הבאים: אם ל – X יש שפעת, אז כל מי ש- X מנשק אותו נעשה אף הוא חולה בשפעת, וכל מי שנדבק מפיץ את השפעת לאדם שהוא או היא מנשקים, וכך הלאה."

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

הדבקה1  (X)                                                                                  

1.   האם  (X)  מנשק (מישהו)                                                           

      1.1 אם כן,  (מישהו) à  “שפעת"                                  

      1.2 אם לא, עצור                                                           

הדבקה2  (X)  

1.       (X)  à  “שפעת"

2.       האם  (X)  מנשק (מישהו)

     2.1 אם כן, הדבקה2  (מישהו)

     2.2 אם לא, עצור

הדבקה3  (X)

1.  האם (X) מנשק (מישהו)

    1.1   אם כן, הדבקה3  (מישהו)

    1.2   אם לא, המשך

2.  (X)  à  “שפעת"

 

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

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

זהו תהליך ההיסק המשוער עבור התכנית הדבקה3, תוך שימוש במודל ההעתקים:

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

 

הרצת הדבקה3 באמצעות מודל הלולאה

 

הרצת הדבקה2 באמצעות מודל הלולאה

 

 

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

 

ממצאי המחקר

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

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

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

 

זו תגובתו של אותו מומחה לפתרון השלישי:

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

 

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

מומחים

טירונים

התגובה

1

16

רק ההליך הדבקה2 מתאים

8

3

שני ההליכים הדבקה2 ו- הדבקה3 מתאימים

0

11

תשובה אחרת

 

דיון בממצאים

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

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

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

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

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

 

מסקנות

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

 

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

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

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