রিকারশনের মাধ্যেমে গসাগু বের করা

গসাগু বা GCD[Greatest common divisor] এর সাথে সবাই পরিচিত তাই না? রিকারশন দিতে দেখি কিভাবে GCD বের করার ইউক্লিডের পদ্ধতির দিয়ে গসাগু বের করা যায়। কত সহজে দেখুন গসাগু বের করা যায় রিকারশন দিয়েঃ

তার আগে আমরা ইউক্লিড পদ্ধতি এর সাহায্যে দুইটি সংখ্যার গসাগু বের করার এলগরিদমটা দেখি।

দুইটি সংখ্যা [m,n] এর গসাগু বের করতে হবে।

1. m কে n দিয়ে ভাগ করি।
2. যদি ভাগশেষ r=0 হয় তাহলে n ই হচ্ছে গসাগু।
3. যদি তা না হয়, তাহলে m=n; n=r; এবং প্রথম ধাপ থেকে শুরু করি। [মানে n এর মান রাখব m এর ভেতর এবং r এর মান রাখব n এর ভেতর। এবং m, n কে আবার প্রথম ধাপে পাঠিয়ে দিব]

নিচের কোডটা দেখুন। GCD বের করার ফাংশন । আমি এখানে শুধু রিকারসিভ ফাংশনটা লিখলামঃ

gcd(int m, int n){

int r=m%n;

if (r==0) return n;

else gcd(n,r);

}

শেষ। এটা দিয়ে একটি প্রোগ্রাম লিখে রান করুন আপনার প্রিয় প্রোগ্রামিং ল্যাঙ্গুয়েজ দিয়ে। দেখুন কি সহজেই গসাগু বের করে পেলে।