רקורסיית זנב

רקורסיית זנב (באנגלית: Tail Recursion או Tail Call) היא פונקציה רקורסיבית המתוכננת כך שתאפשר ריצה בסיבוכיות מקום נמוכה יותר מאשר סיבוכיות מקום פרופורציונלית לעומק מחסנית הרקורסיה.

רקע

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

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

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

דוגמה

את פונקציית העצרת ניתן להגדיר ברקורסיה רגילה:

הגדרת !n :

1. אם n=0, החזר 1.
2. אחרת, החזר את $n!=(n-1)!\cdot n$

אם נרצה לכתוב את הקוד בעזרת רקורסיית זנב, נכתוב אותו כך שיקבל זוג סדור (n,1) ויפעל בצורה הבאה:

הגדרת (a,b):

1. אם a=0, החזר את b.
2. אחרת, החזר את (a-1,ab).

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