שיעור 15: רקורסיה, backtracking ומבוא DP

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

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

רקורסיה ו-backtracking: רקורסיה: פונקציה שקוראת לעצמה על תת-בעיה קטנה יותר עד מקרה בסיס. Backtracking: מנסים בחירה, יורדים ברקורסיה, ומבטלים את הבחירה כדי לסרוק את כל האפשרויות.
מקרה בסיס: התנאי שעוצר את הרקורסיה ומחזיר תשובה ישירה בלי קריאה נוספת — בלעדיו הרקורסיה לא תיגמר.
memoization (זיכרון תוצאות): שמירת תוצאות של תת-בעיות ב-cache (למשל dict) כדי לא לחשב אותן שוב — חוסך חישובים חוזרים ויכול להאיץ מאוד את הריצה (למשל Fibonacci נאיבי מ-O(2ⁿ) ל-O(n)).