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

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

מהי רקורסיה?

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

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

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

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

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. שימו לב תמיד לכתוב בנפרד כל קריאה לפונקציה עד סופה, ואז לשים את ערכי ההחזרה במקום המתאים בפונקציה שקראה לה.

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

פוסטים נוספים בסדרת הרקורסיות