8. רקורסיה

הקדמה

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

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

8.1 דוגמות ראשונות

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

8.1.1 חישוב !n

הסבר כתוב אודות חישוב !n

8.1.2 חישוב סכום של שני מספרים טבעיים

הסבר כתוב אודות חישוב סכום של שני מספרים טבעיים

8.1.3 חישוב החזקה של שני מספרים טבעיים

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

תרגול עצמי בסיסי בנושא תכניות רקורסיביות פשוטות

כתבו תכנית הכוללת את הפונ': unsigned int my_div( unsigned int divided, unsigned int divider) על הפונ' לחשב את המנה הטבעית: divided/divider תוך שימוש בפעולות חיבור וחיסור בלבד (בלי להשתמש בפעולות אריתמטיות אחרות). הפונ' גם לא תעשה שימוש בשום פקודות לולאה שהיא, כלומר עליה להיות רקורסיבית.. לדוגמה: עבור 8/10 תוחזר המנה 0, ועבור 38/10 תוחזר המנה 3.

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

8.1.4 תרגום מספר טבעי מבסיס 10 לבסיס 2

הסבר כתוב אודות תרגום מספר מבסיס 10 לבסיס 2

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

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

8.1.5 קריאת סדרת מספרים באורך לא ידוע, והדפסתם בסדר הפוך

דוגמה זאת מוצגת רק באמצעות טקסט כתוב (ללא סרטון)

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

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

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

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

הנחיה: הפונ' תקבל את המערך, את הערך המבוקש, ואת התא בו הקריאה הנוכחית בודקת האם הערך המבוקש מצוי (בקריאה הראשונה לפונ' מהתכנית הראשית יועבר התא מספר אפס). אם הערך המבוקש מצוי בתא 'הנוכחי' אזי הקריאה הרקורסיבית הנוכחית תחזיר את הערך true. אם התא הנוכחי הוא האחרון במערך (והערך לא נמצא) אזי הקריאה הרקורסיבית הנוכחית תחזיר את הערך false. בכל מקרה אחר: הקריאה הרקורסיבית הנוכחית תזמן קריאה רקורסיבית עם מספרו של התא הבא במערך; והקריאה הנוכחית תחזיר את הערך שהחזירה לה הקריאה המזומנת.

8.1.6 הצגת האיבר ה- n –י בסדרת פיבונאצ'י

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

הסבר כתוב אודות הצגת האיבר ה: n-י בסדרת פיבונאצ'י

8.2 מיון מהיר

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

נתחיל בהצגת רעיון האלג'.

הסבר כתוב אודות רעיון האלגוריתם: מיון מהיר

הקוד של מיון מהיר

נציג עתה את קוד הפונ' שמממשת את המיון

הקוד של מיון מהיר (ושל פונ' החלוקה בה מיון מהיר נעזר)

סימולציית הרצה של ציון מהיר

זמן הריצה של מיון מהיר

נדון בזמן הריצה של מיון מהיר במקרה הטוב ביותר, ובמקרה הגרוע ביותר

הסבר כתוב אודות זמן הריצה של מיון מהיר

8.3 מגדלי האנוי (Towers of Hanoi)

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

8.3.1 + 8.3.2 תיאור הבעיה והאלגוריתם לפתרונה

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

8.3.1הסבר כתוב אודות תיאור הבעיה והאלגוריתם לפתרונה

8.3.3 הקוד של מגדלי האנוי, וסימולצית הרצה של התכנית

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

8.3.4 זמן הריצה של האלגוריתם

הסבר כתוב אודות זמן הריצה של מגדלי האנוי

תרגול עצמי בסיסי(?) בנושא מגדלי האנוי

חשבו איזה טבעת תועבר בצעד המאה, ומאיזה עמוד לאיזה עמוד, עת יש להעביר מגדל בן 7 שעות מעמוד a לעמוד c (תוך שימוש בעמוד b כעמוד העזר)

8.4. בעיית שמונה המלכות (כדוגמה לבעיית backtracking)

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

על backtracking באופן כללי, הצגת בעיית שמונה המלכות, ורעיון האלגוריתם

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

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

8.4.1 בעיית שמונה המלכות: קידוד וסימולציית הרצה

הסבר כתוב אודות: בעיית שמונה המלכות: קידוד וסימולציית הרצה

8.4.2 בעיית שמונה המלכות: הפונ' consistent

8.4.3 בעיית שמונה המלכות: הצגת פתרון יחיד

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

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

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

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

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

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

8.4.4 בעיית שמונה המלכות: הערכת זמן הריצה של האלגוריתם

הסבר כתוב אודות הערכת זמן הריצה של בעיית שמונה המלכות

8.5 בעיית היציאה ממבוך (כדוגמה נוספת לבעיית backtracking)

בעית היציאה ממבוך: הצגת הבעיה ורעיון הפתרון

(בונוס: תזכורת על טיפוסי enum)

הסבר כתוב אודות הצגת בעית היציאה ממבוך ורעיון הפתרון

בעית היציאה ממבוך: קוד התכנית וסימולציית הרצה

הסבר כתוב אדות: בעית היציאה ממבוך: קוד התכנית וסימולציית הרצה

8.6 הערה בעניין כשלים בסגנון התכנותי בכתיבת פונקציות רקורסיביות

8.7 תרגילים

מאוד! מאוד!! מאוד!!! חשוב לתרגל

8.8 בחן את עצמך

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

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