बाहेर पडण्याच्या अटी. स्टॅकओव्हरफ्लो एरर

एक्झिट अटीशिवाय रिकर्सिव कोडचे उदाहरण

चला पुन्हा पुन्हा येणार्‍या समस्येकडे पाहू. उदाहरण म्हणून, फिबोनाची संख्या मोजण्याचा विचार करा. प्रत्येकाला आठवत असेल की फिबोनाची क्रम हा एक संख्यात्मक क्रम आहे ज्यामध्ये पहिल्या दोन संख्या 0 आणि 1 आहेत आणि त्यानंतरची प्रत्येक संख्या मागील दोन संख्यांच्या बेरजेइतकी आहे.

या संख्यांची गणना आणि प्रदर्शित करण्यासाठी कोड लिहू:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}

रिकर्सिव प्रिंटफिबोनाची पद्धतीचा पहिला कॉल करण्यापूर्वी , अनुक्रमाचे पहिले दोन अंक मुद्रित करा: शून्य आणि एक. आम्हाला हे करणे आवश्यक आहे कारण रिकर्सिव्ह पद्धत केवळ इनपुट पॅरामीटर्सची बेरीज दाखवते, स्वतः पॅरामीटर्स दाखवत नाही.

कोड ठीक दिसतो: आम्हाला दोन संख्या मिळतात, त्यांची बेरीज मोजली जाते, ती कन्सोलवर मुद्रित केली जाते आणि प्रिंटफिबोनाची पद्धत पुन्हा आवर्ती कॉल करते. आम्ही मागील संख्या (मागील) आणि वर्तमान संख्या (वर्तमान) वितर्क म्हणून पास करतो.

वास्तविक, कोडमध्ये दोन त्रुटी आहेत. तुम्ही कोड चालवल्यास ते पाहू शकता.

पहिली त्रुटी लांब प्रकार ओव्हरफ्लो आहे. आमच्या क्रमातील 104 वी संख्या ऋणात्मक आहे, हे दर्शविते की लांब प्रकार ओव्हरफ्लो झाला आहे.

दुसरी चूक वेगळी आहे. अंदाजे 12,000 संख्या मोजल्यानंतर, आम्हाला मिळते:

Java मध्ये मेथड कॉल स्टॅक काय आहे हे आठवण्यासाठी ही योग्य वेळ आहे. Java मशीन सर्व फंक्शन कॉल्सचे रेकॉर्ड ठेवते. हे करण्यासाठी, तो स्टॅक नावाचा एक विशेष प्रकारचा संग्रह वापरतो. जेव्हा एक फंक्शन दुसर्‍याला कॉल करते, तेव्हा Java मशीन स्टॅकवर नवीन StackTraceElement ढकलते. फंक्शन संपल्यावर, हा घटक स्टॅकमधून काढला जातो. त्यानुसार, स्टॅक नेहमी फंक्शन कॉल स्टॅकच्या सद्य स्थितीबद्दल अद्ययावत माहिती संग्रहित करतो. StackTraceElement साठीचे दस्तऐवज म्हणते की "एखादे स्टॅक ओव्हरफ्लो होते तेव्हा फेकले जाते कारण एखादे अॅप्लिकेशन खूप खोलवर पुनरावृत्ती होते." मेथड कॉल स्टॅक संचयित करण्यासाठी चालू असलेल्या JVM मध्ये मेमरीचे एक विशेष क्षेत्र असते. या मेमरी क्षेत्राचा आकार OS आणि JVM सेटिंग्जवर अवलंबून असतो. मेथड कॉल स्टॅक स्वतः व्यतिरिक्त, प्रिमिटिव्ह व्हेरिएबल्स (पद्धतीच्या पॅरामीटर्सची विशिष्ट मूल्ये) आणि संदर्भ व्हेरिएबल्सचे पत्ते ("ढीग" नावाच्या मेमरी क्षेत्रात) या विशेष मेमरी क्षेत्रात संग्रहित केले जातात. कॉल स्टॅकमध्ये प्रवेश LIFO तत्त्वानुसार होतो.

निर्गमन स्थितीसह दुरुस्त केलेले उदाहरण

चला कोडमधील दुसरी समस्या सोडवून सुरुवात करूया.

चला समस्या सोडवण्याचा प्रयत्न करूया: जर स्टॅक खूप लहान असेल, तर चला ते मोठे करूया. हे करण्यासाठी, "-Xss" ध्वजासह JVM सुरू करा आणि स्टॅकसाठी किती मेमरी वाटप करायची ते निर्दिष्ट करा. चला 5 मेगाबाइट्स वाटप करण्याचा प्रयत्न करूया. IDEA मध्ये हे असे दिसेल:

आम्ही आउटपुटची लांबी वाढविण्यात व्यवस्थापित केले. आता 12,000 आकड्यांपुरते मर्यादित न राहता अनुक्रमाच्या 49,000 पेक्षा जास्त संख्यांची गणना करू शकते. पण कधीतरी, आम्हाला अजूनही StackOverflowError मिळते .

तुम्ही स्टॅकचा आकार वाढवण्याचा प्रयत्न करू शकता, परंतु ते मूलभूत समस्येचे निराकरण करत नाही. तर, तर्कशास्त्रातील समस्या पाहू. पुनरावृत्ती थांबते तेव्हा एक बिंदू असणे आवश्यक आहे. दुस-या शब्दात, अशी काही अट असली पाहिजे जी रिकर्सिव्ह पद्धत कधी कॉल केली जाणार नाही हे ठरवते, ज्यामुळे कॉल स्टॅक अनवाइंड होऊ शकतो. अशा स्थितीची व्याख्या करण्यासाठी, आमचे उद्दिष्ट स्पष्ट करूया: फिबोनाची मालिका प्रदर्शित करा जोपर्यंत तिची संख्या पूर्णांकापेक्षा कमी आहे. MAX_VALUE .

चला एक नवीन printFibonacciWithCondition पद्धत लिहू जी ही स्थिती विचारात घेईल. आणि आम्ही नवीन सुधारित पद्धतीला मुख्य पद्धतीमध्ये कॉल करू.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}

कोड चालवल्यानंतर, आऊटपुट 1836311903 या क्रमांकाने संपत असल्याचे आपण पाहतो. याच्या आधीची संख्या 1134903170 आहे. या संख्यांची बेरीज 2_971_215_073 आहे, जी खरंच Integer.MAX_VALUE (2_147_483_64) पेक्षा मोठी आहे .

या बदलाने लांब ओव्हरफ्लो बगचे स्वयंचलितपणे निराकरण केले. तुम्हाला अधिक मालिकांची गणना करायची असल्यास, तुम्हाला BigInteger सारखे इतर डेटा प्रकार वापरावे लागतील .

आवर्ती कूळ आणि unwinding

आपला कोड कसा कार्यान्वित केला जातो याचे चरण-दर-चरण विश्लेषण करूया. हे करण्यासाठी, आम्ही प्रतिध्वनी पद्धत जोडू आणि printFibonacciWithCondition पद्धतीच्या रिकर्सिव कॉलच्या आधी आणि नंतर कॉल करू .

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}

प्रोग्राम आम्हाला हे आउटपुट देतो:

येथे काय घडत आहे याचे एक व्हिज्युअलायझेशन आहे.

चला ते पुन्हा म्हणूया: printFibonacciWithCondition पद्धत म्हणतात. हे वर्तमान संख्येची गणना करते. जर ते आमच्यासाठी अनुकूल असेल, तर आम्ही ते प्रदर्शित करतो आणि नवीन युक्तिवादांसह पुन्हा प्रिंटफिबोनाचीविथ कंडिशन पद्धत कॉल करतो.

जोपर्यंत रिकर्सिव्ह पद्धत म्हटले जात आहे, त्याला "रिकर्सिव्ह डिसेंट" असे म्हणतात. जेव्हा रिकर्सिव टर्मिनेट होते आणि मेथड कॉल परत येतो, तेव्हा आम्ही म्हणतो की कॉल स्टॅक "अनवाइंडिंग" आहे.

पुनरावृत्ती हा प्रोग्रामिंगमधील एक मनोरंजक विषय आहे. सामग्रीवर चांगले हँडल मिळविण्यासाठी, आमचे कार्य थोडेसे बदलूया. नवीन कार्य म्हणजे उतरत्या क्रमाने, फिबोनाची मालिकेतील सर्व संख्या आउटपुट करणे जे Integer.MAX_VALUE पेक्षा जास्त नाही . आम्ही या कार्यासाठी आवश्यक असलेले सर्व कोड आधीच लिहिले आहेत. सध्याचा क्रमांक प्रदर्शित करण्याचा आणि रिकर्सिव पद्धतीवर कॉल करण्याचा क्रम स्वॅप करणे बाकी आहे. म्हणजेच, पहिल्या उदाहरणात, गणना केलेली संख्या "उतला" दरम्यान प्रदर्शित केली गेली होती, परंतु आता आपल्याला "अगदी तळाशी उतरणे" आणि नंतर "परत जाताना" क्रमांक प्रदर्शित करणे आवश्यक आहे. आणि अर्थातच, मुख्य पद्धतीमध्ये, आम्ही अनुक्रमातील दोन आरंभिक संख्या (शून्य आणि एक) स्वॅप करतो आणि त्यांना प्रदर्शित केल्यानंतर आम्ही रिकर्सिव्ह पद्धत कॉल करतो. वाचनीयतेसाठी,पद्धत

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}

आउटपुट असेल: