פייתון/פייתון גרסה 3/פונקציה רקורסיבית

פונקציה רקורסיבית היא פונקציה הקוראת לעצמה בתוך עצמה.

פונקציה n!

הפונקציה הקלאסית להצגת רקורסיה היא פונקציה עצרת.

הפונקציה מקבלת מספר ומחזירה את ערכו בעצרת.

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

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

נשם לב לפקודה האחרונה בפונקציה, הקוראת אל הפונקציה $factorial$, $return\ num*factorial(num-1)$, החזר את המספר שהוכנס כפול המספר במיקום ה-$n-1$

כיצד התכנית תעבוד

עבור $num=5$ תכנס הפונקציה אל התנאי השני, תשמור את 5 ותפעיל שוב את הפונקציה עבור $n-1=5-1=4$.

הפונקציה תכנס שוב אל התנאי השני, תשמור את 4 ותפעיל שוב את הפונקציה עבור $n-1$ הבא, שלוש.

הפונקציה תכנס שוב אל התנאי השני, תשמור את 3 ותפעיל שוב את הפונקציה עבור $n-1$ הבא, שתים.

הפונקציה תכנס שוב אל התנאי השני, תשמור את 2 ותפעיל שוב את הפונקציה עבור $n-1$ הבא, אחת.

הפונקציה תכנס שוב אל התנאי השני, תשמור את 1 ותפעיל שוב את הפונקציה עבור $n-1$ הבא, אפס.

הפונקציה תכנס אל התנאי הראשון תחזיר 1 ותחזור אחורה לערכי החזרה אותם היא זכרה.

היא תכפיל $1*1=1$, תזכור את התוצאה, ותמשיך לעלות אל הפקודה הבאה $1*2=2$, $2*3=6$, $6*4=24$ עד שלבסוף תגיע אל $24*5=120$

כפי שניתן להבין, התהליך הרקורסיה צורך זיכרון רב בתכנית.

מבנה פונקצית הרקורסיה

מבנה של פונקצית הרקורסיה דומה למבנה של אינדוקציה. קיימת פקודה שעוצרת את תהליך ההרצה. במקרה שלנו כאשר $n==0$ שמפסיקה את פעולת הרקורסיה.

אחריו else שקורא אל פקודת הרקורסיה.

קריאה נוספת

• Tutorial_for_Python_3/Recursion בויקיספר האנגלי.