רקורסיית זנב

מתוך ויקיפדיה, האנציקלופדיה החופשית
Crystal Clear app help index.svg
ערך מחפש מקורות
רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים.

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

רקורסיית זנבאנגלית: Tail Recursion או Tail Call) היא פונקציה רקורסיבית המתוכננת בצורה כזו שהקריאה הרקורסיבית היא הפעולה האחרונה בפונקציה, ואין צורך לבצע פעולות נוספות על ערך החזרה מהקריאה הרקורסיבית[1].

שימוש ברקורסיית זנב מאפשר ריצה בסיבוכיות מקום נמוכה יותר מאשר סיבוכיות מקום פרופורציונלית לעומק מחסנית הרקורסיה[2].

רקע[עריכת קוד מקור | עריכה]

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

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

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

דוגמה[עריכת קוד מקור | עריכה]

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

הגדרת !n :

  1. אם n=0, החזר 1.
  2. אחרת, החזר את

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

הגדרת (a,b):

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

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Ajay Mittal, Programming In C: A Practical Approach, Pearson Education India, 2010, עמ' 284, ISBN 8131729346
  2. ^ Manuel Rubio-Sanchez, Introduction to Recursive Programming, CRC Press, 2017, פרק 11, ISBN 1351647172
  3. ^ למשל בשפת פייתון: Steven F. Lott, Functional Python Programming: Discover the power of functional programming, generator functions, lazy evaluation, the built-in itertools library, and monads, 2nd Edition, Packt Publishing Ltd, 2018-04-13, עמ' 31, ISBN 978-1-78862-185-4. (באנגלית)