बाहर निकलने की शर्तें। स्टैक ओवरफ्लो एरर

बाहर निकलने की स्थिति के बिना पुनरावर्ती कोड का उदाहरण

आइए पुनरावर्ती समस्या पर एक और नज़र डालें। एक उदाहरण के रूप में, फाइबोनैचि संख्याओं की गणना करने पर विचार करें। सभी को याद होगा कि फाइबोनैचि अनुक्रम एक संख्यात्मक अनुक्रम है जिसमें पहली दो संख्याएँ 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वां अंक ऋणात्मक है, जो दर्शाता है कि long प्रकार अतिप्रवाहित है।

दूसरी त्रुटि अलग है। लगभग 12,000 संख्याओं की गणना करने के बाद, हम पाते हैं:

जावा में मेथड कॉल स्टैक क्या है, इसे याद करने का यह सही समय है। जावा मशीन सभी फंक्शन कॉल्स का रिकॉर्ड रखती है। ऐसा करने के लिए, यह एक विशेष प्रकार के संग्रह का उपयोग करता है जिसे स्टैक कहा जाता है। जब एक फ़ंक्शन दूसरे को कॉल करता है, तो जावा मशीन स्टैक पर एक नया StackTraceElement धकेलती है। जब फ़ंक्शन समाप्त होता है, तो यह तत्व स्टैक से हटा दिया जाता है। तदनुसार, स्टैक हमेशा फ़ंक्शन कॉल स्टैक की वर्तमान स्थिति के बारे में अद्यतित जानकारी संग्रहीत करता है। StackTraceElement के लिए प्रलेखन कहता है कि यह "फेंक दिया जाता है जब एक स्टैक ओवरफ़्लो होता है क्योंकि एक एप्लिकेशन बहुत गहराई से पुनरावर्तन करता है।" चल रहे JVM में मेथड कॉल स्टैक को स्टोर करने के लिए मेमोरी का एक विशेष क्षेत्र होता है। इस मेमोरी क्षेत्र का आकार OS और JVM सेटिंग्स पर निर्भर करता है। मेथड कॉल स्टैक के अलावा, आदिम चर (विधि मापदंडों के विशिष्ट मान) और संदर्भ चर के पते ("हीप" नामक मेमोरी क्षेत्र में) इस विशेष मेमोरी क्षेत्र में संग्रहीत हैं। कॉल स्टैक तक पहुंच LIFO सिद्धांत का पालन करती है।

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

आइए कोड में दूसरी समस्या को ठीक करके प्रारंभ करें।

आइए समस्या को सीधे हल करने का प्रयास करें: यदि स्टैक बहुत छोटा है, तो आइए इसे बड़ा करें। ऐसा करने के लिए, JVM को "-Xss" फ़्लैग से प्रारंभ करें और निर्दिष्ट करें कि स्टैक के लिए कितनी मेमोरी आवंटित की जानी है। आइए 5 मेगाबाइट आवंटित करने का प्रयास करें। आईडिया में यह ऐसा दिखेगा:

हम आउटपुट की लंबाई बढ़ाने में कामयाब रहे। अब लगभग 12,000 संख्याओं तक सीमित होने के बजाय अनुक्रम की 49,000 से अधिक संख्याओं की गणना कर सकते हैं। लेकिन किसी बिंदु पर, हमें अभी भी StackOverflowError मिलता है ।

आप ढेर के आकार को बढ़ाने की कोशिश कर सकते हैं, लेकिन वह मूलभूत समस्या को ठीक नहीं करता है। तो चलिए तर्क में एक समस्या की तलाश करते हैं। एक बिंदु होना चाहिए जब रिकर्सन बंद हो जाए। दूसरे शब्दों में, कुछ शर्त होनी चाहिए जो यह निर्धारित करती है कि पुनरावर्ती विधि को कब नहीं बुलाया जाएगा, जिससे कॉल स्टैक को खोलना होगा। ऐसी स्थिति को परिभाषित करने के लिए, आइए हम अपना उद्देश्य स्पष्ट करें: फिबोनैकी श्रृंखला को तब तक प्रदर्शित करें जब तक इसकी संख्या Integer.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_647) से अधिक है ।

यह परिवर्तन स्वचालित रूप से लंबे अतिप्रवाह बग को ठीक करता है। यदि आपको अधिक श्रृंखला की गणना करने की आवश्यकता है, तो आपको BigInteger जैसे अन्य डेटा प्रकारों का उपयोग करने की आवश्यकता होगी ।

पुनरावर्ती वंश और खोलना

आइए चरण दर चरण विश्लेषण करें कि हमारा कोड कैसे निष्पादित होता है। ऐसा करने के लिए, हम एक इको मेथड जोड़ेंगे और इसे 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 विधि को कॉल किया जाता है। यह वर्तमान संख्या की गणना करता है। यदि यह हमें सूट करता है, तो हम इसे प्रदर्शित करते हैं और फिर से नए तर्कों के साथ 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);
    }
}

आउटपुट होगा: