הצגת המקור של הדף "רקורסיית זנב"

{{מקורות|רמה=מחפש|נושא=מחשוב}}
'''רקורסיית זנב''' (ב[[אנגלית]]: '''Tail Recursion או Tail Call''') היא [[רקורסיה|פונקציה רקורסיבית]] המתוכננת בצורה כזו שהקריאה הרקורסיבית היא הפעולה האחרונה בפונקציה, ואין צורך לבצע פעולות נוספות על ערך החזרה מהקריאה הרקורסיבית<ref>{{צ-ספר|מחבר=Ajay Mittal|שם=Programming In C: A Practical Approach|מו"ל=Pearson Education India|שנת הוצאה=2010|עמ=284|ISBN=8131729346}}</ref>.

שימוש ברקורסיית זנב מאפשר ריצה ב[[סיבוכיות מקום]] נמוכה יותר מאשר סיבוכיות מקום פרופורציונלית לעומק מחסנית הרקורסיה<ref>{{צ-ספר|מחבר=Manuel Rubio-Sanchez|שם=Introduction to Recursive Programming|מו"ל=CRC Press|שנת הוצאה=2017|ISBN=1351647172|פרק=11}}</ref>.

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

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

באלגוריתמים הדורשים קריאות רקורסיביות רבות, רקורסיית זנב עשויה למנוע את הצפת כל הזיכרון אשר הוקצה לטובת ריצת התוכנית, ולמנוע את הצורך להקצות זיכרון חדש. בנוסף, בסוף הריצה, אין צורך לבצע התקפלות של שלבים רבים לאחור (תהליך החזרת ערכי קריאות הפונקציה), כך ריצת הרקורסיה הופכת למהירה יותר. לא כל [[שפת תכנות|שפות התכנות]] תומכות באופטימיזציות על רקורסיית זנב<ref>למשל בשפת [[פייתון]]: {{צ-ספר|שם=Functional Python Programming: Discover the power of functional programming, generator functions, lazy evaluation, the built-in itertools library, and monads, 2nd Edition|קישור=https://books.google.co.il/books?id=aKdWDwAAQBAJ&dq=python+tail+recursion&hl=iw&source=gbs_navlinks_s|מו"ל=Packt Publishing Ltd|שנת הוצאה=2018-04-13|ISBN=978-1-78862-185-4|מחבר=Steven F. Lott|שפה=en|עמ=31}}</ref>.

==דוגמה==
את פונקציית ה[[עצרת (מתמטיקה)|עצרת]] ניתן להגדיר ברקורסיה רגילה:

הגדרת !n :
# אם n=0, החזר 1.
# אחרת, החזר את <math>n! = (n-1)! \cdot n</math> 

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

הגדרת (a,b):
# אם a=0, החזר את b.
# אחרת, החזר את (a-1,a*b).
בקוד זה, הפרמטר הראשון יורד בכל [[איטרציה]] ב-1 עד שהוא מגיע ל-0 בזמן שהפרמטר השני מגדיר את העצרת. לאחר קבלת הערך הוא יוחזר אחורה בכל שלבי הרקורסיה.

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:רקורסיה]]