שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2017 - רקורסיה

אדם עומד על מדרכה. בכל מהלך הוא יכול להתקדם צעד אחד לכיוון ימין או צעד אחד לכיוון שמאל. הוא צריך להגיע לנקודה מסוימת שנמצאת במרחק $n$ צעדים לכיוון ימין. אנו מעוניינים לבדוק בכמה דרכים שונות הוא יכול להגיע לנקודה זו, בעזרת $k$ צעדים בדיוק. לדוגמא, 1. אם $n=0$ ו- $k=0$, התשובה היא 1. ישנה בדיוק דרך אחת להגיע באפס צעדים למיקום הנוכחי (להישאר במקום). 2. אם $n=2$ ו- $k=4$, התשובה היא 4. ישנן ארבע דרכים שונות להגיע בארבעה צעדים לנקודה הנמצאת במרחק שני צעדים מימין למקום בו האדם נמצא, והן: א. שמאל, ימין, ימין, ימין ב. ימין, שמאל, ימין, ימין ג. ימין, ימין, שמאל, ימין ד. ימין, ימין, ימין, שמאל 3. אם $n=3$ ו- $k=4$, התשובה היא 0. אין אף דרך אפשרית להגיע בארבעה צעדים לנקודה הנמצאת במרחק שלושה צעדים מימין. עליכם לכתוב שיטה רקורסיבית המקבלת כפרמטרים שני מספרים שלמים $n$ ו- $k$ ומחזירה את מספר הדרכים האפשריות להגיע ב- $k$ צעדים לנקודה במרחק $n$ צעדים ימינה מהמקום בו האדם נמצא. אתם יכולים להניח כי הפרמטרים תקינים, וכי $k \geq 0$ וכן $n \geq 0$. שימו לב, אין צורך להחזיר את הדרכים עצמן ולא להדפיס אותן. רק להחזיר מהו מספר הדרכים. חתימת השיטה היא: ```java public static int ways (int k, int n) ``` השיטה שתכתבו צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות. אפשר להשתמש בהעמסת יתר (overloading) אין צורך לדאוג ליעילות השיטה! אל תשכחו לתעד את מה שכתבתם!

רמז: חשבו על הצעד האחרון בדרך. אם הצעד ה-$k$ היה ימינה, היכן היה צריך להיות האדם לאחר $k-1$ צעדים? ומה אם הצעד האחרון היה שמאלה?

פתרון: הפתרון לבעיה זו מבוסס על **חשיבה רקורסיבית**. הרעיון המרכזי הוא לפרק את הבעיה של מציאת מספר הדרכים ב-$k$ צעדים לבעיות קטנות יותר, של מציאת מספר הדרכים ב-$k-1$ צעדים. נחשוב על הצעד הראשון שהאדם מבצע. יש לו שתי אפשרויות: 1. ללכת צעד אחד **ימינה**. לאחר צעד זה, נותרו לו $k-1$ צעדים, והמרחק שעליו לעבור הוא $n-1$ צעדים ימינה מהנקודה החדשה. 2. ללכת צעד אחד **שמאלה**. לאחר צעד זה, נותרו לו $k-1$ צעדים, והמרחק שעליו לעבור הוא $n+1$ צעדים ימינה מהנקודה החדשה (מכיוון שהתרחק מהיעד בצעד אחד). מספר הדרכים הכולל להגיע ליעד ב-$k$ צעדים הוא סכום מספר הדרכים בכל אחד משני המקרים הללו. אם נסמן ב-$W(k,n)$ את מספר הדרכים המבוקש, נוכל להגדיר את **נוסחת הנסיגה** הבאה: $$W(k,n) = W(k-1, n-1) + W(k-1, n+1)$$ כעת, עלינו להגדיר את **תנאי העצירה** של הרקורסיה. הרקורסיה נעצרת כאשר לא נותרו יותר צעדים לביצוע, כלומר כאשר $k=0$. - אם $k=0$ וגם $n=0$: הגענו בדיוק ליעד (המרחק הנותר הוא 0) והשתמשנו בכל הצעדים. זוהי דרך חוקית אחת, ולכן הפונקציה תחזיר 1. - אם $k=0$ אבל $n \neq 0$: נגמרו לנו הצעדים, אך לא הגענו ליעד. זוהי אינה דרך חוקית, ולכן הפונקציה תחזיר 0. יש לשים לב שהפרמטר $n$ יכול לקבל ערכים שליליים במהלך הקריאות הרקורסיביות (למשל, בקריאה ל-$W(k-1, n-1)$ אם $n$ היה 0), וזה תקין. מרחק שלילי $n$ פשוט אומר שהיעד נמצא כעת $|n|$ צעדים שמאלה מהמיקום הנוכחי. להלן מימוש השיטה ב-Java, בהתאם להגדרה הרקורסיבית: ```java /** * השיטה מחשבת באופן רקורסיבי את מספר הדרכים השונות * להגיע לנקודה במרחק n צעדים ימינה, באמצעות k צעדים בדיוק. * בכל צעד ניתן לנוע ימינה או שמאלה. * * @param k מספר הצעדים שיש לבצע. * @param n מרחק היעד מהנקודה הנוכחית (חיובי - ימינה). * @return מספר הדרכים האפשריות. */ public static int ways(int k, int n) { // תנאי עצירה: לא נותרו יותר צעדים. if (k == 0) { // אם הגענו ליעד (המרחק הנותר הוא 0), מצאנו דרך אחת. if (n == 0) { return 1; } // אחרת, לא הגענו ליעד, ולכן זו לא דרך חוקית. return 0; } // הצעד הרקורסיבי: // נסכום את מספר הדרכים עבור שתי האפשרויות לצעד הבא. // אפשרות 1: צעד ימינה. נותרים k-1 צעדים ומרחק n-1. int waysAfterRightStep = ways(k - 1, n - 1); // אפשרות 2: צעד שמאלה. נותרים k-1 צעדים ומרחק n+1. int waysAfterLeftStep = ways(k - 1, n + 1); return waysAfterRightStep + waysAfterLeftStep; } ``` הפתרון עונה על כל דרישות השאלה: הוא רקורסיבי טהור ואינו משתמש בלולאות. הוא מטפל נכון במקרים השונים ומגיע לתנאי עצירה מוגדרים היטב.