প্রস্থান শর্ত। স্ট্যাকওভারফ্লো ত্রুটি

প্রস্থান শর্ত ছাড়াই পুনরাবৃত্ত কোডের উদাহরণ

আসুন একটি রিকার্সিভ সমস্যা আরেকবার দেখি। একটি উদাহরণ হিসাবে, ফিবোনাচি সংখ্যা গণনা বিবেচনা করুন. সবাই স্মরণ করবে যে ফিবোনাচি ক্রম হল একটি সংখ্যাসূচক ক্রম যেখানে প্রথম দুটি সংখ্যা 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 সংখ্যা গণনা করার পরে, আমরা পাই:

এখন জাভাতে একটি মেথড কল স্ট্যাক কী তা মনে করার উপযুক্ত সময়। জাভা মেশিন সমস্ত ফাংশন কলের রেকর্ড রাখে। এটি করার জন্য, এটি স্ট্যাক নামে একটি বিশেষ ধরনের সংগ্রহ ব্যবহার করে। যখন একটি ফাংশন অন্যটিকে কল করে, তখন জাভা মেশিন স্ট্যাকের উপর একটি নতুন স্ট্যাকট্রেস এলিমেন্ট পুশ করে। ফাংশন শেষ হলে, এই উপাদানটি স্ট্যাক থেকে সরানো হয়। তদনুসারে, স্ট্যাক সর্বদা ফাংশন কল স্ট্যাকের বর্তমান অবস্থা সম্পর্কে আপ-টু-ডেট তথ্য সংরক্ষণ করে। StackTraceElement-এর জন্য ডকুমেন্টেশন বলে যে "একটি স্ট্যাক ওভারফ্লো ঘটলে এটি নিক্ষেপ করা হয় কারণ একটি অ্যাপ্লিকেশন খুব গভীরভাবে পুনরাবৃত্তি হয়।" একটি চলমান JVM মেথড কল স্ট্যাক সংরক্ষণ করার জন্য মেমরির একটি বিশেষ ক্ষেত্র রয়েছে। এই মেমরি এলাকার আকার OS এবং JVM সেটিংসের উপর নির্ভর করে। পদ্ধতি কল স্ট্যাক নিজেই ছাড়াও, আদিম ভেরিয়েবল (পদ্ধতি প্যারামিটারের নির্দিষ্ট মান) এবং রেফারেন্স ভেরিয়েবলের ঠিকানা (একটি মেমরি এলাকায় যাকে "হিপ" বলা হয়) এই বিশেষ মেমরি এলাকায় সংরক্ষণ করা হয়। কল স্ট্যাকের অ্যাক্সেস LIFO নীতি অনুসরণ করে।

প্রস্থান শর্ত সহ সঠিক উদাহরণ

কোডের দ্বিতীয় সমস্যাটি ঠিক করে শুরু করা যাক।

আসুন সমস্যাটি সমাধান করার চেষ্টা করি: যদি স্ট্যাকটি খুব ছোট হয়, তাহলে আসুন এটিকে আরও বড় করা যাক। এটি করার জন্য, "-Xss" পতাকা দিয়ে JVM শুরু করুন এবং স্ট্যাকের জন্য কত মেমরি বরাদ্দ করতে হবে তা নির্দিষ্ট করুন। আসুন 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_47) এর চেয়ে বেশি ।

এই পরিবর্তনটি স্বয়ংক্রিয়ভাবে দীর্ঘ ওভারফ্লো বাগ সংশোধন করেছে। আপনি যদি সিরিজের আরও গণনা করতে চান তবে আপনাকে অন্যান্য ডেটা প্রকার ব্যবহার করতে হবে, যেমন 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 পদ্ধতি বলা হয়। এটি বর্তমান সংখ্যা গণনা করে। যদি এটি আমাদের জন্য উপযুক্ত হয়, তাহলে আমরা এটি প্রদর্শন করি এবং নতুন আর্গুমেন্ট সহ আবার printFibonacciWithCondition পদ্ধতিতে কল করি।

যতক্ষণ রিকারসিভ মেথড বলা হচ্ছে, একে "রিকারসিভ ডিসেন্ট" বলা হয়। যখন রিকার্সিভ টার্মিনেট হয় এবং মেথড কল রিটার্ন হয়, আমরা বলি যে কল স্ট্যাক "আনওয়াইন্ডিং"।

Recursion প্রোগ্রামিং একটি আকর্ষণীয় বিষয়. উপাদানের উপর একটি ভাল হ্যান্ডেল পেতে, আসুন আমাদের কাজটি সামান্য পরিবর্তন করি। নতুন কাজ হল ফিবোনাচ্চি সিরিজের সমস্ত সংখ্যাকে অবরোহ ক্রমে আউটপুট করা যা 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);
    }
}

আউটপুট হবে: