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

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

1. הרקורסיה הראשונה שלי

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

for i in range(1, 11):
    print(i)

אני גם יכול לכתוב פונקציה שמקבלת מספר (למשל 10) ומדפיסה את כל המספרים עד אליו:

def count_to(n):
    for i in range(1, n + 1):
        print(i)

count_to(10)

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

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

def count(start, end):
    print(start)
    count(start + 1, end)

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

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

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

def count(start, end):
    print(start)
    if start < end:
        count(start + 1, end)

וזה כבר עובד ומדפיס את כל המספרים מ-1 עד 10.

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

גישה ראשונה לכתוב את הפונקציה היא באמצעות לולאה:

def factorial1(n):
    result = 1
    for i in range(1, n + 1):
        result *= i

    return result

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

def factorial2(n):
    if n <= 1:
        return 1

    return n * factorial2(n - 1)

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

1. לוקחים את 4, רושמים אותו בצד וניגשים לחשב את שלוש עצרת.

2. כדי לחשב את 3 עצרת לוקחים את 3, רושמים אותו בצד וניגשים לחשב את שתיים עצרת.

3. כדי לחשב את 2 עצרת לוקחים את 2, רושמים אותו בצד וניגשים לחשב את אחד עצרת.

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

5. הפונקציה factorial(1) החזירה 1. עכשיו אפשר לסיים את החישוב של factorial(2) - לוקחים את ה 2 שרשמנו בצד וכופלים אותו ב-1. התוצאה, 2 היא הערך של factorial(2).

6. עכשיו שגילינו את זה אפשר לקחת את 3 שרשמנו בצד ולכפול אותו בערך שמצאנו של factorial(2). התוצאה עכשיו היא 6.

7. עכשיו אנחנו יודעים ש factorial(3) נותן 6 אפשר ללכת ל-4 שרשמנו בצד ולכפול אותו ב-6 הזה כדי לקבל את התוצאה 24.

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

2. מיון טופולוגי עם רקורסיה

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

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

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

class Task:
    def __init__(self, text):
        self.text = text
        self.depends_on = []

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

a = Task('get up')
b = Task('brush your teeth')
c = Task('get dressed')
d = Task('shave')
e = Task('wear shoes')
f = Task('go to work')

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

b.depends_on = [a]
c.depends_on = [a]
e.depends_on = [c]

f.depends_on = [a, b, c, d, e]

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

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

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

קוד הפיתרון נראה כך:

class Task:
    def __init__(self, text):
        self.text = text
        self.depends_on = []
        self.was_printed = False

    def create_todo_list(self):
        if self.was_printed:
            return

        for prerequisite in self.depends_on:
            prerequisite.create_todo_list()

        print(self.text)
        self.was_printed = True

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

3. תרגול נוסף למתקדמים

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

https://www.tocode.co.il/blog/2017-12-recursion-exercises

בהצלחה