רקורסיה מדעי המחשב לכיתה י״א
בנושא הזה 6 שיעורים. כך הם מתחילים:
הגדרה רקורסיבית, תנאי עצירה וקריאה רקורסיבית
רקורסיה היא פתרון בעיה בעזרת פתרון של אותה בעיה בגרסה קטנה יותר. לפעולה רקורסיבית יש תנאי עצירה (המקרה הפשוט שנפתר ישירות) וקריאה רקורסיבית שמתקרבת אליו. כל קריאה מחכה לתשובה של הקריאה שאחריה - מחסנית הקריאות.
מעקב אחר רקורסיה: f(n) ו-f(n-1)
מעקב אחר רקורסיה נעשה ברמה של f(n) ו-f(n−1): רושמים כל קריאה עם הפרמטרים שלה, מה היא מחכה לו, ומה היא מחזירה. כשהדפסה נמצאת לפני הקריאה הרקורסיבית היא מתבצעת "בדרך הלוך"; כשהיא אחרי - "בדרך חזרה", ולכן בסדר הפוך. אחרי המעקב שואלים: מה הפעולה מחשבת באופן כללי?
סוגי רקורסיה: זנב, הלוך-חזור, כפולה והדדית
תכנית הלימודים מבחינה בין ארבעה סוגי רקורסיה: רקורסיית זנב (הקריאה הרקורסיבית היא הדבר האחרון שנעשה, ואין עבודה בדרך חזרה), רקורסיית הלוך-חזור (יש עבודה אחרי שהקריאה חוזרת), רקורסיה כפולה (שתי קריאות רקורסיביות בכל הפעלה, כמו פיבונאצ׳י) ורקורסיה הדדית (שתי…
רקורסיה על מספרים וספרות
רקורסיה על מספרים שלמים בנויה על אותם כלים כמו לולאת ספרות: n % 10 היא ספרת האחדות, ו-n / 10 הוא המספר בלעדיה. תנאי העצירה הוא בדרך כלל "נשארה ספרה אחת" (n < 10).
רקורסיה על מערכים: פרמטר מציין
רקורסיה על מערך משתמשת בפרמטר מציין (i): כל קריאה מטפלת בתא arr[i] ומעבירה את "שאר המערך" לקריאה עם i + 1. המערך עובר בלי שינוי בין הקריאות; רק המציין משתנה.
יתרונות וחסרונות, ומעבר בין רקורסיה ללולאה + חזרה
יתרונות הרקורסיה: פתרון פשוט וקצר שדומה להגדרה, וקל להוכיח את נכונותו. חסרונות: כל קריאה תופסת מקום במחסנית ולוקחת זמן, ורקורסיה כפולה עלולה לחשב אותו דבר שוב ושוב.
שאלה לדוגמה
מה מחזירה fact(4)?
- 10
- 16
- 24
- 4
לתשובה
24 - 4 · 3 · 2 · 1 · 1 = 24. fact(0) = 1 הוא תנאי העצירה.
→ יחידה 3: מטלת הביצוע (899373)מבוא ליעילות ←
לומדים את כל זה במרחב הלמידה, בחינם
שיעורים מונפשים ותרגול לפי תוכנית משרד החינוך. הילד עושה משהו בכל מסך ומקבל הסבר על כל טעות, וההורה מקבל דוח שבועי. ממלכתי וממלכתי-דתי.