אדוונט אוף קוד החדש התחיל היום ואני שמחתי שמצאתי קצת זמן פנוי בבוקר כדי לפתור את התרגיל לפני תחילת היום. למרות שהתרגיל עצמו היה פשוט כשניסיתי להריץ את הרקורסיה קלוז'ר צעק עליי את המשפט:

Can only recur from tail position

במקום לבלבל אתכם עם הקוד שלי שיצר את השגיאה חשבתי להביא כאן גירסא קצרה יותר שגורמת לאותה בעיה:

(defn factorial-no-tail
  [n]
  (cond
        (< n 1) n
        :else (* n (recur (dec n)))))

הפונקציה factorial-no-tail היא פונקציה רקורסיבית פשוטה לחישוב עצרת, שאם תרשמו אותה בתוכנית קלוז'ר התוכנית תסרב להתקמפל ולרוץ. אז מה קורה כאן?

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

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

4! = 4 * 3!
             3 * 2!
                   2 * 1!
                         1
=>
4! = 4 * 3 * 2 * 1 = 24

בחישוב 4! נרשום בצד את 4 ואז נלך לחשב את 3!. בשביל למצוא את 3! נרשום בצד את 3 ואז נלך לחשב את 2!, בשבילו נרשום בצד את 2 ונלך לחשב את 1! ולשמחתנו 1! הוא 1. עכשיו מתחילים לגלגל אחורה ובעזרת ה-1 מגלים ש 2! הוא 2, בעזרתו אפשר לגלות ש 3! הוא 6 ואיתו נגלה ש 4! הוא 4.

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

(defn factorial-tail
  [n]
  (loop [n n acc 1]
    (cond
      (< n 1) acc
      :else (recur (dec n) (* n acc)))))

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

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

(defn factorial-recursive
  [n]
  (cond
        (< n 1) 1
        :else (* n (factorial-recursive (dec n)))))

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