מימוש TCO ב Python
לא מזמן כתבתי פה על מימוש אלגוריתם רקורסיבי ב Python בצורה איטרטיבית כדי להתגבר על העובדה שפייתון לא יודעת לעשות אופטימיזציה לרקורסיות זנב, ולכן יש הגבלה על עומק הרקורסיה. כמה חברים שקראו את זה שאלו אם אין דרך טובה יותר לכתוב אלגוריתם שיראה רקורסיבי אבל עדיין יכלול TCO ויאפשר רקורסיה בכל עומק.
אז האמת שיש דרך והיא אפילו די פשוטה - פשוט צריך לקחת את הקוד שכתבנו ולארגן אותו כך שאפשר יהיה להשתמש בו שוב ושוב. הרעיון בגדול:
נכתוב Decorator שיריץ את הפונקציה שלנו בלולאת while שמוציאה אלמנטים מתור וממשיכה להפעיל את הקוד שוב ושוב עד שהתור מתרוקן.
נכתוב פונקציה בשם recur שתדמה את הקריאה הרקורסיבית. בעצם מה שהפונקציה תעשה זה בסך הכל להוסיף את הפרמטרים שהעברנו לה לתור מה Decorator.
נפעיל את recur במקום את הקריאה הרקורסיבית, אבל עם אותם פרמטרים ובלי להשתמש במידע שחוזר.
קוד להמחשה? ברור-
def tco(f):
q = []
def recur(*args):
q.append(args)
def inner(*args):
q.append(args)
while len(q) > 0:
next_call_args = q.pop()
res = f(*next_call_args)
return res
inner.recur = recur
return inner
@tco
def fact(n, start=1):
if n <= 1:
return start
return fact.recur(n - 1, start * n)
print(fact(1_000))
הפונקציה fact היא פונקציה רקורסיבית המחשבת עצרת. היא כתובה כך שתוכל להשתמש באופטימיזציית מחיקת זנב הרקורסיה, ובשביל זה מקבלת גם פרמטר שני שנקרא start שבעצם מחזיק את חישוב הביניים של הרקורסיה. לפני האופטימיזציה היא היתה נכתבת כך:
def fact(n, start=1):
if n <= 1:
return start
return fact(n - 1, start * n)
והיתה נופלת בחישוב על Stack Overflow אם הייתם מנסים לחשב עצרת של מספר גדול (למשל אלף). בשביל להוסיף אופטימיזציית TCO כמעט ולא צריך שינויים: מספיק היה להוסיף את ה Decorator ולהחליף את הקריאה ל fact בקריאה ל fact.recur.
וכן אני חושב שזה חלק מהיופי של Python ובאופן כללי של הרבה שפות דינמיות - היכולת לקחת קונספט שאתה צריך שאולי לא נמצא בשפה, ולבנות אותו בצורה פשוטה וגנרית כך שאפשר יהיה להשתמש בו שוב ושוב בהמשך הפרויקט.