א.15 — רקורסיה

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

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

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

מחברות האוניברסיטה הפתוחה — 8-רקורסיה

מה קורה בקריאה לפונקציה?

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

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

def main():
    a = 5
    print("main head:", a)
    f1(a + 1)
    print("main bottom:", a)

def f1(a):
    print("f1 head:", a)
    a += 1
    f2(a + 1)
    print("f1 bottom:", a)

def f2(a):
    print("f2 head:", a)
    a += 1
    print("f2 bottom:", a)

main()

פלט

main head: 5
f1 head: 6
f2 head: 8
f2 bottom: 9
f1 bottom: 7
main bottom: 5

יש כאן שלושה משתנים שונים ששמם a, אחד בכל סביבת עבודה. main העבירה ל־f1 את הערך 6, ו־f1 הגדילה את ה־a שלה ל־7 והעבירה ל־f2 את הערך 8. f2 הגדילה את ה־a שלה ל־9, אבל כשהיא הסתיימה וחזרנו ל־f1, ה־a של f1 היה עדיין 7, וכשחזרנו ל־main ה־a שלה היה עדיין 5. שינוי בסביבה אחת אינו נראה בסביבה אחרת. התרשים מציג את שלוש סביבות העבודה, את הקריאות בירוק ואת החזרות באדום:

הסביבות האלה נשמרות במבנה שנקרא מחסנית — Stack. מחסנית פועלת כמו ערמת צלחות: מניחים צלחת חדשה תמיד למעלה, ולוקחים תמיד את העליונה. האחרון שנכנס הוא הראשון שיוצא, ובאנגלית LIFO, כלומר Last In First Out. כל קריאה לפונקציה נדחפת לראש המחסנית, והפונקציה שבראש היא זו שרצה כרגע. כשהיא מסתיימת היא מוסרת מהמחסנית, והפונקציה שמתחתיה חוזרת להיות בראש וממשיכה מהמקום שבו נעצרה. לכן הפונקציה שנכנסה אחרונה, f2, היא הראשונה שמסיימת, ו־main, שנכנסה ראשונה, מסיימת אחרונה:

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

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

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

def count_up(a):
    print(a, end=" ")
    count_up(a + 1)

count_up(1)

פלט

1 2 3 4 5 6 7 8 9 10 11 12 ... 995 996 997 998
RecursionError: maximum recursion depth exceeded

כל קריאה מדפיסה, פותחת קריאה חדשה וממתינה לה, ואף קריאה אינה מסתיימת. המחסנית מתמלאת בסביבות עבודה: a = 1, מעליה a = 2, מעליה a = 3, וכן הלאה:

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

תנאי עצירה

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

def count_up(a):
    if a == 4:
        print("stop")
        return
    print(a)
    count_up(a + 1)

count_up(1)

פלט

1
2
3
stop

עכשיו נוצרות ארבע סביבות עבודה, ובקריאה הרביעית התנאי מתקיים: מודפס stop והפונקציה חוזרת בלי קריאה נוספת. מכאן מתחילה הדרך חזרה. הקריאה עם a = 3 הייתה ממתינה בשורה שאחרי count_up(a + 1), ומכיוון שאין שם עוד פקודות היא מסתיימת אף היא, וכך גם הקריאות עם a = 2 ועם a = 1. את הריצה נוח לתאר בשני שלבים. הלוך: הקריאות נערמות זו על זו עד שמגיעים לתנאי העצירה. חזור: הקריאות מסתיימות בסדר הפוך, מהפנימית ביותר החוצה, וכל אחת ממשיכה מהמקום שבו נעצרה:

שימו לב לשני פרטים חשובים בקוד. הפרמטר משתנה בכל קריאה, a + 1, ולכן כל קריאה מתקרבת לתנאי העצירה. ובלי ה־return שבתוך התנאי, הפונקציה הייתה ממשיכה להדפיס ולקרוא לעצמה גם אחרי stop. הדוגמה מיועדת להתחלה שאינה גדולה מ־4; אם נתחיל ב־5, לעולם לא נגיע לתנאי העצירה ונקבל שוב RecursionError.

הלוך וחזור: הסדר בתוך הפונקציה קובע

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

def print_before(n):
    if n == 0:
        return
    print(n)
    print_before(n - 1)

def print_after(n):
    if n == 0:
        return
    print_after(n - 1)
    print(n)

print_before(3)
print("---")
print_after(3)

פלט

3
2
1
---
1
2
3

ב־print_before כל קריאה מדפיסה ומיד קוראת הלאה, ולכן המספרים מודפסים בדרך הלוך, מ־3 ל־1. ב־print_after כל קריאה קודם קוראת הלאה וממתינה, ורק כשהקריאה הפנימית חזרה היא מדפיסה. שום דבר אינו מודפס בדרך הלוך; ההדפסות מתבצעות בחזור, ולכן הקריאה הפנימית ביותר שנותרה, זו עם n = 1, מדפיסה ראשונה:

אותה פונקציה יכולה לעשות משהו גם לפני הקריאה וגם אחריה. אם נדפיס את n בשני המקומות נקבל 3 2 1 בהלוך ואז 1 2 3 בחזור. זו הנקודה המרכזית בפרק: ברקורסיה הולכים וחוזרים, ומקומה של פקודה ביחס לקריאה הרקורסיבית קובע אם היא תתבצע בדרך פנימה או בדרך החוצה. כשהקריאה הרקורסיבית היא הפעולה האחרונה בפונקציה, כמו ב־print_before, מדברים על רקורסיית זנב — Tail Recursion: כל העבודה נעשית בהלוך, ובחזור לא נותר מה לעשות. כשהקריאה מופיעה בתחילה והעבודה אחריה, כמו ב־print_after, מדברים על רקורסיית ראש — Head Recursion: העבודה נעשית בחזור.

סכמת הרקורסיה

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

def func(params):
    if stop_condition:
        # do something
        return

    # do something      (optional, on the way in)
    func(smaller_params)
    # do something      (optional, on the way back)

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

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

פונקציה שמחזירה ערך

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

def is_power_of_two(num):
    if num == 2:
        return True
    if num % 2 != 0:
        return False
    res = is_power_of_two(num // 2)
    return res

print(is_power_of_two(8))
print(is_power_of_two(12))

פלט

True
False

כאן יש שני תנאי עצירה: num == 2 מחזיר True, ומספר אי־זוגי מחזיר False. הקריאה עם 8 אינה יודעת את התשובה, ולכן היא קוראת לקריאה עם 4 וממתינה. הקריאה עם 4 גם היא אינה יודעת, וקוראת לקריאה עם 2, שם התשובה ידועה ומוחזר True. עכשיו מתחיל החזור: הקריאה עם 4 מקבלת את True לתוך res ומחזירה אותו כפי שהוא, הקריאה עם 8 מקבלת אותו לתוך ה־res שלה ומחזירה גם היא, עד שהערך מגיע ל־print. הערך שנקבע פעם אחת בתנאי העצירה מפעפע למעלה דרך כל הקריאות הממתינות:

המשתנה res אינו הכרחי. אפשר להחזיר את תוצאת הקריאה ישירות, וזו הצורה המקובלת:

def is_power_of_two(num):
    if num == 2:
        return True
    if num % 2 != 0:
        return False
    return is_power_of_two(num // 2)

print(is_power_of_two(8))

פלט

True

השורה return is_power_of_two(num // 2) עושה בדיוק את שני הדברים שעשו שתי השורות הקודמות: ממתינה לתשובה של הקריאה הפנימית, ומחזירה אותה. לכן בפונקציה שמחזירה ערך חובה לכתוב return בשני מקומות, בתנאי העצירה שבו התשובה נקבעת, ולפני הקריאה הרקורסיבית, כדי שהתשובה תועבר הלאה. אם נשכח את ה־return שלפני הקריאה, הקריאה הפנימית תחשב את התשובה, אבל הקריאה החיצונית תזרוק אותה ותחזיר None.

עם 12 הריצה קצרה יותר: 12 זוגי, הקריאה עם 6 גם, אבל 3 אי־זוגי, ומשם מפעפע False. הגרסה הבאה מחזירה את המעריך במקום True. הפרמטר הנוסף exp סופר בהלוך כמה פעמים חילקנו, ותנאי העצירה מחזיר את הספירה שהצטברה:

def power_of_two_exponent(num, exp=1):
    if num == 2:
        return exp
    if num % 2 != 0:
        return -1
    return power_of_two_exponent(num // 2, exp + 1)

print(power_of_two_exponent(8))
print(power_of_two_exponent(12))

פלט

3
-1

צבירה בדרך פנימה — חישוב בהלוך

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

def sum_list_forward(numbers, total=0, index=0):
    if index == len(numbers):
        return total
    return sum_list_forward(
        numbers, total + numbers[index], index + 1)

print(sum_list_forward([3, 5, 3, 0, 7, -2]))

פלט

16

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

חישוב בדרך חזרה — חישוב בחזור

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

def sum_list(numbers, index=0):
    if index == len(numbers):
        return 0
    return numbers[index] + sum_list(numbers, index + 1)

print(sum_list([3, 1, 9, 10, -4]))

פלט

19

בתנאי העצירה אין עוד איברים לסכום, ולכן מוחזר 0. בדרך חזרה כל קריאה מוסיפה את האיבר שלה לתוצאה שקיבלה. למשל, עבור [3, 1] מתקבל בהדרגה 0, אחר כך 1 + 0, ולבסוף 3 + 1. פייתון אינה יכולה לחשב את numbers[index] + ... לפני שהקריאה הפנימית חזרה, ולכן כל קריאה ממתינה במחסנית עם האיבר שלה עד שהתשובה מגיעה. באותה דרך מחשבים עצרת: n! הוא n כפול (n-1)!, ו־1! הוא 1:

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

print(factorial(4))

פלט

24

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

רקורסיה עם שתי קריאות — עץ הקריאות

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

נדגים זאת בשאלה מקומבינטוריקה: מהן כל המחרוזות באורך 3 שאפשר לבנות משתי האותיות a ו־b? הרעיון: בכל מקום פנוי מציבים פעם a ופעם b, וממשיכים למקום הבא. הפרמטר n סופר כמה מקומות נותרו למלא, והמחרוזת st נבנית בהלוך. כשלא נותרו מקומות, המחרוזת שלמה ומדפיסים אותה:

def combination_string(n, st=""):
    if n == 0:
        print(st)
        return
    combination_string(n - 1, st + "a")
    combination_string(n - 1, st + "b")

combination_string(3)

פלט

aaa
aab
aba
abb
baa
bab
bba
bbb

איך נראים ההלוך והחזור בעץ? הקריאה הראשונה, עם מחרוזת ריקה, קוראת קודם לענף a. הענף הזה קורא לענף aa, וזה לענף aaa, שם תנאי העצירה מתקיים ומודפס aaa. עכשיו הקריאה aaa מסתיימת, וחוזרים לקריאה aa, אבל היא עדיין לא סיימה: נותרה לה הקריאה השנייה, עם aab. רק אחרי ששני הענפים שלה חזרו, aa מסתיימת וחוזרים ל־a, שפונה לענף השני שלה, ab. כך ממשיכים: יורדים לעומק עד לעלה, חוזרים צעד אחד למעלה, ויורדים לענף הבא. סדר סריקה זה נקרא חיפוש לעומק — DFS, Depth First Search, ונפגוש אותו שוב באלגוריתמים על גרפים. בתרשים הבא החצים השחורים הם הקריאות בהלוך, והאדומים הם החזרות:

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

def count_combinations(n, st=""):
    if len(st) == n:
        return 1
    return (count_combinations(n, st + "a")
            + count_combinations(n, st + "b"))

print(count_combinations(3))
print(count_combinations(4))

פלט

8
16

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

יש בעיות שבהן ההגדרה עצמה נשענת על שני מקרים קטנים יותר. בסדרת פיבונאצ׳י מתחילים ב־0 וב־1, וכל איבר נוסף הוא סכום שני קודמיו: 0, 1, 1, 2, 3, 5, 8 וכן הלאה. לכן המימוש הישיר מפעיל שתי קריאות, אחת לכל אחד משני האיברים הקודמים; הוא מיועד לאינדקס שלם שאינו שלילי:

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

print(fibonacci(6))

פלט

8

כאן יש שני תנאי עצירה, לאינדקס 0 ולאינדקס 1, ו־fibonacci(6) מחזירה 8, האיבר השביעי בסדרה. גם כאן עץ הקריאות מתפצל, אך בניגוד לעץ המחרוזות, אותו חישוב חוזר בענפים שונים: fibonacci(6) קוראת ל־fibonacci(5) ול־fibonacci(4), ו־fibonacci(5) קוראת שוב ל־fibonacci(4). הקוד מתאים להמחשת ההגדרה, אך אינו יעיל לחישוב איברים רחוקים. בהמשך הקורס נפגוש את הרעיון של שמירת תוצאות במקום לחשבן שוב.

בחירה בין שתי אפשרויות — Backtracking

עץ הקריאות מאפשר לפתור סוג שלם של בעיות שבהן צריך לבדוק צירופים. הדוגמה האופיינית: האם קיימת תת־קבוצה של איברי הרשימה שסכומה שווה למספר נתון? למשל ברשימה [3, 7, 2, 5] אפשר להגיע ל־9 בעזרת 7 ו־2. בלולאה רגילה קשה לעבור על כל הצירופים, כי מספר הצירופים גדל פי 2 עם כל איבר. ברקורסיה הפתרון טבעי: על כל איבר מחליטים החלטה אחת, לקחת אותו או לדלג עליו, ומעבירים את ההחלטה הלאה. כל החלטה היא ענף בעץ, וכל מסלול מהשורש לעלה הוא צירוף אחד.

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

def has_subset_sum(lst, target, i=0):
    if target == 0:
        return True
    if i == len(lst):
        return False
    skip = has_subset_sum(lst, target, i + 1)
    take = has_subset_sum(lst, target - lst[i], i + 1)
    return skip or take

print(has_subset_sum([3, 7, 2, 5], 9))
print(has_subset_sum([4, 8, 10], 7))

פלט

True
False

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

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

def can_split_equal_sum(lst, i=0, sum1=0, sum2=0):
    if i == len(lst):
        return sum1 == sum2
    first = can_split_equal_sum(lst, i + 1, sum1 + lst[i], sum2)
    second = can_split_equal_sum(lst, i + 1, sum1, sum2 + lst[i])
    return first or second

print(can_split_equal_sum([1, 5, 6]))
print(can_split_equal_sum([1, 2, 5]))

פלט

True
False

ברשימה [1, 5, 6] הענף שבו 1 ו־5 בקבוצה הראשונה ו־6 בשנייה מגיע לשוויון, ולכן התשובה True. ברשימה [1, 2, 5] כל שמונת המסלולים בעץ נבדקים, אף אחד אינו מגיע לשוויון, והתשובה False. כשניגשים לשאלה כזאת כדאי לזהות תחילה את שלושת הרכיבים: מהי ההחלטה שמקבלים על כל איבר, מה מועבר בהלוך, ומה ההחלטה בחזור על סמך שתי התוצאות.