פורסם ב זה רק קוד, מתכוננות לראיונות

רקורסיה – חלק א' – הבנת אלגוריתמים רקורסיביים

זמן קריאה: 5 דקות

הפוסט הקודם בסדרה – רקורסיה – הקדמה

מהי רקורסיה?

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

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

סדרת פיבונאצ'י נראית כך –

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 … fib(n-2) + fib(n-1)

ההגדרה למספר בסדרת פיבונאצ'י היא רקורסיבית – כל מספר (מלבד השניים הראשונים) הוא סכום של שני קודמיו בסדרה. אם נכתוב פונקציה שמחשבת מספר בסדרה היא תיראה כך –

def fib(n):
	if n <= 1:
		return 1
	else:
		return fib(n-1) + fib(n-2)

שימו לב –

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

הבנת אלגוריתם רקורסיבי

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

def sum(arr):
    if len(arr) == 0:
        return 0
    else:
        return arr[0] + sum(arr[1:])

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

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

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

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

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

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

arr = [2,5,1]
sum([2,5,1]):
    len([2,5,1]) == 0 → False
    return 2 + sum([5,1])

sum([5,1]):
    len([5,1]) == 0 → False
    return 5 + sum([1])

sum([1]):
    len([1]) == 0 → False
    return 1 + sum([])

sum([]):
    len([]) == 0 → True
    return 0

sum([1]):
    len([1]) == 0 → False
    return 1 + sum([]) 0 = 1

sum([5,1]):
    len([5,1]) == 0 → False
    return 5 + sum([1]) 1 = 6

sum([2,5,1]):
    len([2,5,1]) == 0 → False
    return 2 + sum([1,5]) 6 = 8

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

כלומר – עצרנו באמצע החישוב של sum([2,5,1]) כדי לחשב את sum([5,1]) ועצרנו באמצע החישוב שלה כדי לחשב את sum([1]) וכן הלאה…

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

הקריאה הראשונה שהחזירה תוצאה היא כמובן הפונקציה sum([]) שמהווה את תנאי העצירה שלנו. אחרי שהצבנו את ערך ההחזרה שלה בפונקציה שקראה לה אז גם היא החזירה ערך, וכן הלאה.

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

בפוסט הבא נתחיל ללמוד איך לפתח אלגוריתמים רקורסיביים.

7 תגובות בנושא “רקורסיה – חלק א' – הבנת אלגוריתמים רקורסיביים

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

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

    def fib(n, i = 1, a = 1, b = 1):
        if (i == n):
            return a
        else:
            return fib(n, i + 1, b, a + b)
    

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

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

    1. פונקציה רקורסיבית היא פונקציה שקוראת לעותק נוסף של עצמה

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

      1. בכל קריאה לפונקציה נשמר משהו ב-stack, אפילו אם זה רק כמה רגיסטרים. זה נכון שאם מסתכלים בתוך ה-CPU אז ה-program counter יחזור על אותן כתובות (כביכול מריץ את "אותה פונקציה"), אבל ההקשר מבחינת נתונים/משתנים הוא אחר. וכל פונקציה רקורסיבית אפשר לממש באופן לא-רקורסיבי, פשוט בד"כ זה אומר לכתוב לבד בדרך הקשה את מה שהקומפיילר היה עושה בשבילך.

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

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

השאר תגובה