recursive tail

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

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

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

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

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

הגישה המוכרת ביותר לכך נקראת tail recursion. או רקורסיית זנב בעברית טכנית.

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

מה הכוונה? אשתמש בקוד רובי (שהוא לדעתי קריא מאוד) לשם כך.

רקורסיה בגישה ה"רגילה" תהיה כתובה כך:

def recursive(n)
  if n <= 1
    1
   else
     n * recursive(n - 1)
   end
end

recursive(4)
=> 24

רקורסיית זנב, תראה כך:

def tail_recursive(current, n, result)
  return result if current <= n

  new_result = result * current
  tail_recursive(current + 1, n, new_result)
end

tail_recursive(1, 4, 1)
=> 24

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

אבל לא הכל ורוד בזה. קשה יותר לדבג בעיות ברקורסיית זנב, היות ולמעשה אין לנו stack frames רבים, שיהיה ניתן להבין באיזה שלב יש בעיה. ובכך אין לנו stack trace שיסייע לנו בנושא.

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

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

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s