רקורסיה ב-C: תנאי עצירה, עצרת ועומק ה-Stack

פונקציה שקוראת לעצמה

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

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* קוראת לעצמה, אבל אף פעם לא עוצרת! */
}

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

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* תנאי עצירה: לעצור */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* צעד רקורסיבי: בעיה קטנה יותר */
}

int main(void) {
    countdown(5);
    return 0;
}

לכל פונקציה רקורסיבית יש בדיוק שני חלקים:

• תנאי עצירה: הקלט הקטן ביותר, שהתשובה עליו ניתנת ישירות, בלי קריאה נוספת.
• צעד רקורסיבי: פותר את הבעיה בעזרת גרסה קטנה יותר ממש של עצמה.

"קטנה יותר ממש" הוא החלק שבו אנשים טועים. countdown(n - 1) מתקדם לעבר 0 בכל קריאה. countdown(n) לא היה מתקדם, וגם countdown(n / 2) לא, אם n יכול להישאר 1 לנצח. כל מסלול חייב להקטין את הבעיה, אחרת לא מגיעים לתנאי העצירה.

עצרת

הדוגמה הראשונה הקלאסית. n! הוא n × (n-1) × ... × 1, ו-0! מוגדר כ-1. ההגדרה הזו כבר רקורסיבית: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* תנאי עצירה: 0! וגם 1! שווים 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* צעד רקורסיבי */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

עקבו אחרי factorial(4) כדי לראות איך התשובה נבנית. הקריאות יורדות למטה, והכפלות קורות בדרך חזרה למעלה:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (תנאי עצירה)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

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

שימו לב לטיפוס ההחזרה. int גולש בסביבות 13! ומפיק בשקט מספר שגוי, כי C לא בודקת. unsigned long long מביא אתכם עד 20! ולא יותר, כי 21! חורג מ-64 ביט. הרקורסיה היא לא הגורם המגביל כאן, הטיפוס הוא.

תנאי העצירה משתמש ב-n <= 1 ולא ב-n == 1 בכוונה: factorial(0) צריך להיות 1, ו-<= מטפל בזה. עם n == 1, קריאה ל-factorial(0) הייתה ממשיכה ל--1, ל--2, ולא הייתה מסתיימת אף פעם. זו המחשה טובה לאיך תנאי עצירה "נכון בעליל" יכול לפספס קלט.

פיבונאצ'י, ולמה הגרסה הנאיבית היא מלכודת

פיבונאצ'י היא הדוגמה הקלאסית השנייה: כל מספר הוא סכום שני המספרים שלפניו, החל מ-0 ו-1. ההגדרה הרקורסיבית כותבת את עצמה.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

הסתכלו על מספר הקריאות. fib(10) דורשת 177 קריאות, ו-fib(35) דורשת כמעט 30 מיליון. כל צעד של 5 מכפיל את העבודה בערך פי אחת־עשרה.

הסיבה נראית בעץ הקריאות. fib(5) קוראת ל-fib(4) ול-fib(3), fib(4) קוראת ל-fib(3) שוב, וכל אחת מהן מחשבת את fib(2) מאפס. שום דבר לא נזכר, ולכן אותן תתי־בעיות נפתרות שוב ושוב, ומספר הקריאות גדל בערך כמו 1.6ⁿ. fib(50) בדרך הזו הייתה רצה ימים, ו-fib(100) הייתה נמשכת יותר מהיקום.

גרסת הלולאה שומרת את שני הערכים האחרונים והיא ליניארית:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

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

מחסנית הקריאות ו-stack overflow

כל קריאה לפונקציה צריכה מקום לשמור בו את הפרמטרים, את המשתנים המקומיים ואת הכתובת לחזור אליה. האחסון הזה הוא stack frame, שנדחף כשהקריאה מתחילה ונשלף כשהיא חוזרת. רקורסיה מערימה frames אחד על השני: ל-factorial(1000) יש אלף frames חיים בו־זמנית, כל אחד עם ה-n שלו.

ה-stack לא גדול. ברירת מחדל טיפוסית היא 1 עד 8 MB, כך שכמה עשרות אלפי frames הם הגבול המציאותי, והרבה פחות אם כל frame מחזיק מערך מקומי גדול. עברו אותו, והתוכנית מתה:

Segmentation fault (core dumped)

זה stack overflow, ויש שתי דרכים להגיע אליו:

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

int bad(int n) {
    return bad(n - 1);      /* אין תנאי עצירה: קורסת בתוך שבריר שנייה */
}

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

חלק מהקומפיילרים יכולים להפוך tail recursion, שבה הקריאה הרקורסיבית היא הדבר האחרון שהפונקציה עושה, בלי עבודה ממתינה אחריה, ללולאה שמשתמשת שוב ב-frame אחד. countdown שלמעלה היא tail recursive, ו-factorial לא, כי הכפל עדיין צריך לקרות אחרי שהקריאה חוזרת. אבל C לא מחייבת את האופטימיזציה הזו, ולכן היא עשויה לקרות או לא, תלוי בקומפיילר ובדגלים. לעולם אל תכתבו קוד C שעובד רק כי ה-optimizer ביטל קריאת זנב.

איפה רקורסיה באמת מנצחת

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

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

#include <stdio.h>

/* מחזירה את האינדקס של target, או -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* תנאי עצירה: לא נשאר כלום */
    }
    int mid = low + (high - low) / 2;       /* מונע גלישה באינדקסים גדולים */

    if (a[mid] == target) {
        return mid;                         /* תנאי עצירה: נמצא */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

כאן יש שני תנאי עצירה, וזה רגיל: אחד להצלחה ואחד למיצוי. העומק הוא בערך log₂(n), כך שגם מיליארד איברים צריכים רק שלושים frames.

מקומות נוספים שבהם רקורסיה מתאימה באופן טבעי: מעבר על עץ או על רשימה מקושרת, סריקת תיקיות, ניתוח ביטויים מקוננים ומיונים מסוג divide and conquer כמו quicksort ו-merge sort. בכולם הקוד הרקורסיבי קצר וגם ברור יותר מהלולאה עם stack מפורש שמחליפה אותו.

רקורסיה או לולאה?

לולאה: כשהבעיה ליניארית, כמו ספירה, סכימה וסריקה
רקורסיה: כשהנתונים מקוננים, כמו עצים, מבנים מקוננים ו-divide and conquer
לשכתב את הרקורסיה: אם העומק יכול לגדול עם גודל הקלט בלי גבול
אף פעם לא רקורסיה: כשתתי־בעיות חופפות, אלא אם שומרים תוצאות (memoization)

שתי הערות מעשיות. קריאות רקורסיביות עולות קצת יותר מאיטרציה של לולאה, כי צריך לדחוף ולשלוף frame בכל פעם, ולכן בלולאות פשוטות וחמות הגרסה האיטרטיבית מנצחת גם במהירות וגם בזיכרון. וגם הדיבוג שונה: stack trace מרקורסיה עמוקה הוא מאות frames שנראים זהים, לכן הדפיסו את הפרמטר בכניסה (כמו מונה ה-calls שלמעלה) כשמשהו לא מסתיים.

כתיבת פונקציה רקורסיבית: רשימת בדיקה

1. מצאו קודם את תנאי העצירה. מה הקלט הקטן ביותר, ומה התשובה עליו? אם אי אפשר לנסח אותו, אי אפשר לכתוב את הפונקציה.
2. הניחו שהקריאה הרקורסיבית עובדת. אל תעקבו אחריה בראש: סמכו על factorial(n - 1) שתחזיר (n-1)!, וכתבו את הצעד האחד שהופך את זה לתשובה.
3. ודאו שכל מסלול מקטין את הבעיה. כל קריאה רקורסיבית חייבת להתקדם לעבר תנאי העצירה עבור כל קלט אפשרי, כולל 0 ומספרים שליליים.
4. בדקו את העומק. בערך כמה frames לעומק זה יגיע על נתונים אמיתיים? אלפים זה בסדר, מיליונים לא.
5. בדקו חפיפה. אם אותה תת־בעיה מחושבת פעמיים, צריך memoization או לולאה.