পোস্টটি পড়া হয়েছে 7,209 বার

রিকার্সিভ ফাংশনের সৌন্দর্য – ৩ [GCD of 2 numbers]

Post updated on 14th September, 2019 at 10:49 pm

রিকার্সিভ ফাংশনের সৌন্দর্য সিরিজে ইচ্ছা ছিল পর্যায়ক্রমে বিভিন্ন উদাহরণ ও সেগুলোর ব্যাখ্যা যুক্ত করা। তারই ধারাবাহিকতায় আজ দেখব দুটি সংখ্যার GCD (Greatest Common Divisor) বা গ.সা.গু. (গরিষ্ঠ সাধারণ গুণনীয়ক) কিভাবে বের করা যায়। সেক্ষেত্রে প্রথমে আলোচনা করা হবে GCD এর ব্যাসিক কনসেপ্ট। এরপর রিকার্সিভ ফাংশন ব্যবহার না করে ও ব্যবহার করে উভয় কোডই দেখানো হবে ইনশাআল্লাহ।

রিকার্সনের বেশ কিছু প্রাথমিক ধারণা দেয়া হয়েছে প্রথমদ্বিতীয় পর্বে। সেগুলো মাথায় থাকলে আশা করি এই পর্ব বুঝতে কোনো সমস্যা হবে না।

GCD বা গ.সা.গু কী?

ছোটবেলায় আমরা পড়ে এসেছি গ.সা.গু. এর পূর্ণরূপ হচ্ছে গরিষ্ঠ সাধারণ গুণনীয়ক। ইংরেজিতে যাকে বলা হয় Greatest Common Divisor. নাম দেখে বিষয়টা বুঝার জন্য আমার কাছে বাংলার চেয়ে ইংরেজিটাই বেশি সহজ মনে হয়। Greatest মানে সবচেয়ে বড় বা গরিষ্ঠ, Common অর্থ সাধারণ – মানে যেটা উভয়ের মধ্যেই কমন আছে এবং Divisor মানে যে কিনা ভাগ করে বা নিঃশেষে বিভাজ্য করতে পারে। সুতরাং দুটি সংখ্যার GCD হচ্ছে এমন একটি বৃহত্তম সংখ্যা যা দিয়ে উভয় সংখ্যাকেই নিঃশষে ভাগ করা যায়

উদাহরণ হিসাবে উল্লেখ করা যায় 12 ও 56 এর GCD হচ্ছে 4. অর্থাৎ 4 হচ্ছে এমন সর্বোচ্চ সংখ্যা যা দিয়ে 12 ও 56 উভয়কেই নিঃশেষে ভাগ করা যায়। আর কোন্ কোন্ সংখ্যা দিয়ে 12 ও 56 কে ভাগ করা যায়? 12 ও 56 উভয় সংখ্যার Common Divisor-গুলো হচ্ছে 1, 2, 4. এই তিনটি সংখ্যা দিয়েই কেবল 12 ও 56 কে নিঃশেষে বিভাজ্য করা যায়। আর যেহেতু 4 হচ্ছে এদের মধ্যে greatest তাই একে আমরা বলছি Greatest Common Divisor.

GCD বা গ.সা.গু. নির্ণয়ের পদ্ধতি

বেশ কয়েক ভাবেই GCD বের করা যায়। প্রথমে দেখি মৌলিক উৎপাদকের সাহায্যে কিভাবে কাজটা করা যায়।

12 ও 56 সংখ্যা দুটিকে prime factor (মৌলিক উৎপাদক) এর মাধ্যমে এভাবে প্রকাশ করতে পারিঃ

12 = 2 * 2 * 3

56 = 2 * 2 * 2 * 7

এবার দুটি সংখ্যার মধ্যে যতগুলো কমন prime factor আছে সেগুলোকে আলাদা করি। দেখা যাচ্ছে উভয়ের মধ্যেই দুইটি করে 2 কমন আছে। তাই, 2*2 বা 4-ই হচ্ছে 12 ও 56 এর GCD.

স্কুললাইফে আমরা শিখেছিলাম ইউক্লিডিয়ান পদ্ধতিতে গ.সা.গু. নির্ণয়। এখন সেটা দেখা যাক।

Euclidean algorithm for GCD
Euclidean algorithm for GCD

এখানে যেই কাজগুলো করা হয়েছে তা হচ্ছেঃ প্রথমে 12 (b)  দিয়ে 56 (a) কে ভাগ করে ভাগশেষটা (r = a % b) বের করা হয়েছে। ভাগফল আমাদের আপাতত কোনো কাজে আসবে না। তো ভাগশেষ পাওয়া গেল 8 (r). এবার এই ভাগশেষ 8 (now b is 8) দিয়ে ভাগ করতে হবে ভাজক 12 কে (a is 12)। এবার ভাগশেষ পাওয়া গেল 4 (new r is 4). এভাবে প্রতিবার ভাজক ও ভাজ্যকে পরিবর্তন করে করে ভাগশেষ বের করতে হবে। যতক্ষণ পর্যন্ত ভাগশেষ 0 পাওয়া না যাবে ততক্ষণ এই ভাগের কাজ চালিয়ে যেতে হবে। খেয়াল করলে বুঝা যাবে প্রতিবার ভাগ করার পরই a, b ও r এর মান পাল্টে যাচ্ছে। প্রথমবার ভাগ করার পর প্রাপ্ত r দ্বিতীয় ধাপে গিয়ে b এর পজিশনে বসবে অর্থাৎ এই r ই এখন ভাজক হিসাবে কাজ করবে। একই ভাবে প্রথম ধাপের ভাজক b দ্বিতীয় ধাপে হয়ে যাচ্ছে ভাজ্য a. এভাবে প্রতিটা iteration এ মানগুলো swap করতে থাকবে।

আর যেই সংখ্যাটি দিয়ে ভাগ করার ফলে ভাগশেষ 0 আসলো সেটাই হবে GCD. পোস্টের পরের অংশে ইউক্লিডিয়ান মেথডটাকেই কোডে রূপান্তর করা হবে।

C Program for GCD of 2 numbers

পোস্টটা মূলত রিকার্সিভ ফাংশনের হলেও আমরা এখানে রিকার্সিভ সহ ও রিকার্সিভ ছাড়া উভয় ইমপ্লিমেন্টেশনই দেখব। এতে উভয়ের মধ্যে তুলনা করতে সহজ হবে।

Find GCD using While Loop

ছবিতে দেখানো ইউক্লিডিয়ান মেথডটার হুবহু ইম্প্লিমেন্টেশন দেখানো হয়েছে নিচের কোডেঃ

int gcdByLoop(int a, int b){
    int r;
    while(1)
    {
        r = a % b;

        if(r==0)
            break;

        a = b;
        b = r;
    }

    return b;
}

উপরের ফাংশনে দুটি nonzero positive integer পাঠালে তাদের GCD রিটার্ন করা হবে। While Loop এর condition পার্টে 1 দেয়া হয়েছে। আপাত দৃষ্টিতে এটি একটি infinite loop. লুপের ভিতরে ঢোকা যাক। লুপের ভিতরে ঢুকেই a-কে b দিয়ে ভাগ করে তার ভাগশেষ রাখা হয়েছে r এ। আমরা জানি ভাগশেষ বের করার অপারেটর হচ্ছে ‘%’. ভাগশেষ বের করার পর চেক করছি ভাগশেষটা 0 কিনা। যদি 0 হয় তাহলে এই লুপের কাজ শেষ। break statement এর মাধ্যমে লুপ থেকে বের হয়ে return করে দিবে b এর মান। কারণ b দিয়ে a কে ভাগ করেই ভাগশেষ 0 এসেছে। তাই b এর মানই হবে GCD.

যদি লুপের প্রথম ইটারেশনে ভাগশেষ 0 না হয় তখন লুপ ব্রেক করবে না। ইউক্লিডিয়ান মেথড অনুযায়ী ভাগশেষ বের করার পর নতুন ইটারেশনের জন্য ভাজ্য ও ভাজকের মান নির্ধারণ করতে হবে। আগেই দেখেছি প্রথম ধাপের ভাজক b এর মান পরের ধাপে হয়ে যাবে ভাজ্য a. সেই কাজটাই করা হয়েছে ব্রেকের পরের লাইনে। তো আমরা পেয়ে গেলাম পরের ধাপের নতুন ভাজ্য a. এখন দরকার নতুন ভাজক। যে কিনা ভাগ করার কাজটা করবে। প্রথম ধাপের কোন্ মানটা পরের ধাপে গিয়ে ভাজক হিসাবে কাজ করে? সেটা হচ্ছে ভাগশেষ r এর মান। তাই নতুন ভাজকের মান বসানো হয়েছে b = r করার মাধ্যমে।

তো এভাবে প্রতিবার লুপ ঘুরতে থাকবে, r = a%b এর মান বের করবে। সেটা 0 হলে ব্রেক করে b return করে দিবে। 0 না হলে a=b ও b=r করবে। আশা করি এটা বুঝতে কোনো সমস্যা নাই। উপরের এই কোডটাকে একটু চেঞ্জ করে নিচের মত করে লিখা যায়।

int gcdByLoop(int a, int b){
    int r;
    while(1)
    {
        r = a % b;
        a = b;
        b = r;

        if(b==0) //(r==0) এটাও লিখতে পারেন
            break;
    }

    return a;
}

আগের থেকে এর পার্থক্যটা হচ্ছে ভাগশেষ বের করার সাথে সাথেই সেটা 0 কিনা চেক না করে পরের ধাপের জন্য ভাজ্য ও ভাজকের মান আপডেট করে দিলাম। ফলে লুপের প্রথম তিন লাইন এক্সিকিউট হবার পর current iteration এর ভাগশেষ আছে b এর মধ্যে আর ভাজক আছে a এর মধ্যে। এরপর চেক করা হল b==0 কিনা। যদি সত্য হয় তাহলে লুপ ব্রেক করে দিচ্ছি। এরপর রিটার্ন করছি a এর মান। a-ই আমাদের GCD কারণ সর্বশেষ যেই ভাজকের জন্য ভাগশেষ 0 হয়েছে সেটি রাখা আছে a এর মধ্যে।

এই কোডটুকু বুঝলে পরের অংশের রিকার্সিভ ফাংশনের সাথে লুপের কোডের তুলনা করতে সহজ হবে।

Find GCD using Recursive Function

int gcdByRecursion(int a, int b){

    if(b==0) //base case
        return a;

    return gcdByRecursion(b, a%b);
}

উপরের এই ছোট্ট কোডটা আগের উল্লেখিত কোডের মত একই কাজ করবে।

প্রথম বার gcdByRecursion(56, 12) দিয়ে কল করা হয় main function থেকে। তখন ফাংশন বডির ভিতরে if(b==0) মিথ্যা হবে। তাই return a; এক্সিটিউট হবে না। পরের লাইনে গিয়ে return gcdByRecursion(b, a%b) এক্সিকিউট হবে। তখন আসলে কী কাজটা হচ্ছে? এখানে এই ফাংশনটা নিজেই নিজেকে কল দিচ্ছে। কল দেয়ার সময় প্যারামিটার হিসাবে পাঠাচ্ছে (12, 8) [কারণঃ 56%12 = 8]

সে নিজেকে কল করছে এবং লক্ষ্যনীয় বিষয় হচ্ছে এখনো কিন্তু প্রথম ফাংশন কলের কাজ শেষ হয় নাই। ফাংশন কলের একটা স্ট্যাক কল্পনা করলে বুঝতে সুবিধা হবে। প্রথমবার যখন এই ফাংশনটি কল হয়েছে, ধরা যাক তখন কলের যাবতীয় ডেটা একটা স্ট্যাকে পুশ করা হয়েছে। যতক্ষণ ফাংশনটির এক্সিকিউশন শেষ না হবে ততক্ষণ পর্যন্ত ডেটাগুলো স্ট্যাকে থাকবে।

দ্বিতীয় বার gcdByRecursion() কল হয় প্রথম ফাংশনের বডির ভেতর থেকে (12, 8) দিয়ে। এই কলে ফাংশনের প্রথম প্যারামিটারে পাঠানো হচ্ছে 12 আর দ্বিতীয় প্যারামিটারে পাঠানো হচ্ছে 8 (56%12 = 8)। যখন দ্বিতীয়বার (12, 8) দিয়ে কল করা হয়েছে তখন এই দ্বিতীয় ফাংশন কলের যাবতীয় ডেটা আগের স্ট্যাকে পুশ হয়ে যাবে। তাহলে স্ট্যাকের একদম নিচে আছে প্রথম ফাংশন কলের ইনফরমেশন। আর তার উপরের পজিশনে আছে দ্বিতীয় ফাংশন কলের ইনফরমেশন। এই ফাংশন এক্সিকিউট করতে গিয়ে দেখা গেল এখানেও base case true নয়। তাই আবার gcdByRecursion() ফাংশনটি কল হবে। এবারের কলে পাঠানো হবে (8, 4) [কারণঃ 12%8 = 4].

তৃতীয় বারের মত কল হওয়া ফাংশনের প্যারামিটারে পাওয়া গেল (8, 4)। কল হবার সাথে সাথে আগের মত স্ট্যাকে আবার এই ফাংশনের ইনফরমেশন পুশ করা হবে। ফাংশন বডির ভিতরে গিয়ে দেখা গেল b এর মান 4 যা 0 এর সমান নয়, অর্থাৎ এটিও base case satisfy করে না। তাই ফাংশন বডির শেষ লাইনের মাধ্যমে আবার ফাংশনটি কল করা হবে। কল করার সময় প্যারামিটারে পাঠানো হবে (4, 0). দ্বিতীয় প্যারামিটারে শূন্য পাঠানো হচ্ছে কারণ 8 % 4 = 0.

চতুর্থ কলে এসে আগের মতই ফাংশনের যেই স্ট্যাকটা আছে সেখানে এই ফাংশন কলের ইনফরমেশনও পুশ করা হবে। ফাংশনটি এক্সিকিউট করার সময় দেখা যাবে base case-টা সত্য হয়ে গেছে। কারণ এই ফাংশন কল করা হয়েছিল (4, 0) দ্বারা। b এর ভ্যালু যেহেতু 0 তাই ফাংশনটি তার আগের caller এর কাছে রিটার্ন করবে a এর মান যা 4. একই সাথে এই ফাংশনের কাজ শেষ হয়ে যাওয়ায় একে ফাংশনের স্ট্যাক থেকে pop করা হবে।

gcd recursive call function stack in memory
Illustration of Function Stack for Recursive call

আগের লাইনে বলেছি চতুর্থ ফাংশন তার কলারের কাছে 4 রিটার্ন করবে। আচ্ছা চতুর্থ ফাংশনের caller-টা আবার কে? মানে কে এই চতুর্থ ফাংশনকে কল করলো? খেয়াল আছে নিশ্চয়ই! তৃতীয় ফাংশন থেকেই কিন্তু চতুর্থ ফাংশনের ডাক এসেছিল। তো যখন চতুর্থ ফাংশন 4 রিটার্ন করবে তখন তা রিসিভ করবে তৃতীয় ফাংশন।

আমাদের প্রোগ্রাম এখন তৃতীয় ফাংশন কলের কাজকর্ম শেষ করার দিকে মনোযোগ দিবে। সে দেখবে স্ট্যাকের টপে থাকা আমাদের তৃতীয় ফাংশনকে কল করা হয়েছিল (8, 4) দ্বারা। কে কল করেছিল? কল করেছিল দ্বিতীয় ফাংশন। সেটা নিয়ে পরে চিন্তা করা যাবে। আপাতত তৃতীয়টার কাজ শেষ করি। তো তৃতীয় ফাংশন এতক্ষণ বসেছিল কেন? কারণ তার বেজ কেস সত্য না হওয়ায় সে এক্সিকিউট করেছিল return gecByRecursion(4, 0); তার মানে দাঁড়ায়, তৃতীয় ফাংশন তার কলারের কাছে gecByRecursion(4, 0) এর ভ্যালু রিটার্ন করবে। সেই ভ্যালুটা কত? gecByRecursion(4, 0) কল করে কী রিটার্ন পেয়েছিলাম? চতুর্থ ফাংশন থেকে এর মান রিটার্ন পেয়েছিলাম 4. অতএব তৃতীয় ফাংশন তার caller দ্বিতীয় ফাংশনের কাছে gecByRecursion(4, 0) এর মান হিসাবে 4 রিটার্ন করে দিবে। এবং একই সাথে এই ফাংশনের কাজ শেষ হওয়ায় একে ফাংশন স্ট্যাক থেকে pop করা হবে।

দ্বিতীয় ফাংশনটি এখন স্ট্যাকের টপে আছে। এই ফাংশনের দিকে নজর দিলে দেখা যাবে একে কল করার সময় প্যারামিটার পাঠানো হয়েছিল (12, 8)। তৃতীয় ফাংশনের মত তারও বেজ কেস সত্য ছিল না। তাই সে এক্সিকিউট করেছিল return gcdByRecursion(8, 12%8); অর্থাৎ সে রিটার্ন করতে চায়, gcdByRecursion(8, 4) কল করলে যেই ভ্যালু পাওয়া যাবে সেটা। gcdByRecursion(8, 4) দিয়ে তৃতীয় ফাংশনকে কল করা হয়েছিল, সে কী রিটার্ন করেছিল মনে আছে? সে দ্বিতীয় ফাংশনের কাছে রিটার্ন করেছিল 4. ব্যস!!! দ্বিতীয় ফাংশনও 4 রিটার্ন করে দিবে তার caller প্রথম ফাংশনের কাছে। অতপর একেও স্ট্যাক থেকে বিতাড়িত করা হবে।

প্রথম ফাংশন এখন স্ট্যাকের টপে। আর এটিই সর্বশেষ ফাংশন। এই ফাংশনকে কল করা হয়েছিল main function থেকে। আর এই ফাংশনকে কল করা হয়েছিল (56, 12) দিয়ে। অর্থাৎ এই ফাংশন কলে আমরা আসলে 56 ও 12 এর গ.সা.গু. রিটার্ন হোক সেটা এক্সপেক্ট করি। এতক্ষণ এত এত কাজ হল। সব শেষ করে এখন প্রথম ফাংশনের ভিতর আসা যাক। দেখা গেল প্রথম ফাংশনেরও বেস কেস সত্য ছিল না। তাই সে দ্বিতীয় ফাংশন কলটি করেছিল return gcdByRecursion(12, 8) কল করার মাধ্যমে। অর্থাৎ সে তার caller-কে অর্থাৎ মেইন ফাংশনের কাছে gcdByRecursion(12, 8) এর রিটার্ন করা ভ্যালুটাই রিটার্ন করবে। আর এটি হচ্ছে 4 যা তার কাছে রিটার্ন করেছে দ্বিতীয় ফাংশন। এরই মাধ্যমে প্রথম ফাংশনের এক্সিকিউশন শেষ হল এবং একেও স্ট্যাক থেকে pop করা হলো।

অবশেষে main function এ রেজাল্ট পাওয়া গেল 4.

রিকার্সিভ ফাংশনে অ্যাত্ত ঝামেলা!!! কী দরকার এর?

উপরের চার পাঁচটা ফাংশন কল আর এর ভিতরকার এত কিছু দেখে উপরের প্রশ্নটি মাথায় আসলে কাউকে দোষ দেয়া যায় না। আসলেই তো! কী দরকার আছে এত ঝামেলা করে রিকার্সন ইউজ করার? বা সকল ক্ষেত্রেই রিকার্সন কি ভাল চয়েজ? উত্তর হচ্ছে “না। সব সময় রিকার্সন ভাল চয়েজ নাও হতে পারে”। যদি আপনার মেমরি লিমিটেশন থাকে, অর্থাৎ অল্প মেমরির কোনো ডিভাইসের জন্য অ্যাপ্লিকেশন বানাতে চাচ্ছেন তখন সেখানে রিকার্সিভ ফাংশন ইউজ করার আগে একটু হিসাব করে নেয়া ভাল। কারণ এই ফাংশন স্ট্যাকের প্রতিটা আইটেমের জন্যেই কিন্তু আলাদা আলাদা ভাবে দুটি করে integer a and b declare করা হয়েছে। প্রথম থেকে চতুর্থ ফাংশন পর্যন্ত চার দু গুণে মোট আটটা ইন্টিজার ভ্যারিয়েবল এক্সট্রা ইউজ হচ্ছে। তো আপনার যদি মেমরি স্বল্পতা থাকে তাহলে রিকার্সন ইউজ না করে লুপ ঘুরিয়ে কাজ করা ভাল হবে।

আসলে রিকার্সন সাধারণত এরকম সোজাসাপ্টা কাজের চেয়ে আরেকটু জটিল কাজের জন্য বেশি ব্যবহৃত হয়। একটা ইন্টারেস্টিং বিষয় কি! এত এত জটিল কাজকর্ম হচ্ছে তা কিন্তু ভিতরে ভিতরে। আমাদের কোড করার আগে শুধু একটু চিন্তা করতে হবে যে কিভাবে কোডটাকে একটা রিকার্সন সিসটেমের মধ্যে ফেলে দেয়া যায়। এর ফলে কোড কম লিখতে হয়। কিন্তু রিকার্সিভের জাদুতে সুন্দর ভাবে আমাদের কাজটাও হাসিল হয়। উদাহরণ হিসাবে Quick Sort এবং Merge Sort এর কথা উল্লেখ করা যায়। এই পোস্টটি বুঝে থাকলে আপনি কুইক সর্টের উপর আমার এই লেখাটি এবং মার্জ সর্টের উপর এই লেখাটি পড়তে পারেন। দেখবেন এই অ্যালগরিদমগুলো রিকার্সন ছাড়া ইমপ্লিমেন্ট করা খুবই কঠিন ব্যাপার। রিকার্সনের অন্যতম প্রধান উদ্দেশ্য হচ্ছে ইটারেটিভ কোনো প্রবলেমকে ভেঙে ছোট ছোট প্রবলেমে ভাগ করা এবং ভাগ হওয়া এই প্রবলেমগুলোর সলিউশনগুলোর উপর বেজ করে ফাইনাল সলিউশন দাঁড় করানো। তবে সব প্রবলেমের ক্ষেত্রে এটা অ্যাপ্রোপ্রিয়েট নাও হতে পারে। এজন্য প্র্যাক্টিস, প্রবলেম সলভিং ও অভিজ্ঞতার বিকল্প নাই।

এই সিরিজের পরবর্তী পোস্ট হচ্ছে Fibonacci Series এর n-তম পদের মান বের করার জন্য রিকার্সিভ ফাংশনের ব্যবহার সম্পর্কে। চতুর্থ পোস্টটি পড়া যাবে এখান থেকে

9 thoughts on “রিকার্সিভ ফাংশনের সৌন্দর্য – ৩ [GCD of 2 numbers]

  1. অসংখ্য ধন্যবাদ ভাইয়া ^_^
    রিকার্শন নিয়ে যা ঘাপলা ছিলো ,
    আপনার পোস্টগুলো পড়ে ,
    সেগুলো দূর হয়ে গেছে 🙂

  2. অনেক সুন্দর পোষ্ট , অনেক কিছু জানলাম। আমার কিছু প্রশ্ন ছিল যদি একটু ক্লিয়ার করে দিতেন তাহলে উপকৃত হতাম।
    প্রথম while loop উদারণ এ উল্লেখ করে দিসিলেন যে, r=a%b , a=b, b=r . কিন্তু রিকারসির্ভ এর সময় r=a%b , a=b, b=r এই রকম কোন কিছু ত ডিক্লেয়ার করে দেন নাই। তাইলে কিভাবে (b,a%b) এর পরে b=a, a%b=b হয়ে যাচ্ছে ? বিষয়টা একটু ক্লিয়ার করে দিলে ভাল হত।

    1. ভ্যালুগুলো কিন্তু ঠিকই ইন্টারচেঞ্জ হচ্ছে। প্রথমবার যখন ফাংশন কল হয় তখন যদি ৫৬, ১২ পাঠানো হয়। এরপর ফাংশনের ভিতরে আবার ফাংশন কল হবে ১২, ৫৬%১২ দ্বারা। দেখেন, প্রথম ফাংশন কলে যেই ভ্যালুটা b, সেটা দ্বিতীয় ফাংশন কলে a হয়ে যাচ্ছে।

      আপনি কোডের পরের ব্যাখ্যাগুলো আর সাথে তার নিচের ছবিটা একটু মিলিয়ে নিন। আশা করি বুঝতে সহজ হবে।

      1. নিচে কোন ছবির কথা বললেন ভাই বুঝলাম না 🙁 । আপনি বললেন যে, প্রথম ফাংশন কলে যেই ভ্যালু b ,সেটা দ্বিতীয় ফাংশন কলে a হয়ে যাচ্ছে কিন্তু কিভাবে সেটা বুঝতেসি না কারণ b যদি দিয়েই দি তাহলে b কিভাবে a হয়ে যাচ্ছে ? আর প্রথম ফাংশন কলে যেটা b, সেটা যদি দ্বিতীয় ফাংশন কলে a হয়ে যায় তাহলে দ্বিতীয় ফাংশন কলে b হচ্ছে কোনটা ? ভাইয়া কিছুতেই বুঝতেসি না ফাংশনের ভিতর দিয়ে কিভাবে কি পাস হয়ে ভ্যালু নিজে নিজে চ্যাঞ্জ হয়ে যাচ্ছে 🙁 যদি একটু বিস্তারিত বুঝাইয়া দিতেন খুব ভাল হত।
        আশা করি বুঝিয়ে দিবেন। রিপ্লে এর অপেক্ষায় থাকলাম 🙂

        1. মূল পোস্টের রিকার্সিভ ফাংশনের পরে একটা ছবি আছে। সেটার কথা বলেছি।
          ফাংশনটা এরকম যদি হয়ঃ
          int gcd(int a, int b){
          … … …
          retrun gcd(b, a%b)
          }
          এখানে কী হচ্ছে? প্যারামিটারে এসেছে a এবং b. প্রথমে a এবং দ্বিতীয়তে b. শেষ লাইনে যখন আবার ফাংশনটা নিজেই নিজেকে কল করছে তখন দেখেন প্রথম প্যারামিটারে পাঠানো হয়েছে b আর দ্বিতীয় প্যারামিটারে পাঠানো হয়েছে a%b.

          এর মানে কী দাঁড়ালো? মানে হচ্ছে, প্রথম ফাংশন কলে যেই মানটা b হিসাবে এসেছিল ঐ মানটিই দ্বিতীয় ফাংশন কলে a হিসাবে যাচ্ছে। এভাবে চিন্তা করে পোস্টের ছবিটার সাথে মিলিয়ে দেখতে পারেন।

  3. আচ্ছা a=12 আর b=56 হলে প্রোগ্রামের ফ্লো কেমন হবে? আর এক্ষেত্রেও কেন রেজাল্ট 4 দেয়?

    1. চমৎকার প্রশ্ন!
      যখন a=12 আর b=56 হয় তখন ফাংশনের বডিতে ঢুকে বেজ কেসটা false. তাই return a; এক্সিকিউট হবে না। পরের লাইনে ফাংশনটি আবার কল হবে। কী দিয়ে কল করা হবে? (b, a%b) দিয়ে। b এর ভ্যালু 56 এখন প্রথম প্যারামিটারে বসে গেছে। দ্বিতীয় প্যারামিটারে বসবে a%b এর মান, যা 12. খাতা-কলমে হিসাব করে দেখবেন ছোট সংখ্যাকে বড় সংখ্যা দিয়ে ভাগ করলে ছোট সংখ্যাটিই ভাগশেষ হিসাবে পাওয়া যায়। তার মানে দ্বিতীয়বার ফাংশন কলে কিন্তু আমরা উদাহরণের মত a=56, b=12 পেয়ে গেছি। এতে বাড়তি একটা স্টেপ বেশি কাজ করতে হবে প্রোগ্রামকে। আমার উদাহরণে চারটা স্ট্যাকের মাধ্যমে চারটা স্টেপে রেজাল্ট চলে আসে। কিন্তু প্যারামিটারের ভ্যালুগুলোর অর্ডার চেঞ্জ করে দিলে অর্থাৎ ছোটটাকে প্রথমে আর বড়টাকে পরে দিলে একটা স্টেপ বেশি লাগবে।

      আশা করি উত্তরটা পেয়েছেন। এখনো কনফিউশন থাকলে কমেন্টে জানাবেন।
      ধন্যবাদ।

      1. অনেক ধন্যবাদ। খুব ব্যাসিক জিনিসটা মিস করে গেছিলাম। তাই সমস্যা হচ্ছিল।

Leave a Reply

Your email address will not be published. Required fields are marked *