ממואיזציה ללא רקורסיה
שיעור 5 מתוך 15 בקורס תכנות דינמי 101 של Coddy.
בשיעור הקודם למדנו על שמירת תוצאות (memoization) ועל האופן שבו היא יכולה לעזור לשפר את סיבוכיות הזמן של הפתרונות הרקורסיביים שלנו. בשיעור הזה נבחן איך להשתמש ברקורסיה עם שמירת תוצאות כדי לפתור בעיות ביעילות רבה יותר.
רקורסיה היא טכניקה בתכנות שבה פונקציה קוראת לעצמה כדי לפתור בעיה. פתרונות רקורסיביים יכולים להיות אלגנטיים ואינטואיטיביים מאוד, אך הם יכולים גם להיות לא יעילים, במיוחד אם קוראים לאותה פונקציה כמה פעמים עם אותם ארגומנטים. כאן נכנסת לתמונה שמירת תוצאות. על ידי שמירת התוצאות של קריאות קודמות לפונקציה, אפשר להימנע מחישובים מיותרים ולשפר משמעותית את הביצועים של הפתרונות הרקורסיביים שלנו.
אתגר
קלנניח שאפשר לעלות בכל פעם צעד אחד או שני צעדים.
כתבו פונקציה בשם count_ways שמקבלת מספר שלם n ומחזירה את מספר הדרכים לעלות בגרם מדרגות בן n צעדים.
יש לבצע ממוּניזציה לפונקציה כדי להימנע מחישובים חוזרים.
הימנעו משימוש ברקורסיה באתגר הזה!
נסו בעצמכם
def count_ways(n):
# TODO: כתבו את הקוד שלכם כאןכל השיעורים ביחידה תכנות דינמי 101
תרגלו בעצמכם: קומפיילר Python אונליין