כיצד ליצור רקורסיה בג'אווה - פונקציה רקורסיבית

רקורסיה הוא תהליך ההגדרה של משהו במונחים שלעצמה. בהתייחס לתכנות Java, רקורסיה היא התכונה המאפשרת לשיטה לקרוא לעצמה. שיטה שקוראת לעצמה אומרים שהיא רקורסיבית וג'אווה תומכת ברקורסיה.

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

לכל רקורסיה צריך להיות המאפיינים הבאים:

1. מקרה בסיס פשוט שעליו יש לנו פיתרון וערך החזר.
2. דרך לקרב את הבעיה שלנו למקרה הבסיס. כלומר דרך לחתוך חלק מהבעיה כדי לקבל בעיה מעט יותר פשוטה.
3. שיחה רקורסיבית שמעבירה את הבעיה הפשוטה יותר חזרה לשיטה.

יתרונות

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

חסרונות

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

לדוגמה:

int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}

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

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

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

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

בעבר ראית את תוכנית ה- Java שלנו לחישוב מפעל של מספר שלם.

הדרך הנכונה לעשות מפעל רקורסיבי לזנב היא זו:

int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}

שימו לב שבחזרה לשיחהfactorial_i (currentNumber - 1, סכום * currentNumber); שני הפרמטרים ניתנים לפיתרון מיידי. אנו יכולים לחשב מהו כל פרמטר בלי לחכות לשיחת פונקציה רקורסיבית. זה לא המקרה בגירסה הקודמת של מפעל. התייעלות זו מאפשרת למהדר למזער את השימוש בערימה כמוסבר לעיל.

אתה יכול גם לקחת את המספר מהמשתמש כטיעון שורת פקודה.

תוכנית רקורסיה של ג'אווה

class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}

תפוקה

הסבר על קוד Java ופלט

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

כדי להבין טוב יותר כיצד עובדה () השיטה עובדת, בואו נעבור דוגמא קצרה. כשמחשבים את המפעל של 3, השיחה הראשונה אל עובדה () תביא לשיחה שנייה עם טיעון של 2. כניעה זו תגרום עובדה () להיקרא פעם שלישית עם טיעון של 2. שיחה זו תחזור 1, אשר נקראת אז פעם שלישית עם טיעון של 1. קריאה זו תחזור 1, שאז מוכפלת על ידי 2 (הערך של n בפתיחה השנייה). תוצאה זו (שהיא 2) מוחזרת לאחר מכן לכניסת המקור של עובדה () ולהכפיל ב -3 (הערך המקורי של n). זה מניב את התשובה, 6. ייתכן שתמצא את זה מעניין להכניס println () הצהרות לתוך עובדה () אשר יראה באיזו רמה כל קריאה היא ומה התשובות הביניים.

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

בשלב הבא נלמד כיצד להתמודד מערך בג'אווה.

עיין במדריכי הלימוד וההנחיות המוחלטות לתכנות ג'אווה כאן.