פרק 4: רקורסיה

4.1 הגדרה רקורסיבית

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

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

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

wizard(X) :- known_wizard(X).

wizard(X) :-
parents(Y,Z,X),
wizard(Y),
wizard(Z).

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

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

בשלב זה כדאי להדגיש את חשיבותו של תנאי העצירה.
תלמיד כתב חוק רקורסיבי:

wizard :- wizard.

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

?- wizard.

מהי תגובתו של פרולוג?

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

מסקנה: חוקים רקורסיביים עם מטרות זהות משני צידי החוק הם מסוכנים, ותנאי עצירה – יצילנו מצרה!

חד גדיא: תרגיל קצר ברקורסיה

מתוך הגדה של פסח:

"... ואתא שונרא ואכלה לגדיא
ואתא כלבא ונשך לשונרא
ואתא חוטרא והכה לכלבא
ואתא נורא ושרך לחוטרא
ואתא מיא וכבה לנורא
ואתא תורא ושתה למיא
ואתא השוחט ושחט לתורא ..."

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

השתמשו במתאר came_to(X,Y) שמשמעו X בא (= אתא) אל Y כדי לתאר את הקשרים הישירים ) לדוגמא, עובדה אחת בתכנית תהיה came_to(shunra, gadia). כתבו הגדרה רקורסיבית שתוכל לגלות גם את הקשרים העקיפים.

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

?- xad_gadia(X1, X2).

תשובתו של פרולוג תהיה כדלקמן.

מבוא