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

রিকার্সিভ ফাংশনের সৌন্দর্য – ১

ধরো তোমার দুনিয়ায় রিকার্সিভ ফাংশন বলে কিসসু নাই। তুমি মহা শান্তিতে কোড করে দিন পার করতেছো। তোমার একদিন হঠাৎ করে জটিল একটা প্রবলেম সলভ করতে ইচ্ছা করলো। জটিল (!) প্রবলেমটা হচ্ছে ১ থেকে ১০ পর্যন্ত সংখ্যাগুলোকে তুমি প্রিন্ট করতে চাও। এই জটিল প্রবলেমের সহজ সমাধানের জন্য তুমি একটা কোড লিখলে এরকম করেঃ

চমৎকার ভাবে একটা ফাংশন কল করে তুমি ১ থেকে ১০ পর্যন্ত প্রিন্ট করে ফেললা! তবে এই একই কাজ করার জন্য আরেকটা দারুণ কোড লিখা যায় নিচের মত করেঃ

কোডটা রান করে দেখো। এটাও ১ থেকে ১০ পর্যন্ত প্রিন্ট করে। কী এমন আছে এই কোডের মধ্যে? আসো লাইন বাই লাইন কোডের ব্যবচ্ছেদ করি!

main function থেকে printSeries(10); কল করা হয়েছে। বুঝলাম এটা একটা ফাংশন। এর মধ্যে ১০ পাঠানো হয়েছে। ফাংশনের কাজ হচ্ছে ১ থেকে ১০ পর্যন্ত প্রিন্ট করে দেখানো। এবার দেখি এই ফাংশনের ভিতরে কী এমন আছে যার কারণে সে লুপ-টুপ ঘুরানো ছাড়াই কাজ করে ফেললো!

ফাংশনের বডির প্রথম লাইনে চেক করা হয়েছে n==0 কিনা? আমরা যেহেতু ১০ দিয়ে কল দিয়েছি তাই এখানে এই IF সত্য হবার কোন কারণ নাই। তাই আপাতত এটা নিয়ে মাথা না ঘামালাম। কোডের ৮ নাম্বার লাইনে দেখ আবার কল করা হয়েছে printfSeries(n-1); ঘটনা কী? মেইন ফাংশন থেকে একবার কল দিলাম ১০ দিয়ে, ফাংশনের ভিতরে দেখি আবার কল দেয়ার কোড লেখা। তেলেসমাতি কান্ড!!! এই লাইনে তাহলে কল হবে printSeries(9) দিয়ে (কারণ, n=10 সুতরাং n-1 = 9)। ফাংশনের বডির মধ্যে বসে আবারো সেই একই ফাংশনকে কল করা হয়েছে।

এখন আপাতত কোডের দিকে মন দিও না। মাথায় জট পাকানোর আগে আসো একটু গফ-সফ করি! 😛

তুমি যেহেতু ফাংশন কল বুঝো তাই বলছি আর কি। ফাংশন কল হলে প্রোগ্রামে কী ঘটনা ঘটে জানো? ধরো মেইন ফাংশনটা এক্সিকিউট হচ্ছে। একটা স্ট্যাক থাকে ফাংশনগুলো রাখার জন্য। স্ট্যাক না বুঝলে আপাতত ধরে নাও স্ট্যাক নামক একটা সিডি/ডিভিডি রাখার কেস আছে (যাতে সিডি/ডিভিডি ডিস্কগুলো একটার উপর একটা রাখা যায়)। তো এই স্ট্যাকের মধ্যে প্রোগ্রামে থাকা ফাংশনগুলোকে একটার উপর একটা সাজিয়ে রাখা হয়।

আমাদের মেইন ফাংশনটা কাজ করছে এই মুহুর্তে। তাই স্ট্যাকে মেইন ফাংশনটাকে রাখা হয়েছে। মেইন ফাংশন থেকে মনে করো A() নামক একটা ফাংশনকে কল করা হয়েছে। তখন কিন্তু মেইন ফাংশনের কাজ pause হয়ে থাকবে। কাজ চলতে থাকবে A() ফাংশনের। নতুন এই ফাংশনটাকে স্ট্যাকে রাখা হবে। স্ট্যাকের সিসটেমটাই হচ্ছে এরকম যে, সবার প্রথমে যাকে স্ট্যাকে রাখা হবে সে সবার নিচে থাকবে। আর সবার পরে যাকে রাখা হবে সে উপরে থাকবে। ১০ টা প্লেট একটার উপর একটা রাখলে যেই ঘটনা ঘটে সেটাই স্ট্যাক। তো এই মুহুর্তে আমাদের স্ট্যাকের উপরে আছে A(). উপরে যে থাকবে সে-ই কাজ করতে থাকবে। A() এর ভিতর থেকে আরেকটা ফাংশন কল হল B(). তখন স্ট্যাকে B() কে push করে দেয়া হবে। B() কাজ করতে থাকবে। B() এর কাজ শেষ হলে একে স্ট্যাকের উপর থেকে তুলে ডিলেট করে দেয়া হবে। এখন স্ট্যাকের উপর কে আছে? A() ফাংশন তাই না? এখন A() ফাংশন তার কোন কাজ বাকি থাকলে সেগুলো সেরে নিবে। এটার কাজ শেষ হলে এটাকেও স্ট্যাক থেকে মুছে দেয়া হবে। এখন স্ট্যাকে কে আছে? আমাদের মেইন ফাংশন তাই না? মেইন ফাংশন তার কাজ করতে থাকবে। যখন এর কাজ শেষ হয়ে যাবে তখন প্রোগ্রাম ক্লোজ হবে। স্ট্যাক থেকে একেও মুছে ফেলা হবে। এভাবেই ফাংশনগুলোর কল ম্যানেজ করে আমাদের বোকাসোকা কম্পিউটারগুলো।

লক্ষ্য করো, একটার পর একটা ফাংশন কল হচ্ছে। প্রতিটা ফাংশনের ভিতরেই এক বা একাধিক ভেরিয়েবল ডিক্লিয়ার হতে পারে। তার মানে প্রতিটা ফাংশন যখন কাজ করে তখন সে তার জন্য প্রয়োজনীয় মেমরি দখল করে। একটা ফাংশনের ভেরিয়েবল বা ডেটার সাথে কিন্তু অন্য ফাংশনের ডেটার সম্পর্ক থাকে না। অর্থাৎ A() ফাংশনের ভিতরে number নামের একটা ভেরিয়েবল ডিক্লিয়ার করলে B() ফাংশনের ভিতরেও number নামের ভেরিয়েবল ডিক্লিয়ার করতে পারবে। দুইটার মধ্যে কিন্তু কনফ্লিক্ট হবে না। অর্থাৎ ফাংশনগুলো নিজেদের একেকটা জগত তৈরি করে। ততক্ষণই তাদের রাজত্ব স্থায়ী হয় যতক্ষণ ফাংশনটা এক্সিকিউট হতে থাকে। ফাংশনের কাজ শেষ হলেই তাসের ঘরের মত ভেঙ্গে পরে তাদের সংসার। তার ডেটা রাখার জন্য যে সকল মেমরি দখল করা ছিল সেগুলোও ফ্রি হয়ে যায়। Recursive function বুঝার জন্য ফাংশন কল হবার বা স্ট্যাকের আইডিয়া থাকলে একটু সুবিধা হবে। তাই একটু বলে নেয়া।

রিকার্সিভ ফাংশন - রিকার্সন

কোডে ফেরত যাই। মেইন ফাংশন থেকে printSeries(10) দিয়ে যখন ফাংশন কল করা হয়েছে তখন স্ট্যাকে থাকা মেইন ফাংশনের উপরে এই ফাংশনটাকে রাখা হয়েছে। যার ভিতর n নামের একটা ভেরিয়েবল আছে। যার মান 10. ফাংশন বডিতে ঢোকার পরে একই ফাংশনকে যখন printSeries(9) দিয়ে কল করা হল তখন স্ট্যাকের উপরে আবারো একই ফাংশনের আরেকটা instance রাখা হল। যেখানে আগের ফাংশনের মতই n নামের একটা ভেরিয়েবল আছে। যার মান এটার ক্ষেত্রে ৯। আগের ফাংশনের n আর এই ফাংশনের n কিন্তু আলাদা। তাই একটার সাথে আরেকটা কনফ্লিক্ট করবে না। ৯ দিয়ে যখন একই ফাংশনকে আবারো কল দেয়া হল তখন প্রথম লাইনে চেক হল n==0 কিনা? ৯ দিয়ে কল হওয়ায় n এর মান 9 তাই IF এর আন্ডারে থাকা return কাজ করবে না। পরের লাইনে গিয়ে আবার কল হবে printSeries(n-1) বা printSeries(8) দিয়ে। এই ফাংশনের একটা instance আবারো রাখা হবে স্ট্যাকে। এভাবে রাখতেই থাকবে, রাখতেই থাকবে। স্ট্যাকে একটার উপর একটা ফাংশন থাকার মানেই হচ্ছে এই ফাংশনগুলোর কাজ এখনো কমপ্লিট হয় নাই। পরে হলেও এগুলোর কাজ আস্তে আস্তে শেষ করা হবে। প্রতিবার ফাংশন কল হবার সময় কিন্তু ১ করে কমছে। তার মানে কমতে কমতে এক সময় n এর মান দাঁড়াবে 0. স্ট্যাকের একদম উপরে এই ফাংশনকে রাখা হবে। এখন কিন্তু কোডের ৫ নাম্বার লাইনের চেকিং এ ধরা খেয়ে যেতে হবে। অর্থাৎ আমাদের এই IF এর মান সত্য হয়ে যাবে। সত্য হলে এক্সিকিউট হবে return; এর মানে হচ্ছে এই ফাংশন কলের কাজ এখানেই শেষ। ফাংশন বডির পরের লাইনগুলো আর এক্সিকিউট হবে না।

এই ফাংশনের কাজ শেষ এর মানে হচ্ছে একে call stack থেকে বের করে দাও। বের করে দিলে স্ট্যাকের একদম উপরে এখন কোন ফাংশন আছে? 0 এর আগের স্টেটটা আছে তাই না? অর্থাৎ এমন একটা printSeries() আছে যার n এর মান 1. যেহেতু এটা স্ট্যাকের উপরে আছে তাই এখন এর বাকি কাজগুলো শেষ করতে হবে। printSeries() ফাংশনের বডি হচ্ছে 4 থেকে 11 নাম্বার লাইন পর্যন্ত। স্ট্যাকের উপরে থাকা ফাংশন কিন্তু ৮ নাম্বার লাইনের কাজ শেষ করে রেখেছে। কারণ ৮ নাম্বার লাইনে এসেই সে printSeries(0) কল করেছিল। অতএব সে এখন ৯-১১ নাম্বার লাইনের কাজগুলো করবে। ১০ নাম্বার লাইনে দেখতে পাচ্ছি n এর মান প্রিন্ট করতে বলা হয়েছে। এই ফাংশনের n এর মান হচ্ছে 1. তাই সে 1 প্রিন্ট করবে। প্রিন্ট হবার পর এই ফাংশনের আর কোন কাজ বাকি থাকবে না। সুতরাং এই ফাংশন ইন্সটেন্সকেও স্ট্যাক থেকে বহিস্কার করা হবে!

এখন স্ট্যাকের উপরে আছে printSeries(2) এই ফাংশনটা। এই ফাংশনও কিন্তু ৮ নাম্বার লাইনের কাজ সেরে ফেলেছিল আগেই printSeries(1) কল দেয়ার মাধ্যমে। এখন বাকি কাজ করবে ১০ নাম্বার লাইনে n এর মান 2 প্রিন্ট করার মাধ্যমে। এরপর একেও স্ট্যাক থেকে বিদায় করা হবে। এভাবে এক সময় একে একে ১০ পর্যন্ত প্রিন্ট করা হবে। ১০ প্রিন্ট হবার পর সেটাকে বিদায় করা হবে। এখন স্ট্যাকের উপরের পজিশনে কে থাকবে? আমাদের মেইন ফাংশন! মেইন ফাংশনের কাছে যখন রিটার্ন করা হবে তখন কিন্তু স্ট্যাকে একটাই ফাংশন থাকবে। সেটা মেইন ফাংশনই! মেইনে রিটার্ন করে বাকি থাকা কাজগুলো করবে। অর্থাৎ ১৯ নাম্বার লাইনে থাকা printf() এর কাজ করবে। এভাবেই ১ থেকে ১০ পর্যন্ত প্রিন্ট করা হয়েছে।

ব্যাপারটা কি খুব বেশি গোলমেলে? মনে হয় না! যদি বুঝে গিয়ে থাকো তাহলে তোমার রিকার্সিভ ফাংশন বুঝা হয়ে গেছে! অভিনন্দন তোমাকে! 🙂

Recursion বা রিকার্সিভ ফাংশন এর সংজ্ঞা হিসেবে বলা হয় “এটা এক ধরনের ফাংশন যে কিনা নিজেই নিজেকে কল করে একেকটা স্বতন্ত্র ফাংশনের instance তৈরি করে।” অর্থাৎ, নিজের মত বৈশিষ্ট্যমন্ডিত ও একই রকম কর্মক্ষম আরো ফাংশনের কপি বানাতে পারে এমন ফাংশনই হচ্ছে রিকার্সিভ ফাংশন। রিকার্সিভ ফাংশন উদ্দেশ্য হচ্ছে আমরা যেই কাজটা করতে চাই বা যেই প্রবলেমটা সলভ করতে চাই সেটাকে ছোট ছোট প্রবলেমে ভাগ করা। প্রতিটা ছোট প্রবলেমকে সলভ করা (ছোট প্রবলেম সলভ করা সহজ তাই না?)। এরপর ছোট প্রবলেমের সলিউশনগুলোকে মার্জ করা বা ছোট প্রবলেমগুলোর সলিউশনের উপর ভিত্তি করে মূল সলিউশন বের করা।recursive_frame_by_codeandreload-d66yu9z

আমাদের প্রবলেম ছিল ১ থেকে ১০ প্রিন্ট করা। ফাংশনে পাঠানো হয়েছিল ১০। আমরা এটাকে ছোট অংশে কিভাবে ভাংতে পারি? আমি বলতে পারি যে, আমি ১০ প্রিন্ট করব। বাকিগুলা প্রিন্ট করব না। ১ থেকে ৯ পর্যন্ত প্রিন্ট করার দায়িত্ব আমি তোমাকে দিলাম। তুমি করলা কী, শুধু ৯ প্রিন্ট করলা। ১ থেকে ৮ প্রিন্ট করার দায়িত্ব রামকে দিলা। রাম ৮ প্রিন্ট করে ১ থেকে ৭ এর দায়িত্ব দিল সামকে। সাম ৭ প্রিন্ট করে ১ থেকে ৬ এর দায়িত্ব দিল যদুকে। যদু ৬ প্রিন্ট করে ৫ পাঠালো মধুর কাছে। এভাবে আমি ছোট্ট একটা কাজ করে বাকি কাজগুলো রাম-সাম-যদু-মধুকে দিয়ে করিয়ে নিলাম অর্থাৎ আমার বড় প্রবলেমটাকে আমি ছোট ছোট টুকরা করে ভাগ করে দিলাম। ছোট ছোট অংশ সলভ হল, তার ফলে আমার বড় প্রবলেমটাই আলটিমেটলি সলভ হল! এটাই রিকার্সিভের মজা!

লুপ দিয়ে করা যায় এমন সব প্রবলেমই রিকার্সন দিয়ে করা যায়। তাহলে লুপ ব্যবহার না করে রিকার্শন কেন ব্যবহার করব? কারণ রিকার্সনের ক্ষেত্রে আমাদের কোড অনেক সময়ই কম লিখতে হয়। রিকার্সন ফাংশন কল হওয়া কখন থামাতে হবে সেটা বের করে প্রবলেমটা ছেড়ে দেয়া যায় ফাংশনের উপর। আমাদের কাজ খানিকটা কমিয়ে দেয়। পরবর্তীতে বিভিন্ন অ্যালগরদিম ইমপ্লিমেন্ট করার সময়ও রিকার্সিভ ফাংশন প্রয়োজন হবে ঝামেলা কমানোর জন্য। রিকার্সন কল হওয়া কখন থামাতে হবে সেটা সব চেয়ে জরুরি বিষয়। যেই case এর জন্য ফাংশল কল হওয়া বন্ধ হয়ে যায় বা return; স্টেটমেন্ট কাজ করে সেই কেসকে বলা হয় base case. ফাংশন বডির শুরুতেই তাই বেজ কেসের চেক রাখতে হয়। বেজ কেস ঠিক মত চেক না করলে infinite loop এর মধ্যে পড়ে গিয়ে ফাংশন কল হতেই থাকবে। তাই সাধু সাবধান!

আজকে আর কোন জ্ঞান গর্ভ আলোচনা করব না। এবার সময় নিজেদের প্র্যাক্টিস করার। আমি ১ থেকে ১০ প্রিন্ট করেছি। তোমার কাজ এখন ১০ থেকে ১ প্রিন্ট করা। ২-১ জায়গায় একটু চেঞ্জ করলেই কাজ হয়ে যাবে। তুমি কি আসলেই কিছু বুঝেছ? কিসসু না বুঝে থাকলে কমেন্ট করে জানাও। আমি লেখাটাকে আরো মোডিফাই করার চেষ্টা করব। তুমি কি এই প্রথম রিকার্সন বুঝলে? তাহলেও জানাও! রিকার্সনের উপর আরো ২-৩ পর্ব লিখার জন্য উৎসাহ পাব। 🙂

আপনার মন্তব্য, পরামর্শ, সমালোচনার জন্য অধীর আগ্রহে অপেক্ষা করছি… 🙂

রিকার্সনের চমৎকার একটা উদাহরণ দেখা যাবে আলাভোলার ব্লগে! 😛

Comments

comments

26 thoughts on “রিকার্সিভ ফাংশনের সৌন্দর্য – ১

  1. খুব সুন্দর লেখা ভাই। আজকেই প্রথম রিকার্শন শিখলাম। মনে হয় বুঝছি। পরের পর্বগুলোর অপেক্ষায় থাকলাম। অনেক ধন্যবাদ।
    আর ছোট্ট একটা প্রশ্ন। void যেহেতু আছে return দিয়ে ব্রেক না করে লুপ কি break কমান্ড দিয়ে ব্রেক করা যাবে???

    1. মন্তব্যের জন্য ধন্যবাদ।
      দ্বিতীয় কোডে লুপ ব্যবহার করা হয় নি। তাই break statement ব্যবহার করা যাবে না। return-ই ব্যবহার করতে হবে।

      1. আচ্ছা if (n==0) এইখানে বুঝতে একটু প্রবলেম হয়েছিলো । ধন্যবাদ 🙂

          1. হ্যা ভাই বুঝেছি। আপনি লুপ না বলার পর আবার পড়লাম পুরোটা :v

  2. অনেক সুন্দর লিখেছেন, ভাই। অসংখ্য ধন্যবাদ।

  3. অনেক ভাল হয়েছে। পরবর্তি পর্বটা একটু তারাতারি দিন প্লিজ।

  4. ভাই Recursion নিয়ে আরো লেখেন। এই প্রথম। fibonacci and factorial এর। example বিহীন জানার মত কিছু পাইলাম। 🙂

  5. শেষের থেকে ১২ তম লাইনে “ফাংশন” শব্দটা “ফাংশল” লিখা হইসে।

  6. আমি আজকে পুরোপুরি বুঝলাম। আরো পর্বের অপেক্ষায় থাকলাম। ধন্যবাদ আপনাকে

  7. Resursive function এর প্রোগ্রামটাতে আপনি printSeries(int n) এর ভিতর প্রোগ্রাম থেকে বের হওয়ার জন্য return ইউজ করেছেন। শুধু return দেখে অনেক্ষন ভাবলাম যে শুধু return কেন ইউজ করলাম, এতদিন তো return 0; / return x+y(an operation); ইউজ করে এসেছি। পরে প্রোগ্রামটা break; statement ইউজ করে রান করার ট্রাই করলাম । হলনা, কারন break; শুধু loop এবং switch এর সাথে ইউজ হয় । তারপর আবার প্রোগ্রামটাতে আপনার reutrn; এর জায়গায় আমি return 0; দিয়ে রান করলাম এবং দেখি ঠিকই কাজ করল।

    তখন বুঝলাম যে return দিয়ে আসলে কি বুঝায় এবং কখন কিভাবে ইউজ করতে হয় আমি এখনো ভাল করে বুঝিনি.

    একটু কি ব্যাখ্যা করবেন যে কেন আপনি
    ১। return 0; না দিয়ে শুধু return; ইউজ করলেন?
    2. return দিয়ে আসলে কি বুঝায় এবং
    3. কখন return; ইউজ করব?

    1. return keyword এর কাজ হচ্ছে ফাংশনের কাজ শেষ করে প্রোগ্রামের কন্ট্রোলটা এই ফাংশনের caller এর কাছে ফিরিয়ে দেয়া (return করা)। ধরেন main function থেকে A() কল করা হল। স্ট্যাকে A() এখন টপে আছে। A() এর কাজ শেষ হবার পর প্রোগ্রামের কোন অংশ রান হবে? main function এর যেখান থেকে কল করা হয়েছে তার পর থেকে তাই না? এই রিটার্ন করার মাধ্যমে প্রোগ্রামের কন্ট্রোল কার হাতে যাবে বা কোথা বাকি পরের কাজগুলো করা হবে সেটা নির্দেশ করে।

      printSeries() ফাংশনের রিটার্ন টাইপ হচ্ছে void. অর্থাৎ এই ফাংশন তার caller এর কাছে কোনো ভ্যালু রিটার্ন করবে না। তার মানে আমার উচিত না এই ফাংশনের পর return 0; লিখাটা। কারণ return 0 এর অর্থ হচ্ছে এই ফাংশন তার caller কে 0 মানটা পাঠাচ্ছে। আমার ফাংশন যেহেতু void type এর অতএব কোনো ভ্যালু আমি রিটার্ন করতে পারব না। তাহলে এই ফাংশনের কাজ শেষ হলে main function এর কাছে প্রোগ্রামের কন্ট্রোলটা কিভাবে পাঠাবো? তখন জাস্ট return; লিখব। এর মানে হচ্ছে আমি এই ফাংশন কলের কাজ শেষ করলাম আর পরবর্তী কনট্রোল দিচ্ছি এই ফাংশনকে যে কল করেছে তাকে।

      কোনো একটা ফাংশন লিখলেন যেটা কোনো মান রিটার্ন করবে। উদাহরণ দেয়া যেতে পারে int add(int a, int b); একটা ফাংশন। add এর return type হচ্ছে int. আপনি expect করছেন এই ফাংশনে দুইটা int পাঠালে এই ফাংশন আপনাকে যোগফলটা পাঠায় দিবে। তখন আপনি return; দিয়ে শুধু প্রোগ্রামের কনট্রোলটা caller এর কাছে পাঠিয়ে দিলে হবে না। কনট্রোলের সাথে যোগফলটাও পাঠাতে হবে।

      এই লাইনের উত্তরঃ যদি ফাংশন শেষে বাকি প্রোগ্রামের কনট্রোলটুকুই তার কলারের কাছে পাঠাতে চান তাহলে শুধু return; ব্যবহার করবেন। আর যদি কনট্রোলের সাথে কোনো ভ্যালুও পাঠাতে চান তখন return value; ব্যবহার করবেন।

      আশা করি উত্তরটা পেয়েছেন। আরো সুন্দর ভাবে বুঝার জন্য এটা দেখতে পারেন। 🙂
      [টু দি পয়েন্টে পরিচ্ছন্ন একটা প্রশ্ন করার জন্য ধন্যবাদ। প্রশ্ন করা একটা আর্ট। খুব বেশি মানুষ এই আর্টটা জানে না <3 ]

  8. Assa vaia amra to printSeries ekta funcion nilam. Function use korle to function prototypes dite hoi.ekhane deoa hoi nai. Onek somoy e dekhi deoa hoi na kono problem o hosse. Bisoy ektu clear korle upokrito hota. 🙂

Leave a Reply

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