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

נתונה המחלקה DataQueue הבאה, המממשת תור. איברי התור הם אובייקטים מהמחלקה DataNode, המכילים ערכים מטיפוס int: ```java public class DataQueue { private DataNode _rear, _front; public DataQueue() { ... } // Constructs an empty queue public boolean empty() { ... } // Returns true iff the queue is empty public void enqueue(DataNode newItem) { ... } // Adds the new item to the end of the queue public DataNode retrieve() { ... } // Removes oldest item from the queue and returns it. // Returns null if queue is empty. } ``` בנוסף, נתונות שתי השיטות הסטטיות הבאות: ```java public static boolean mystery(DataQueue q1, DataQueue q2) { if (q1.empty() && q2.empty()) return true; if (q1.empty() || q2.empty()) return false; if (!(q1.retrieve().equals(q2.retrieve()))) return false; return mystery(q1, q2); } public static void secret(DataQueue q) { if (!q.empty()) { DataNode node = q.retrieve(); secret(q); q.enqueue(node); } } ``` **סעיף ב (5 נקודות)** מה מבצעת השיטה secret כאשר היא מקבלת כפרמטר תור q? כתבו בקצרה מה מבצעת השיטה ולא כיצד היא מבצעת זאת.

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

פתרון: השיטה secret מבצעת **היפוך** (reverse) של תור q. היא מוציאה את האיבר הראשון, קוראת רקורסיבית על שאר התור (שהופך), ואז מכניסה את האיבר שהוציאה לסוף התור. לדוגמה, אם התור הוא [1, 2, 3] (1 בראש), לאחר secret הוא יהיה [3, 2, 1].