רקורסיה בג'אווה

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

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

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

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

דוגמה קלאסית לשימוש בפונקציה רקורסיבית היא חישוב הפקטוריאלי של מספר. למקרה ששכחת, הרשו לי להזכיר לכם: הפקטוריאלי של מספר שלם חיובי N(מסומן כ-N!) הוא מכפלה של מספרים מ- 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. אגב, הפקטוריאלי של אפס בהגדרה שווה ל-1. אז את הפקטוראלי ניתן למצוא לכל מספר שלם ואפס חיובי (בלשון המתמטיקה - לקבוצת המספרים השלמים הלא שליליים או לקבוצת המספרים הטבעיים ו- אֶפֶס). אני חושב שאתה מבין שאתה יכול לתכנת פקטורי באמצעות לולאות. למעשה, הנה שיטה לא רקורסיבית לפתרון בעיה זו:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

נוסיף בדיקה שהמספר חיובי ומספר שלם, וסימון נפרד לאפס.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

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

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

בואו נסתכל על תוצאות הפלט של השיחות:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

נקבל את הערכים הצפויים:

1
1
2
6
24
120
720

בואו נוסיף פלט יפה ונחשב את הפקטוריאלי למספר גדול יותר:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

אנו מקבלים: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! במקרה זה, השימוש בפונקציה רקורסיבית מוצדק ובטוח. הגדרנו בבירור את התנאי ליציאה מהגוש הרקורסי, ואנו בטוחים שהוא בר השגה: נזין מספר שלם לא שלילי, אם המספר שווה לאפס או לאחד, נחזיר את התוצאה, אם המספר גדול יותר , נכפיל את התוצאה בפונקציה של המספר n-1. שימוש בפקטורי של שלוש כדוגמה:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

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

if (n == 1 || n == 0) {
    return result;
}

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

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

והכל יהיה בסדר. מה היתרון של שיטה אחת על פני אחרת? לא נראה שיש הבדל גדול, אבל למעשה, להרבה שיחות רקורסיביות תהיה השפעה שלילית על הביצועים וצריכת הזיכרון: מחסנית השיחות היא משאב כמעט בלתי נשלט ובתנאים שונים לקריאה לאותה פונקציה רקורסיבית, אנו עשויים לקבל או לא לקבל בעיות הקשורות למשאב זה. כמעט כל הבעיות שנפתרות באמצעות איטרציות (מחזורים כמו for-each) ניתנות לפתרון גם רקורסיבית. היתרון של הרקורסיה הוא קריאה וקלות כתיבה, דיברנו על החסרונות לעיל: ההזדמנות "לירות לעצמך ברגל" אינה אשליה. אתה צריך להיות זהיר עוד יותר כאשר אתה משתמש במה שנקרא "רקורסיה מורכבת": פונקציה A()תקרא לפונקציה B()שקוראת לפונקציה A(). פתרון בעיות כאלה דורש הבנה מלאה של אופן הפעולה של הרקורסיה. דוגמה למשימה כזו: חישוב הערך של x^n/(n!). הפקטורי, כפי שדיברנו לעיל, מוגדר על קבוצת המספרים השלמים הלא שליליים. לבסוף, אני אתן את קוד הפתרון. רקורסיה מורכבת תהיה מורכבת משתי שיטות:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

כדי להיכנס לרקורסיה, משתמשים בשיטה calculate, שקוראת למתודה power, שבתורה קוראת למתודה calculate. הגדרנו את בסיס הרקורסיה בשיטת הכוח:

if (n == 1) return x;

שלב הרקורסיה מוגדר גם שם:

return x * calculate(x, n - 1);

נותר להוסיף בדיקה לתקפות נתוני הקלט:

• כל מספר מלבד אפס שווה בחזקת אפס 1. אם n = 0, אז n! = 1. צריך להחזיר אותו 1.
• אפס בכל חזקה שווה לאפס.
• לא נשקול אי ודאות סוג 0^0ונקבל נתוני קלט כאלה כלא חוקיים.

עם כל הבדיקות, השיטות ייראו כך:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

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

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}