מבוא לרקורסיה

מבוא לרקורסיה#

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

טקסט המופיע למטה בסגול מציין קטעים המופיעים בסרטון

ניתן להיעזר בו כדי לחזור על התכנים או לעיין בהם שוב.

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

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

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

נחזור למדעי המחשב:
ברקורסיה, במקום לפתור בעיה גדולה ישירות, מפרקים אותה לתתי-בעיות (Decomposition) קטנות יותר מאותו סוג , עד שמגיעים לנקודה פשוטה שאותה ניתן לפתור ללא פירוק נוסף.
נקרא לנקודה זו תנאי עצירה או מקרה בסיס (Base case).
לאחר מכן, מרכיבים את תתי הבעיות הללו יחדיו (Aggregation) כדי לפתור את הבעיה השלמה.

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

מקרה בסיס/תנאי עצירה (Base case)

פירוק לתתי בעיות (Decomposition)

שימוש בפתרון תתי הבעיות כדי לפתור את הבעיה המקורית (Aggregation)

דוגמא - מטריושקה#

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

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

  • נפתח את המטריושקה שקיבלנו.

  • נספור כמה בובות בתוכה.

  • נוסיף 1 (כדי לספור גם את הבובה הנוכחית).

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

במקרה זה, הרקורסיה באה לידי ביטוי בכך שבכל שלב הקטנו את הבעיה לבעיה “יותר פשוטה” מאותו סוג - ספירת הבובות שיש בתוכה (+1).

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

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

  1. קבל את הבובה הנוכחית.

  2. נסה לפתוח את הבובה.

  3. אם אין בובה בפנים:
    3.1 החזר 1 עבור ספירת הבובה הנוכחית.

  4. אם יש בובה בפנים:
    4.1 פתח את הבובה ובצע על הבובה הבת את האלגוריתם הזה.
    4.2 החזר את התשובה אשר קיבלת מ4.1, בתוספת 1 עבור ספירת הבובה הנוכחית.

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

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

פונקציות שקוראות לפונקציות אחרות#

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

def h():
    s = "h "
    print(s + "start")
    print(s + "done")

h()

h start
h done

def g():
    s = "g "
    print(s + "start")
    h()
    print(s + "done")

g()

g start
h start
h done
g done

def f():
    s = "f "
    print(s + "start")
    g()
    print(s + "done")

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

בכל פעם שמתבצעת קריאה לפונקציה, נפתח scope חדש שבו נשמרים המשתנים המקומיים של אותה קריאה.
כאשר הפונקציה מסיימת את פעולתה, ה-scope שלה נמחק מהזיכרון.
למעשה, ה-scopes נערמים אחד על גבי השני: כל קריאה חדשה מתווספת למעלה, וכשמסיימים – הקריאה האחרונה שהתווספה היא הראשונה שנמחקת.
או במילים אחרות Last in - first out (LIFO).

נסו כעת זאת ב-Python Tutor:
הריצו את הקוד שורה שורה, ועקבו אחר סדר פתיחת וסגירת ה-scopeים.

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

טקסט המופיע למטה בסגול מציין קטעים המופיעים בסרטון

ניתן להיעזר בו כדי לחזור על התכנים או לעיין בהם שוב.

בואו נראה את “ערימת” ה-scopes כאשר פונקציה הקוראת לעצמה.

נתבונן בפונקציה R שלפנינו:

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

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

לכן, אם ננסה להריץ את הפונקציה נקבל שגיאה:

this is R
...
this is R
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)

Cell In[24], line 1
----> 1 recursive_function()
Cell In[22], line 3, in recursive_function()
      1 def R():
      2     print("This is R")
----> 3     R()

line 3, in R()

RecursionError: maximum recursion depth exceeded while calling a Python object

כלומר, השגיאה שקיבלנו היא:

RecursionError: maximum recursion depth exceeded

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

עצרו וחישבו מה עלינו לעשות כדי להריץ את R בלי שהתכנית תקרוס?

נזכר שרקורסיה תקנית כוללת:

  • מקרה בסיס/תנאי עצירה (Base case)

  • פירוק לתתי בעיות (Decomposition)

  • הרכבת תתי הבעיות כדי לפתור את הבעיה המקורית (Aggregation)

מקרה הבסיס למעשה מונע מהרקורסיה לרוץ “לנצח”, ולכן מונע את קריסת התכנית בעקבות maximum recursion depth.

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

נבחן את השינוי הבא בפונקציה R:

def R(n):
    if n < 0:
        return
    print("This is R " + str(n))
    R(n-1)

def R(n):       
    print("This is R " + str(n))
    if n >= 0: 
        R(n-1)

כעת, לפונקציה R יש תנאי עצירה - עבור n<0, הפונקציה לא תקרא לעצמה רקורסיביות.
בנוסף, בכל קריאה, הפונקציה מתקרבת לתנאי העצירה בכך שהיא מקטינה את n.

נראה כעת כיצד תנאי העצירה בא לידי ביטוי בקטע הקוד הבא:

def R(n):       
    if n < 0:
        return
    
    print("This is R " + str(n))
    R(n-1)  
        
R(4)

This is R 4
This is R 3
This is R 2
This is R 1
This is R 0

עבור הרצה זו, ערימת הscopes תראה כך:

נסו כעת זאת ב-Python Tutor:
הריצו את הקוד שורה שורה, ועקבו אחר סדר פתיחת וסגירת ה-scopeים.

מה בעצם קרה במקרה הזה?
כעת R מקבלת פרמטר n (מספר חיובי).
תחילה, נבדק תנאי העצירה שהוספנו - if n < 0. אם הוא אינו מתקיים, מחסירים 1 מn ואז קוראים לפונקציה פעם נוספת, עם הערך המופחת.
התהליך יימשך עד שערך הקלט יהיה שלילי, ואז יתקיים תנאי העצירה, בו נחזיר ערך ללא קריאה נוספת לפונקציה.

שימו לב

על מנת שתנאי העצירה יתקיים, עלינו לוודא כי תתי-הקריאות מקרבות את ערכי הקלט לתנאי הבסיס שלנו.
במקרה של R, בכל תת-קריאה ערך הקלט מתקרב ל0.

Contents