בעיות מתקדמות ברקורסיה

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

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

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

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

לפני שנדון בבעיות עצמן, נדבר על שיטות שונות לפתרון בעיות במדעי המחשב.

Divide and Conquer

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

די קשה להסביר את האלגוריתם הזה מבלי לציין דוגמא.

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

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

אני חושב שההסרטון הזה מסביר בצורה ממצה את העניין.

Backtracking

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

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

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

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

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

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

הסרטון שמסביר זאת בצורה הטובה ביותר לדעתי, הוא זה (אפשר לדלג על ההסבר של הקוד)

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

פיבונאצ'י

חישוב מספר פיבונאצ'י הוא דוגמא בסיסית לשימוש ב-Divide and Conquer.

כדי לחשב מספר n בסדרה צריך לחשב את הסכום של שתי הספרות שלפניו וכן הלאה עד לשני המספרים הראשונים בסדרה.

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

- כלל עצירה: המספר היחידי אותו אנו יודעים מראש הוא הראשון והשני שהם שווים ל-1.

- הערך המוחזר יהיה ערך סכום של שתי הקריאות לפונקציה עם שני המספרים שקדמו ל-n.

- הקשר בין שתי הקריאות יהיה חיבור.

חישוב עצרת

חישוב עצרת של מספר היא דוגמא נוספת.

כדי לחשב עצרת של מספר אנחנו נחשב את המכפלה של המספר בעצרת של המספר שלפניו, עד למספר הראשון שחישוב העצרת שלו הוא נתון: עצרת של 1 היא 1.

חיפוש בינארי

חיפוש בינארי הוא דוגמא נוספת, פשוטה יחסית לשימוש ב-Divide and Conquer. 

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

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

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

כלל עצירה: אם המספר נמצא, יוחזר האינדקס שלו, או שהחיפוש הסתיים ויוחזר 1-

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

סיכום

סקרנו את הרעיון הבסיסי של Backtracking ו-Divide And Conquer.

בהמשך, נראה איך אפשר לשכלל את הרעיונות האלה כדי לפתור בעיות סבוכות.