רקורסיה חלק ו’ – הטעות של יונתן

הפוסט הקודם בסדרה – רקורסיה חלק ה’ – חיפוש קובץ במערכת קבצים

אני מאמינה שרובכן ראיתן את סרטון המאסטר שף של מייקרוסופט ששטף את הרשתות החברתיות בשבוע שעבר.

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

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

public static int Fib(int n1)
	if (n1 <= 2) 
	{
		return 1;
	}
	else
	{
		return Fib(n1 - 1) + Fib(n1 -2 )
	}

למה הקוד הזה גרוע כל כך?

הדוגמא של סדרת פיבונאצ’י היא דוגמא מפורסמת לקוד רקורסיבי, מכיוון שההגדרה של סדרת פיבונאצ’י היא הגדרה רקורסיבית. המספר ה-n בסדרת פיבונאצ’י הוא סכום שני המספרים הקודמים בסדרה.

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

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

רציתי לבדוק מתי בדיוק זה יקרה, אז הרצתי את הקוד ובדקתי. החישוב של Fib(30) במחשב שלי לקח פחות משנייה, החישוב של Fib(40) לקח 22 שניות. החישוב של Fib(60) כבר לא חזר.

העליתי את הקוד, ואתן יכולות לבדוק אותו גם במחשב שלכן.

אז למה זה קורה?

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

אנחנו רואות ש-fib(5) קורא ל-fib(4) ו-fib(3).

לאחר מכן fib(4) גם הוא קורא ל-fib(3) כך שהחישוב של fib(3) מחושב פעמייים בצורה זהה.

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

איך אפשר לעשות את הקוד פחות גרוע?

יש שלוש דרכים טובות יותר למצוא את האיבר ה-n בסדרת פיבונאצ’י.

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

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

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

אני אוסיף cache כזה לקוד המקורי – 

def memoized_fib(n):
    results_cache = {}

    def fib(num):
        if num in results_cache:
            return results_cache[num]
        else:
            if num <= 2:
                res = 1
            else:
                res = fib(num - 1) + fib(num - 2)

            results_cache[num] = res
            return res

    return fib(n)

הקוד החדש נראה דומה לקוד הקודם. הוא עדיין קורא שוב ושוב לחישובים שכבר בוצעו, אבל בזכות השימוש ב-cache אנחנו מורידות מהעץ את כל החישובים הכפולים, ונשארות עם כמות עבודה לינארית.
כעת החישובים רצים הרבה יותר מהר – Fib(500) לוקח פחות משנייה.

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

בבעיה הזו נטפל בפוסט הבא.

פוסטים נוספים בסדרת הרקורסיות