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

מקרה בסיס

המקרה הקטן ביותר, שהתשובה שלו ידועה בלי עוד קריאה. אצל עצרת: 0! = 1. בלי מקרה בסיס, הפונקציה קוראת לעצמה בלי סוף.

צעד רקורסיבי

הפונקציה קוראת לעצמה עם בעיה קטנה יותר, ומשתמשת בתשובה: 4! = 4 · 3!. כל קריאה חייבת להתקרב למקרה הבסיס.

מחסנית הקריאות

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

אין מקרה בסיס

הפונקציה קוראת לעצמה שוב ושוב. אחרי בערך 1000 קריאות פייתון עוצר אותה עם RecursionError.

def fact(n):
    return n * fact(n - 1)

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

מתרחקים מהבסיס

יש מקרה בסיס, אבל לא מגיעים אליו. עם n + 1 המספר רק גדל, ו-fact(-1) מדלג מעל 0.

    return n * fact(n + 1)
print(fact(-1))

    return n * fact(n - 1)
print(fact(4))

שוכחים return

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

    if n == 0:
        return 1
    n * fact(n - 1)

    if n == 0:
        return 1
    return n * fact(n - 1)

ערך בסיס לא נכון

אם מקרה הבסיס מחזיר 0, כל המכפלה מתאפסת. בכפל הבסיס הוא 1, ובחיבור הוא 0.

    if n == 0:
        return 0

    if n == 0:
        return 1