נושא: פעולות רקורסיביות

נשלח בתאריך: 17 October 2008 בשעה 16:26 | IP רשוּם

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

 ישנה טכניקה מקלה בשלושת המרכיבים העיקריים ברקורסיה -
1.תנאי עצירה.
2.קריאה רקורסיבית.
3.קשר פונקציונאלי.
שים לב - השלבים לא חייבים לבוא אחד אחרי השני בצורה שהם רשומים פה. אבל הם חייבים להתקיים.

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

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

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

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

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

פתרון פסאודו-קוד -
מצא_איבר_מקס(עץ)
1. אם לעץ אין בנים החזר את תוכן השורש.
2. שים ב-max מינוס אינסוף.
3. בעבור כל תת עץ בצע:
  3.1 מצא_איבר_מקס(תת עץ) = x
  3.2 אם x > max
    3.2.1 max = x
4. החזר את max.