నిష్క్రమణ పరిస్థితులు. స్టాక్‌ఓవర్‌ఫ్లో ఎర్రర్

నిష్క్రమణ పరిస్థితి లేకుండా పునరావృత కోడ్ యొక్క ఉదాహరణ

పునరావృత సమస్య గురించి మరొకసారి చూద్దాం. ఉదాహరణగా, ఫైబొనాక్సీ సంఖ్యలను లెక్కించడాన్ని పరిగణించండి. ఫిబొనాక్సీ సీక్వెన్స్ అనేది మొదటి రెండు సంఖ్యలు 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);
    }
}
    

పునరావృత ప్రింట్‌ఫైబొనాక్సీ పద్ధతి యొక్క మొదటి కాల్‌కు ముందు , క్రమం యొక్క మొదటి రెండు సంఖ్యలను ముద్రించండి: సున్నా మరియు ఒకటి. రికర్సివ్ పద్ధతి ఇన్‌పుట్ పారామితుల మొత్తాన్ని మాత్రమే ప్రదర్శిస్తుంది, పారామితులు కాకుండా మనం దీన్ని చేయాలి.

కోడ్ బాగానే ఉంది: మేము రెండు సంఖ్యలను పొందుతాము, వాటి మొత్తాన్ని లెక్కించండి, దానిని కన్సోల్‌లో ముద్రించండి మరియు printFibonacci పద్ధతిని పునరావృతంగా మళ్లీ కాల్ చేస్తాము. మేము మునుపటి సంఖ్యను (మునుపటి) మరియు ప్రస్తుత సంఖ్యను (ప్రస్తుతం) ఆర్గ్యుమెంట్‌లుగా పాస్ చేస్తాము.

వాస్తవానికి, కోడ్‌లో రెండు లోపాలు ఉన్నాయి. మీరు కోడ్‌ని అమలు చేస్తే వాటిని చూడవచ్చు.

మొదటి ఎర్రర్ లాంగ్ టైప్ ఓవర్‌ఫ్లో కావడం. మా సీక్వెన్స్‌లోని 104వ సంఖ్య ప్రతికూలంగా ఉంది, ఇది పొడవైన రకం పొంగిపొర్లిందని సూచిస్తుంది.

రెండవ లోపం భిన్నంగా ఉంటుంది. సుమారు 12,000 సంఖ్యలను లెక్కించిన తర్వాత, మనకు లభిస్తుంది:

జావాలో కాల్ స్టాక్ పద్ధతి ఏమిటో గుర్తుకు తెచ్చుకోవడానికి ఇప్పుడు సరైన సమయం. జావా మెషీన్ అన్ని ఫంక్షన్ కాల్‌ల రికార్డును ఉంచుతుంది. దీన్ని చేయడానికి, ఇది స్టాక్ అని పిలువబడే ప్రత్యేక రకమైన సేకరణను ఉపయోగిస్తుంది. ఒక ఫంక్షన్ మరొకదానికి కాల్ చేసినప్పుడు, జావా మెషీన్ కొత్త 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, ఇది నిజానికి పూర్ణాంకం కంటే ఎక్కువ.MAX_VALUE (2_164_78 ) .

ఈ మార్పు స్వయంచాలకంగా సుదీర్ఘ ఓవర్‌ఫ్లో బగ్‌ను పరిష్కరించింది . మీరు మరిన్ని సిరీస్‌లను లెక్కించాలనుకుంటే, మీరు 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 పద్ధతిని కాల్ చేస్తాము.

రికర్సివ్ పద్ధతి అని పిలువబడుతున్నంత కాలం, దీనిని "పునరావృత అవరోహణ" అంటారు. పునరావృత ముగింపులు మరియు పద్ధతి కాల్‌లు తిరిగి వచ్చినప్పుడు, మేము కాల్ స్టాక్ "అన్‌వైండింగ్" అని చెబుతాము.

ప్రోగ్రామింగ్‌లో రికర్షన్ అనేది ఒక ఆసక్తికరమైన అంశం. మెటీరియల్‌పై మెరుగైన హ్యాండిల్ పొందడానికి, మన పనిని కొద్దిగా మార్చుకుందాం. ఫిబొనాక్సీ సిరీస్‌లోని పూర్ణాంకానికి మించని అన్ని సంఖ్యలను అవరోహణ క్రమంలో అవుట్‌పుట్ చేయడం కొత్త పని. 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);
    }
}
    

అవుట్‌పుట్ ఇలా ఉంటుంది: