הרצאה 10 - רקורסיה

מבוא

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

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

חישוב עצרת איטרטיבי

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

int factorial(int n) {
    if(n >= 2) {
        return n;
    }
    int result = 1;
    for(int i = n; i > 1; i++) {
        result *= i;
    }
    return result;
}

זהו פתרון פשוט שיעבוד בצורה מצוינת לפי הגדרת העצרת:

$n!=n(n-1)(n-2)…3\cdot 2 \cdot 1$

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

חישוב עצרת רקורסיבי

נשים לב לעובדה הבאה בנוגע לעצרת - ניתן בקלות לפשט את הבעיה של חישוב $!n$ לבעיה פשוטה יותר, של חישוב $!(1-n)$, מכיוון שמתקיים:

$n! = n \cdot (n-1)!$

כלומר, אין צורך בכלל לדעת את $!n$ אם אנחנו יודעים את $!(1-n)$. מצד שני, ניתן לחשוב שלא עשינו כלום בכך - איך נחשב כעת את $!(1-n)$? באופן מפתיע, נעשה את אותה הפעולה שוב!

$n! = n \cdot (n-1)! = n \cdot (n-1) \cdot (n-2)!$

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

$n! = n \cdot (n-1)! = n \cdot (n-1) \cdot (n-2)!$ $=n\cdot (n-1)\cdot(n-2)\cdot…\cdot3\cdot2\cdot1$

כאשר הגענו ל-$!1$ הפסקנו לבצע את הפירוק של $!(1-n)\cdot n=!n$, מכיוון שאנו יודעים שמתקיים על פי ההגדרה $1=!1$.

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

כעת נממש את הפתרון שלנו בקוד. הוא יכיל מאפיין מעניין שטרם פגשנו:

int factorial(int n) {
    if(n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

פונקציה כמו factorial הזו, הקוראת לעצמה, נקראת רקורסיבית. אין שום מניעה שפונקציה תקרא לעצמה בשפת C - ניתן לחשוב על זאת כמעין לולאה. כאשר הוספנו את מקרה הבסיס של n <= 1, דאגנו לתנאי עצירה לאותה הלולאה.

הערה: המימוש הנ״ל בעייתי במספר מובנים - n יכול להיות שלילי, ועבור n > 12 מתקיים כי !n גדול מטווח היצוג של משתנה int. ניתן לכתוב מימושים נכונים יותר המתחשבים ביותר מקרי קצה או מכירים בהם.

רקורסיה

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

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

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

$p(n,x)=x^n$

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

$ p(x,0) = x^0 = 1 $

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

$ p(x,n) = x^n = x \cdot x^{n-1} = x p(n-1,x) $

מצאנו את מקרה הבסיס ואת צעד הרקורסיה! נכתוב מימוש:

int power(int x, int n) {
    if(n == 0) {
        return 1;
    }
    return x * power(x, n - 1);
}

דוגמא 1

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

פתרון איטרטיבי

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

#include <stdlib.h>
#include <stdio.h>
void print_reverse(void) {
    int len = 32;
    int* arr = malloc(len * sizeof(int));
    int i = 0;
    while(i < len) {
        scanf("%d", &arr[i]);
        if(arr[i] < 0) {
            break;
        }
        if(++i == len) {
            len *= 2;
            int* new_arr = malloc(len * sizeof(int));
            for(int i = 0; i < len / 2; i++) {
                new_arr[i] = arr[i];
            }
            free(arr);
            arr = new_arr;
        }
    }
    for(int j = i - 1; j >= 0; j--) {
        printf("%d\n", arr[j]);
    }
    free(arr);
}

הפתרון מאוד לא פשוט - הוא דורש לקיים מערך שגדל במידת הצורך, לבדוק לו קצוות וכו׳ - מורכב ולא טריוויאלי בכלל.

פתרון רקורסיבי

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

#include <stdio.h>
void print_reverse(void) {
    int n;
    scanf("%d", &n);
    if(n < 0) {
        return;
    }
    print_reverse();
    printf("%d\n", n);
}

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

סיבוכיות זמן ומקום בתכנות רקורסיבי

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

#include <stdio.h>
void print_reverse(void) {
    int n;
    scanf("%d", &n);
    if(n < 0) {
        return;
    }
    print_reverse();
    printf("%d\n", n);
}

נרצה לנתח את סיבוכיות הזמן והמקום של האלגוריתם הזה. סיבוכיות הזמן פשוטה יחסית - אם אורך הקלט הוא n, נבצע n קריאות לפונקציה print_reverse כאשר בכל קריאה נבצע מספר קבוע של פעולות, לסה״כ $\Theta(n)$. סיבוכיות המקום מעט מורכבת יותר. להזכירכם, כל קריאה לפונקציה דוחפת stack frame חדש על מחסנית הקריאות - המשתנים הלוקאלים של הפונקציה, כתובות חזרה וכו׳. הקריאה הרקורסיבית מתבצעת $n$ פעמים, ולכן נקצה $\Theta(n)$ זכרון על מחסנית הקריאות!

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

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

int factorial_recursive(int n) {
    if(n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
int factorial_iterative(int n) {
    int result = 1;
    for(int i = n; i > 1; i--) {
        result *= n;
    }
    return result;
}

בפתרון הרקורסיבי נבצע $n$ קריאות רקורסיביות עם $\Theta(1)$ פעולות בכל קריאה, ולכן נקבל סיבוכיות זמן של $\Theta(n)$ וסיבוכיות מקום של $\Theta(n)$ - בגלל ההקצאות על הקריאות הרקורסיביות על מחסנית הקריאות. הפתרון האיטרטיבי, לעומתו, לוקח את אותו $\Theta(n)$ בסיבוכיות הזמן, אבל מקצה מספר משתנים בודדים ולכן סיבוכיות המקום שלו היא $\Theta(1)$!

הערות:

למרות החסרון בשימוש במקום הזה של פתרון רקורסיבי, הרבה פעמים שימוש ברקורסיה מפשט משמעותית פתרון בעיות והרבה פעמים נרצה להשתמש בו. חשוב להיות מודעים למשמעויות ולוודא שאנחנו לא מקצים יותר מדי זכרון.
חשוב מאוד להיות מודעים לצריכת הזכרון של פתרונות רקורסיביים - טעות קלאסית במבחן היא לשכוח זאת ולקבל סיבוכיות מקום שגויה עבור פונקציות רקורסיביות.
ניתן לחשוב שאולי אפשר להמנע מהצורך להקצות stack frame חדש בעת קריאה רקורסיבית - הרי ניתן לכל הפחות להפטר מכתובת החזרה, מכיוון שאנחנו חוזרים לאותו מקום! מתסבר שזה נכון, וקיימות שפות תכנות גבוהות יותר עם מנגנון בשם Tail Call Optimization שמעלימות את הצורך בשימוש בזכרון נוסף לצורך קריאות רקורסיביות. בשפת C המנגנון הזה לא קיים לצערנו.

תרגילים

תרגיל 2

סדרת פיבונאצ׳י היא סדרת מספרים רקורסיבית המוגדרת ע״פ הנוסחא הבאה:

[ \left{ \begin{array}{l} F_n = F_{n - 1} + F_{n-2} \ F_0 = F_1 = 1 \end{array} \right. ]

כלומר, כל איבר בסדרה הוא סכום שני האיברים לפניו, כאשר שני האיברים הראשונים מוגדרים להיות $1$.

סעיף א׳

כתבו פונקציה רקורסיבית שמקבלת מספר אי-שלילי n ומחזירה את המספר במקום ה-n בסדרת פיבונאצ׳י.

פתרון

סדרת פיבונאצ׳י מוגדרת באופן טבעי בצורה רקורסיבית - צעד הרקורסיה ומקרי הבסיס מוגדרים לנו באופן טבעי בהגדרת הסדרה. לכן כתיבת הפונקציה אינה מאוד מסובכת:

int fib(int n) {
    if(n == 0 || n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

סעיף ב׳

חשבו כמה קריאות לפונקציה fib מתבצעות עבור fib(5). מהו fib(5)?

פתרון

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

$fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) $ $ = ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) $ $ (1 + 1) + (1 + 1) + (1 + 1 + 1) = 2 + 2 + 3 = 7 $

כלומר, מתבצעות 7 קריאות לפונקציה! נשים לב שחישבונ את fib(2) למשל 3 פעמים שונות - מאוד לא יעיל.

סעיף ג׳

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

פתרון

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

#include <stdbool.h>
#define MAX_FIB 21
#define NEW_CALC -1
int fib(int n) {
    static int fibs[MAX_FIB];
    static bool initialized = false;
    if(!initialized) {
        fibs[0] = 1;
        fibs[1] = 1;
        for(int i = 2; i < MAX_FIB; i++) {
            fibs[i] = NEW_CALC;
        }
        initialized = true;
    }
    if(fibs[n] != NEW_CALC) {
        return fibs[n];
    }
    fibs[n] = fib(n - 1) + fib(n - 2);
    return fibs[n];
}

שאלה 3

כתבו פונקציה רקורסיבית שהופכת מחרוזת נתונה in-place ללא לולאות. ניתן להניח שהמחרוזת שניתנת תקינה באורך $0\le n$.

פתרון

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

void swap(char* c1, char* c2);
void reverse_str(char* str) {
    int len = strlen(str);
    int l = 0, r = len - 1;
    while(l < r) {
        swap(&str[l++], &str[r--]);
    }
}

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

void swap(char* c1, char* c2);
void reverse_str_aux(char* str, int l, int r) {
    if(l >= r) {
        return;
    }
    swap(&str[l++], &str[r--]);
    revese_str_aux(str, l + 1, r - 1);
}
void reverse_str(char* str) {
    reverse_str_aux(str, 0, strlen(str) - 1);
}

שאלה 4

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

פתרון

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

void is_pali_aux(char* str, int l, int r) {
    if(l >= r) {
        return true;
    }
    if(str[l] != str[r]) {
        return false;
    }
    return is_pali_aux(str, l + 1, r - 1);
}
void is_pali(char* str) {
    return is_pali_aux(str, 0, strlen(str) - 1);
}

שאלה 5

כתבו פונקציה שלוקחת מחרוזת ומוחקת ממנה תווים סמוכים זהים in-place. לאחר הפונקציה המחרוזת לא תכיל שום שני תווים סמוכים זהים. לדוגמא, המחרוזת aaaabbccc תהפוך ל-abc. כתבו ללא לולאות.

פתרון

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

void remove_duplicates_aux(char* read, char* write) {
    if(!(*read)) {
        *write = '\0';
        return;
    }
    *write = *read;
    char* next = skip_duplicates(read);
}
void remove_duplicates(char* str) {
    remove_duplicates_aux(str, str);
}

Keyboard shortcuts

מבוא לתכנות בשפת C