קוד פייתון הבא מחשב מספר n בסידרת פיבונאצ'י בדרך מאוד לא יעילה:

def fib(n):
    if n <= 1:
        return 1

    return fib(n-1) + fib(n-2)

הבעיה איתו היא שהוא מחשב את ערכי הביניים יותר מדי פעמים. בניסיון לחשב את fib(10) הוא יחשב את הסכום fib(9)+fib(8), ואז בשביל לחשב את fib(9) הוא שוב יחשב את fib(8). אפשר להיווכח בזה בקלות אם מוסיפים שורת הדפסה בתחילת הפונקציה. הקוד יהיה:

def fib(n):
    print(f"fib({n})")
    if n <= 1:
        return 1

    return fib(n-1) + fib(n-2)

והפלט הוא:

fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(2)
fib(1)
fib(0)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
8

דרך קלה לתקן את זה היא להשתמש בדקורטור הבנוי בשפה lru_cache. אבל בשביל המשחק בואו נראה מה קורה אם אנחנו מנסים ליישם את אותו מנגנון בלי הדקורטור.

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

def my_cached(f):
    cache = {}
    def cached_version_of_f(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]

    return cached_version_of_f

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

def fib(n):
    print(f"fib({n})")
    if n <= 1:
        return 1

    return fib(n-1) + fib(n-2)


"""
Output:
fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
8
"""

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

better_fib = my_cached(fib)
print(better_fib(5))

הפעם התוצאה הרבה פחות משמחת. הפלט הוא שוב כמו בהתחלה עם כל ההדפסות הכפולות:

fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(2)
fib(1)
fib(0)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
8

רק בשביל להיות בטוח שאני לא הוזה הפעלתי את my_cached שוב אבל הפעם בלי ליצור פונקציה חדשה, בדיוק כמו שדקורטור היה מתנהג:

fib = my_cached(fib)
print(fib(5))

ועכשיו הכל שוב עובד כמו שצריך - בדיוק כמו שהיה קורה אם הייתי מפעיל את הדקורייטור.

מה קורה כאן? למה אי אפשר לשמור יחד את שתי הגירסאות של הפונקציה?

---

התשובה פשוטה - הפונקציה היא רקורסיבית. כשהיו לי שתי גירסאות של הפונקציה, הגירסה המתוקנת הפעילה (בקריאה הרקורסיבית) את הגירסה האיטית, וכך רק הקריאה הראשונה עברה דרך ה cache אבל כל שאר הקריאות הרקורסיביות דילגו עליו.

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