רקורסיה ב-Python לנוער: פותחים קופסה בתוך קופסה
פונקציה שקוראת לעצמה נשמעת כמו מתכון ללולאה אינסופית. אבל כשנותנים לכל קריאה משימה קטנה יותר ונקודת עצירה ברורה, מתקבל כלי מדויק לפתרון בעיות מקוננות.
כמה מטבעות יש בכל התיבות יחד?
בתיבת אוצר יש מטבעות, אבל יכולות להיות בה גם תיבות קטנות. בכל אחת מהן יש מטבעות ואולי עוד תיבות. אי אפשר לדעת מראש כמה שכבות נצטרך לפתוח. זו בדיוק הצורה שבה רקורסיה מתחילה להיות שימושית.
חומרי Python שסופקו למכללה כוללים פונקציות, פרמטרים, ערכים חוזרים ורקורסיה. הדוגמה כאן מסבירה את הרעיונות היציבים האלה ואינה מתארת תוכנית לימודים או כלי עדכני.
תיבה ראשית · 4 מטבעות
מכילה תיבה כחולה ותיבה אדומה
כחולה · 3
בתוכה: ירוקה · 2
אדומה · 5
אין תיבות נוספות
נסו לחשב לפני שממשיכים: 4 + 3 + 2 + 5 = ?
כל פונקציה רקורסיבית צריכה לדעת לעצור ולהקטין
1. מקרה בסיס
זה המצב שבו אפשר לענות מיד. אם בתיבה אין תיבות משנה, מחזירים את מספר המטבעות שבה. אין צורך לקרוא שוב לפונקציה.
2. צעד רקורסיבי
אם יש תיבות משנה, מפעילים עליהן את אותה פונקציה. הבעיה קטנה מפני שכל קריאה יורדת לתיבה פנימית יותר, עד שמגיעים לתיבה שאין בתוכה עוד תיבות.
אותה שאלה, תיבה קטנה יותר
הפונקציה מתחילה במטבעות של התיבה הנוכחית. לאחר מכן היא מבקשת מכל תיבת משנה לספור את עצמה, ומצרפת את המספר שחזר לסכום.
אין כאן פקודת עצירה נפרדת: כשהרשימה chests ריקה, הלולאה לא רצה והפונקציה מגיעה מיד ל-return. זהו מקרה הבסיס.
def count_coins(chest):
total = chest["coins"]
for smaller_chest in chest["chests"]:
total += count_coins(smaller_chest)
return totalיורדים עם הקריאות, עולים עם התשובות
Python שומר לכל קריאה את המשתנים ואת המקום שאליו צריך לחזור. אוסף הקריאות הממתינות נקרא מחסנית קריאות. הקריאה האחרונה שנפתחה היא הראשונה שתסיים.
- עומק 1ממתינה לתוצאות של שתיהן
התיבה הראשית
מוצאת 4 מטבעות ושתי תיבות קטנות
- עומק 2ממתינה לתוצאה מהתיבה הירוקה
התיבה הכחולה
מוצאת 3 מטבעות ותיבה אחת נוספת
- עומק 3מחזירה 2
התיבה הירוקה
מוצאת 2 מטבעות ואין בה תיבות
הדרך חזרה: ירוקה מחזירה 2 ← כחולה מחזירה 5 ← הראשית מצרפת גם את האדומה ומחזירה 14.
זו נקודה חשובה: רקורסיה אינה רק ירידה לעומק. חצי מהסיפור הוא הערכים שחוזרים מכל קריאה ומאפשרים לרמה שמעליה להשלים את החישוב.
לא כל חזרה צריכה רקורסיה
לולאה ורקורסיה יכולות לפעמים לפתור אותה בעיה. השאלה הטובה היא לא מה נראה מתוחכם יותר, אלא איזה מבנה מתאר את הנתונים בצורה ברורה ובטוחה.
| המשימה | בחירה טבעית | למה |
|---|---|---|
| עוברים על רשימת ציונים שטוחה | לולאה | כל הפריטים נמצאים באותה רמה ויש סדר מעבר ברור. |
| סורקים תיקיות שבתוכן תיקיות נוספות | רקורסיה | כל תיקייה היא גרסה קטנה של אותה הבעיה. |
| מזיזים דמות 20 צעדים | לולאה | מספר החזרות ידוע ואין מבנה מקונן. |
| בודקים עץ החלטות של משחק | רקורסיה | כל בחירה יכולה לפתוח בחירות משנה באותו מבנה. |
גם כשהמבנה מקונן, עומק גדול מדי עלול למלא את מחסנית הקריאות. בקוד אמיתי בודקים מהו העומק האפשרי, ולעיתים מעדיפים לולאה עם מחסנית מפורשת שאפשר לנהל ולמדוד.
שלוש שאלות לפני שמריצים שוב
אין תנאי עצירה
סימן: הפונקציה ממשיכה לקרוא לעצמה עד ש-Python עוצר אותה.
בדיקה: מסמנים על הנייר איזה קלט חייב להחזיר תשובה בלי קריאה נוספת.
הבעיה לא נעשית קטנה יותר
סימן: כל קריאה מקבלת שוב את אותה תיבה או אותו מספר.
בדיקה: בודקים שהקריאה הבאה עובדת על תיבת משנה, מספר קטן יותר או מצב קרוב יותר לסיום.
שוכחים להשתמש בערך שחזר
סימן: הקריאות מתבצעות, אבל הסכום הסופי חסר.
בדיקה: עוקבים אחרי return מלמטה למעלה ומוודאים שכל רמה מצרפת את התוצאה שלה.
לפני המקלדת: ציירו שלוש תיבות
כתבו בכל תיבה מספר מטבעות וחברו תיבה אחת בתוך אחרת. סמנו את מקרה הבסיס, רשמו את סדר הקריאות כלפי מטה ואת ערכי ה-return כלפי מעלה. רק אחר כך הריצו את הפונקציה והוסיפו תיבה ריקה, שתי תיבות אחיות ותיבה בעומק נוסף. אם התחזית והפלט תואמים, אתם לא רק משתמשים ברקורסיה — אתם שולטים בזרימה שלה.