רקורסיה - דוגמאות בסיסיות

רקורסיה - דוגמאות בסיסיות#

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

1. חישוב עצרת#

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

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

עצרת היא פעולה שמתבצעת על מספרים אי-שליליים (גדולים או שווים לאפס), והיא מוגדרת כמכפלת כל המספרים מ1 ועד המספר נתון. לדוגמא: \(4! = 1*2*3*4 = 24\)

להלן ההגדרה המתמטית הקלאסית לעצרת:

\(n! = 1*2*3*…(n-1)*n\)

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

\(n! = n * (n-1)!\)

\(0! = 1\)

מדוע מדובר בנוסחא רקורסיבית?

  • בביטוי הראשון - הפעולה עצרת (\(n!\)) מוגדרת על-ידי הפעלת אותה הפעולה על מספר קטן יותר (\(n-1 \)).

  • כך ניתן יהיה להפעיל את אותה נוסחא, כל פעם עם \(n\) קטן יותר, עד שנקבל \(n=0 \). במקרה זה, הנוסחא תחזיר 1 ללא קריאה נוספת לעצרת (!).

עצרו וחישבו: מה תנאי העצירה במקרה זה?

המקרה היחיד בו אין קריאה רקורסיבית הוא \(n=0 \). הוא תנאי העצירה שלנו.

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

def factorial(n):
    if n == 0: 
        return 1
    return n * factorial(n-1)

print(factorial(4))

24

עצרו וחישבו: מה יקרה אם נקרא לפונקציה הזו על מספר שלילי?

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

עצרו וחישבו: למה שמנו את בדיקת תנאי הבסיס לפני הקריאה הרקורסיבית?

אם גם במקרה של \(n=0\) נבצע קריאה רקורסיבית, לא יהיה לנו אף מקרה בסיס. כדי שרקורסיה תסתיים, היא חייבת להגיע למקרה בסיס בו אין כלל קריאות רקורסיביות!

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

פתרון בלולאות#

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

def iterative_factorial(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

print(iterative_factorial(4))

24

ככלל, בהרבה בעיות ניתן לבחור בין פתרון בלולאות לבין פתרון ברקורסיה.

מתי נעדיף להשתמש בגישה רקורסיבית במקום בלולאות?

  • נעדיף להשתמש ברקורסיה במקומות בהן הפתרון יהיה:

    • קצר ואלגנטי

    • טבעי עבור הבעיה עצמה (כמו נוסחא מתמטית רקורסיבית)

  • לעומת זאת, במקרים בהם פירוק הבעיה פחות טבעי, עלולות לצוץ הבעיות הבאות:

    • לוגיקת פתרון מסורבלת, מה שגם בד”כ מביא לכדי קוד לא קריא

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

2. סדרת פיבונאצ’י#

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

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

סדרת פיבונאצ’י מוגדרת מתמטית על-ידי הנוסחא הבאה:

\[\begin{split} \begin{aligned} fib(0) &= 0 \\ fib(1) &= 1 \\ fib(n) &= fib(n-1) + fib(n-2) \end{aligned} \end{split}\]

התחלת סדרת פיבונאצ’י נראית כך: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34...\)

כמו בחישוב העצרת, ניתן לראות כי הנוסחא המתמטית מגלמת בתוכה את הקריאה הרקורסיבית: הערך של מספר פיבונאצ’י ה-\(n\) תלוי בערכי מספרי פיבונאצ’י ה\(n-1\) ו-\(n-2\).

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

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

\[\begin{split} fib(0) = 0 \\ fib(1) = 1 \end{split}\]

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

\[ fib(n) = fib(n-1) + fib(n-2) \]

הפירוק הוא 2 קריאות לפונקצית פיבונאצ’י - עם הפרמטרים \(n-1\) ו-\(n-2\).
ההרכבה היא פעולת החיבור שנעשית על תוצאות 2 הקריאות.

מימוש בפייתון#

def fibonacci_rec(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_rec(n-1) + fibonacci_rec(n-2)

ניתן גם לצרף את 2 תנאי העצירה לתנאי אחד:

def fibonacci_rec(n):
    if n == 0 or n == 1:
        return n
    return fibonacci_rec(n-1) + fibonacci_rec(n-2)

נסו בעצמכם

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

3. סכום של רשימות מקוננות#

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

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

בבעיה זו, כל רשימה יכולה להכיל מספרים שלמים (int) או רשימות (list).
בהנתן רשימה כלשהי, נרצה להדפיס את סכום כל המספרים המוכלים בה (כולל אלו שנמצאים בתתי רשימות המוכלות בה).

לדוגמא:

\([1,2,[3,4,[5,6]],7] \Rightarrow 28 \)

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

מימוש בפייתון#

def sum_multi_nested_list(element):
    if type(element) == int: 
        return element
    sum_of_sublist = 0
    for sub_element in element:
        sum_of_sublist += sum_multi_nested_list(sub_element)
    return sum_of_sublist

נסו בעצמכם

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

sum_multi_nested_list([1,2,[3,4,[5,6]],7])

28

sum_multi_nested_list([1,2,7])

10

sum_multi_nested_list([1, [], [[[1]]]])

2
Contents