המרת תוכנית רגילה לרקורסיבית JAVA

[iem]

כאשר נתונה בידי (כתבתי), תוכנית רגילה ב- JAVA, מהי הדרך הטובה ביותר ע"מ להופכה לרקורסיבית ?

האם יש כמה כללי יסוד שבאמצעותם אני אהפוך ביתר קלות את התוכנית לרקורסיבית ?

תודה

[erez20]

הנה כמה טיפים ממה שאני זוכר:

אין משמעות ללהפוך "את התוכנית" לרקורסיבית, אתה יכול להמיר לולאה לרקורסיה, קשה לי להאמין שתרצה שכל התוכנה תרוץ ברקורסיה

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

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

[iem]

לא ממש הבנתי...

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

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

צריך לעשות בעיקרון אחרי שכתבנו את תנאי העצירה

[שניצל]

השאלה היא למה בכלל אתה רוצה לעשות את זה?

לרוב אין סיבה לכתוב באופן רקורסיבי. פונקציה רקורסיבית נועדה למקרה שבו לולאות פשוטות לא מספיקות (כמו במקרה של מעבר על עץ).

[iem]

כי יש לי בקרוב מבחן ששאלה אחת תהיה כתיבת תוכנית רקורסיבית...

אני יודע שהשאלה צריכה להיות די קשה, אבל לא ידרשו ממני לכתוב תוכנית שקשורה בעצים...

איזה שאלות באמת יכולים לתת ? והאם יש סוג של אלגוריתם באופן כללי אפילו שמדבר על הפיכת תוכנית לרקורסיבית

[שניצל]

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

תחשוב על זה ככה - לולאה רגילה (while או for) בנויה משלושה מרכיבים - אתחול, תנאי המשך/עצירה וקידום.

האתחול הוא בעצם הקריאה הראשונית שלך לפונקציה הרקורסיבית.

תנאי העצירה של הלולאה הוא תנאי העצירה של הרקורסיה (שים לב שב-for/while הלולאה ממשיכה כל עוד התנאי מתקיים, ברקורסיה אתה צריך לצאת מהפונקציה כשהתנאי לא מתקיים).

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

קח לדוגמה את הלולאה הזו:

for (int i = 0 ; i < N ; i++)
 System.out.println(i);

הפונקציה הרקורסיבית השקולה היא:

void f(int i)
{
 if (i >= N)
  return;
 System.out.println(i);
 f(i+1);
}

והקריאה הראשונית לה היא באמצעות (f(0.

יש?

[exercise]

בהרבה שפות הקומפיילר יהפוך קוד רקורסיבי כזה (מה שנקרא tail recursion) חזרה לקוד של לולאה מאחורי הקלעים (כדי לא לפוצץ את ה call stack שלא לצורך למשל).

[iem]

שניצל: סבבה הבנתי... אבל כאשר מדובר בתוכנית רצינית של ממש איך אני "בונה" את השיטה הרקורסיבית שלי ?

[DXT]

זה תלוי מה אתה רוצה לממש.

בעיקרון רקורסיה עובדת עפ"י שני כללים:

1. כלל העצירה של הרקורסיה - באיזה מצב הפונקציה הרקורסיבית תחזיר ערך ממשי קבוע (למשל בעץ כאשר הגענו לעלה או ל- NULL).

2. מה הקריאה (או הקריאות) הרקורסיבית של הפונקציה? פה בא לידי ביטוי הרעיון שמאחורי הפתרון לתכנית ולרקורסיה עצמה, אתה צריך למצוא את ה"חוק" של הפתרון של הבעיה.

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