רקורסיה
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
פונקציה הקוראת לעצמה
- רקורסיה היא כאשר פונקציה קוראת לעצמה.
- כל שיחה צריכה לעבוד על גרסה קטנה יותר של הבעיה.
- כאשר ביצוע נכון, הבעיה מתכווצת עד שהיא קלה לפתרון.
מקרה בסיסי ומקרה רקורסיבי
- ה-מקרה הבסיסי הוא המקרה הפשוט ביותר — הוא מעצור את הרקורסיה.
- ה-מקרה הרקורסיבי קורא שוב לפונקציה עם כניסה קטנה יותר.
- ללא מקרה בסיסי, הפונקציה לעולם לא תיעצר (שגיאה).
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
דוגמה פותרת: פקטוריאלי
- הפקטוריאלי
n!שווה לn × (n-1) × ... × 1. - בצורה רקורסיבית:
n! = n × (n-1)!, והמקרה הבסיסי הוא0! = 1. - כל שיחה כופלת את
nבפקטוריאלי של אחד פחות.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
איך המחשב מפעיל זאת
- כל שיחה מושבתת על שורת שיחות בזמן שהיא מחכה לשיחה הפנימית.
- כאשר המקרה הבסיסי מחזיר ערך, השיחות המושבתות מסתיימות אחת אחת.
- מספר רב מדי של שיחות גורם להצפה בשורה — Python משלחת שגיאת
RecursionError.
בפסאודוקוד קמברידג'
- פונקציה רקורסיבית מכנה במפורש את המקרה הבסיסי ואת המקרה הרקורסיבי שלה.
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
טעויות נפוצות
- לכל רקורסיה יש צורך במקרה בסיסי, אחרת היא תגרום להצפה בשורת השיחות.
- כל שיחה חייבת לקרב למקרה הבסיסי.
כעת תנסו בעצמכם
- תן לכל פונקציה מקרה בסיסי ומקרה רקורסיבי.
- לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
חקור
רקורסיב חוזר מהעלים
כל קריאה מתפצלת לקריאות קטנות יותר; התשובות חוזרות כלפי מעלה מהמקרים הבסיסיים.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה רקורסיבית sum_to(n) שהחזרתה היא 1 + 2 + ... + n. המקרה הבסיסי הוא sum_to(0) שהוא 0.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה רקורסיבית power(base, exp) שהחזרתה היא base מושוואה ל-exp. המקרה הבסיסי הוא exp == 0, שנותן 1.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב פונקציה רקורסיבית count_up(n) שהחזרתה היא הרשימה [1, 2, ..., n]. המקרה הבסיסי הוא count_up(0) שהוא הרשימה הרוקה [].
לחץ על הרץ כדי לראות את התוצא כאן.