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

סדרת פיבונאצ'י היא הסדרה הבאה: $1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ שני האיברים הראשונים (המודגשים) בסדרה, שהם האיבר ה-0 והאיבר ה-1, שווים לאחד. החל מהאיבר ה-2 כל איבר שווה לסכום שני האיברים הקודמים לו בסדרה. נסמן את האיבר ה-n בסדרה ב- `fib(n)`. **סעיף א - משימת חימום (2 נקודות)** השלימו בדף התשובות את הגדרת הפונקציה הרקורסיבית ```c public static int fib(int n) ``` המקבלת מספר אי-שלילי n ומחזירה את האיבר ה-n בסדרה. יש להניח שהקלט תקין. כלומר $0 \leq n$. **סעיף ב (10 נקודות)** השלימו בדף התשובות את הגדרת הפונקציה הרקורסיבית ```c public static int fibCount1(int n, int k) ``` המקבלת שני מספרים n ו-k כך ש- $0 \leq k \leq n$ ומחזירה את מספר הקריאות המתבצעות ל- `fib(k)` במהלך החישוב של הקריאה לפונקציה הרקורסיבית `fib(n)` שכתבתם בסעיף א'. למשל, במהלך החישוב של הקריאה לפונקציה `fib(5)`, יש בדיוק קריאה אחת לפונקציה `fib(5)` ובדיוק שלוש קריאות לפונקציה `fib(2)`. דוגמה: הפלט של קטע הקוד הבא: ```c System.out.println(fibCount1(5,5)); System.out.println(fibCount1(5,2)); System.out.println(fibCount1(6,4)); System.out.println(fibCount1(1,0)); System.out.println(fibCount1(0,0)); ``` הוא ``` 1 3 2 0 1 ``` יש להניח שהקלט תקין. כלומר $0 \leq k \leq n$. **סעיף ג (13 נקודות)** הפונקציה הרקורסיבית שכתבתם בסעיף ב', כמו הפונקציה שכתבתם בסעיף א', מבצעת חישובים חוזרים. השלימו בדף התשובות את הגדרת הפונקציה ```c public static int fibCount2(int n, int k) ``` המקבלת שני מספרים n ו-k כך ש- $0 \leq k \leq n$ ומחזירה את מספר הקריאות המתבצעות ל- `fib(k)` במהלך החישוב של הקריאה לפונקציה הרקורסיבית `fib(n)` שכתבתם בסעיף א', באופן ש- `fibCount2` אינה מבצעת חישובים מיותרים. הדרכת חובה: יש לכתוב פונקציית עזר רקורסיבית אחת. יש להניח שהקלט תקין. כלומר $0 \leq k \leq n$.

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

פתרון: ### סעיף א המימוש הרקורסיבי של פונקציית פיבונאצ'י לפי ההגדרה הנתונה: - **תנאי עצירה:** עבור `n=0` או `n=1`, הפונקציה מחזירה 1. - **הצעד הרקורסיבי:** עבור `n > 1`, הפונקציה קוראת לעצמה עבור `n-1` ו-`n-2` ומחזירה את סכום התוצאות. ```java public static int fib(int n) { if (n == 0 || n == 1) { return 1; } return fib(n - 1) + fib(n - 2); } ``` ### סעיף ב המטרה היא לספור את מספר הקריאות ל-`fib(k)` במהלך חישוב `fib(n)`. ננתח את עץ הרקורסיה של `fib(n)`: - אם `n == k`, זוהי הקריאה הראשית עצמה, ולכן יש **קריאה אחת**. - אם `n < k`, `fib(k)` לא יכולה להיקרא, כי ערך הפרמטר בקריאות הרקורסיביות רק יורד. לכן יש **אפס קריאות**. (מקרה זה אינו אפשרי לפי הגדרת השאלה $0 \le k \le n$). - אם `n > k`: - אם `n` הוא 0 או 1, `fib(n)` הוא **מקרה בסיס** ואינו מבצע קריאות רקורסיביות נוספות. לכן, מספר הקריאות ל-`fib(k)` הוא **אפס**. - אם `n > 1`, `fib(n)` קורא ל-`fib(n-1)` ול-`fib(n-2)`. מספר הקריאות הכולל ל-`fib(k)` הוא סכום הקריאות שנוצרו משני ענפי החישוב הללו. זה מוביל להגדרה רקורסיבית עבור `fibCount1(n, k)`: ```java public static int fibCount1(int n, int k) { if (n == k) { return 1; } // המקרה n > k if (n <= 1) { // n=1, k=0. fib(1) הוא מקרה בסיס, אין קריאות נוספות. return 0; } // n > 1, n > k. נסכום את הקריאות משני התתי-עצים. return fibCount1(n - 1, k) + fibCount1(n - 2, k); } ``` ### סעיף ג הפונקציה `fibCount1` סובלת מבעיית **חישובים חוזרים** (overlapping subproblems), בדומה לפונקציה `fib` המקורית. כדי לייעל אותה, נשתמש בטכניקת **תכנון דינמי** עם **ממואיזציה (memoization)**. נכתוב פונקציית עזר רקורסיבית שתקבל, בנוסף ל-`n` ו-`k`, גם מערך המשמש כזכרון מטמון (`memo`) לאחסון תוצאות שכבר חושבו. פונקציית העזר `fibCount2Helper` תפעל כך: 1. לפני כל חישוב, היא תבדוק במערך `memo` אם התוצאה עבור `(n, k)` כבר קיימת. אם כן, היא תחזיר אותה ישירות. 2. אם התוצאה אינה קיימת, היא תחשב אותה באמצעות אותה לוגיקה רקורסיבית מסעיף ב'. 3. לאחר החישוב, היא תאחסן את התוצאה החדשה במערך `memo` לפני שתחזיר אותה. הפונקציה הציבורית `fibCount2` תיצור ותאתחל את מערך המטמון ותפעיל את פונקציית העזר. ```java public static int fibCount2(int n, int k) { // מערך דו-ממדי לאחסון תוצאות שכבר חושבו. // مقدار -1 מציין שהערך עדיין לא חושב. int[][] memo = new int[n + 1][k + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { memo[i][j] = -1; } } return fibCount2Helper(n, k, memo); } private static int fibCount2Helper(int n, int k, int[][] memo) { // בדיקה אם התוצאה כבר קיימת בזיכרון המטמון if (memo[n][k] != -1) { return memo[n][k]; } int result; // אותה לוגיקה רקורסיבית מסעיף ב' if (n == k) { result = 1; } else if (n <= 1) { // n > k result = 0; } else { // n > 1, n > k result = fibCount2Helper(n - 1, k, memo) + fibCount2Helper(n - 2, k, memo); } // שמירת התוצאה בזיכרון המטמון לפני החזרתה memo[n][k] = result; return result; } ```