רקורסיה

תת־שגרות עשויות לקרוא לעצמן, זו לזו, או - בקצת טקס - להחליף את מסגרת הקריאה שלהן עצמן ולהעביר את הבקרה למקום אחר מבלי להגדיל את המחסנית. עמוד זה מכסה את ארבעת המנגנונים: רקורסיה רגילה, רקורסיה הדדית, קריאות זנב goto &fn, ו־__SUB__ עבור הפניה־עצמית אנונימית. הוא גם מכסה את מגבלת העומק שבה תיתקל אם תתעלם מהם.

רקורסיה פשוטה

sub factorial {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * factorial($n - 1);
}

factorial(10);                   # 3628800

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

Perl פולט אזהרת ”Deep recursion on subroutine X“ כשתת־שגרה מבצעת רקורסיה מעבר ל־100 רמות עומק (סף זמן־הידור, PERL_SUB_DEPTH_WARN). האזהרה היא בקטגוריה recursion - no warnings 'recursion' משתיק אותה. המגבלה הקשיחה היחידה היא מחסנית מערכת ההפעלה, בדרך כלל 8 MiB כברירת מחדל, ניתנת לשליטה עם ulimit -s.

עבור עומסי עבודה עמוקים ורקורסיביים מבנית, העדף אחד מאלה:

• תור עבודה מפורש (ניסוח מחדש איטרטיבי).

• רקורסיית זנב באמצעות goto &fn (ראה להלן).

• טרמפולינה (ראה להלן).

רקורסיה הדדית

שתי תת־שגרות הקוראות זו לזו:

sub is_even {
    my ($n) = @_;
    return 1 if $n == 0;
    return is_odd($n - 1);
}

sub is_odd {
    my ($n) = @_;
    return 0 if $n == 0;
    return is_even($n - 1);
}

is_even(10);                     # 1

לרקורסיה הדדית אין טיפול מיוחד מצד זמן־הריצה - אלו רק שתי תת־שגרות שבמקרה קוראות זו לזו. אותה מגבלת עומק חלה.

אם is_even מוגדרת תחילה ומתייחסת ל־is_odd לפני ש־is_odd קיימת, תראה ”Bareword not allowed“ או ”Called undefined subroutine“ בהתאם לצורת הקריאה. הצהר מראש כדי לתקן:

sub is_odd;                      # forward declaration
sub is_even { ... is_odd($n-1) }
sub is_odd  { ... is_even($n-1) }

goto &fn - העברת קריאת־זנב

הצורה goto &SUBROUTINE מחליפה את המסגרת הנוכחית בקריאה לתת־שגרה אחרת. המסגרת הנוכחית נעלמה - היא אינה על המחסנית - כך שהקריאה אינה מגדילה את המחסנית:

sub api_v2 {
    my @args = @_;
    push @args, deprecated => 1;
    @_ = @args;
    goto &api_v1;                # tail-call: api_v1 sees the modified @_
}

זהו הכלי הנכון כאשר:

• תת־שגרת עטיפה צריכה להעביר למימוש אמיתי מבלי להשאיר אחריה מסגרת מחסנית. מעטרים, שכבות־ביניים לרישום ביומן, משגרי AUTOLOAD.

• תת־שגרה רקורסיבית יכולה לבטא את הרקורסיה שלה כ“בצע עבודה כלשהי, ואז הפוך לקריאה אחרת זו“. רקורסיית זנב קלאסית:

  sub factorial_tail {
      my ($n, $acc) = @_;
      $acc //= 1;
      return $acc if $n <= 1;
      @_ = ($n - 1, $n * $acc);
      goto &factorial_tail;
  }
  
  factorial_tail(20);            # 2432902008176640000, no stack growth
  

המכניקה: @_ הופך למערך הארגומנטים של תת־השגרה הנקראת, המסגרת הנוכחית מתפרקת, הבקרה קופצת. הקורא של תת־השגרה הנוכחית יראה את התוצאה של תת־השגרה שאליה בוצע goto, לעולם לא את זו שהוא קרא.

goto &fn הוא הצורה היחידה של goto המבצעת קריאת זנב. הצורה המבוססת־תווית (goto LABEL) אינה קשורה ומוגבלת הרבה יותר.

ראה goto עבור התיאור המלא של מילת המפתח ומגבלות הצורה.

__SUB__ - הפניה־עצמית אנונימית

use feature 'current_sub';                # or use v5.16

my $factorial = sub {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * __SUB__->($n - 1);
};

$factorial->(5);                 # 120

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

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

טרמפולינות

כשברצונך רקורסיה חסומת־מחסנית אך goto &fn מסורבל (משום שהרקורסיה הדדית, או מסתעפת למקרי־משנה רבים), תבנית הטרמפולינה עובדת:

sub trampoline {
    my $next = shift;
    while (ref $next eq 'CODE') {
        $next = $next->();
    }
    return $next;
}

sub even {
    my ($n) = @_;
    return $n == 0 ? 1 : sub { odd($n - 1)  };
}

sub odd {
    my ($n) = @_;
    return $n == 0 ? 0 : sub { even($n - 1) };
}

trampoline(even(10000));         # 1, no stack growth

כל קריאה ”רקורסיבית“ מחזירה closure שיופעל בהמשך, במקום לקרוא לעצמה ישירות. הטרמפולינה מניעה את ה־closures בלולאה. המחסנית נשארת בעומק 2 לעד.

טרמפולינות כבדות יותר מ־goto &fn (הקצאת closure אחת לכל ”קריאה“), אך הן מתכללות לבקרת־זרימה שרירותית - כולל המשכויות וקוד בסגנון CPS. עבור Perl בייצור, goto &fn הוא הבחירה הרגילה; טרמפולינות מופיעות כשמבנה הרקורסיה הופך את goto למסורבל.

מגבלת העומק, בפועל

sub recurse {
    my ($n) = @_;
    return $n if $n <= 0;
    return recurse($n - 1);
}

recurse(2000);                   # warning: Deep recursion on subroutine
                                 # (default limit 1000)

אזהרת ”Deep recursion“ היא מידעית, לא קטלנית - היא נורית פעם אחת לכל תת־שגרה. ייגמר לך מקום המחסנית בפועל הרבה לפני כל מגבלה מעשית ברוב הפלטפורמות. אם אתה רואה אזהרה זו, התשובה היא כמעט תמיד לבצע ריפקטור (לולאה איטרטיבית, goto &fn, או טרמפולינה), לא להעלות את המגבלה.

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

no warnings 'recursion';

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

ראו גם

• goto - מילת המפתח שמאחורי goto &fn.

• caller - עובד דרך מסגרות שבוצע אליהן goto עם אותו מספור כמו מסגרות רגילות.

• ארגומנטים ו־@_ - הסמנטיקה של @_ תחת goto &fn.

• הצהרה - תת־שגרות אנונימיות, התשתית עבור __SUB__ וטרמפולינות.

• תיחום - closures, התשתית עבור טרמפולינות.