רקורסיית זנב

רקורסיית זנב (באנגלית: 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,a*b).

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