রিকার্সন ফাংশন আসলে কিভাবে কাজ করে!
Published: 2022-12-01 14:42:22



রিকার্সন আসলে কিভাবে কাজ করে তা জানার আগে আমরা আগে একটা রিকার্সন ফাংশন এর উদাহরন কোড দেখে নেই আমি কোডটি সি প্রোগ্রামিং ভাষায় দেখিয়েছি। আসলে সব কম্পিউটার প্রোগ্রামিং ভাষার মৌলিক জিনিসপত্র গুলো একই, কিছু সিনট্যাক্স এর ভিন্নতা রয়েছে না হলে সবকিছু মোটামুটি একই তবে এদের প্রয়োগ ক্ষেত্র আলাদা আলাদা হয়।



রিকার্সন বলতে বুঝায় যে ফাংশন নিজেই নিজেকে কল করে তাকে রিকার্সন ফাংশন বলে। তো আমরা এখন উপরের প্রোগ্রাম টি কিভাবে কাজ করছে তা বর্ননা করবো। বর্ননা করার আগে আমাদের কিছু জিনিস সর্ম্পকে জান্তে হবে যেমনঃ স্ট্যাক মেমরি, ফাংশন, রিটার্ন ইত্যাদি।

স্ট্যাকঃ- স্ট্যাক হলো একটি ডাটা স্ট্রাকচার যা ভেতর এ ফাংশন কল হবার পর ফাংশন এর সমস্ত তথ্য স্ট্যাক এ জমা হয়।  স্ট্যাক এ সবার আগে যে বা যাকে রাখা হবে তাকে সবার শেষে ব্যাবহার বা এক্সেস করা জাবে। স্ট্যাক হলো LIFO (Last in fast out) ফর্মুলা অনুযায়ি কাজ করে।

ফাংশনঃ- ফাংশন এর মানে হলো কাজ করা বুঝায়। যেখানে কোন একটি নির্দিষ্ট কাজ করা হয়।

রির্টানঃ- রিটার্ন এর মানে হলো ফেরত পাঠানো, কোন একটি ফাংশন কোন নির্দিষ্ট কাজ করে  তার ফল রিটার্ন করে দেয়। যেখান থেকে ফাংশন কল করা হয়েছে সেখান এ তা ফেরত পাঠানো হয়।

এবার আসি আমাদের মূল কথায় রিকার্সন আসলে কিভাবে কাজ করে। যখন একটি সি প্রোগ্রাম চালানো হয় তখন মেইন ফাংশন থেকে কাজ করা শুরু করে এটা সি প্রোগ্রামিং এর নিয়ম বলা যেতে পারে। তারপরে আমরা ব্যাবহারকারী থেক n এর মান ইনপুট হিসাবে নেই। n  এর মান কে আমরা চ্যাক করে দেখতেছি যে n  এর  মান শূন্য এর ছোট কি না। যদি ছোট হয় তাহলে লজিক টি সত্য হবে আর সত্য হলে ইফ এর ভেতরে যাবে এবং আনডিফাইন্ড প্রিন্ট করবে তারপর প্রোগ্রাম টারমিনেট হয়ে যাবে। আর যদি মিথ্যা হয় তাহলে এলস এ  যাবে এবং ফ্যাক্টোরিয়াল ফাংশন কল করা হবে, কল করার সময়  তখন প্যারামিটার হিসাবে n এর মান পাস করবে যা আমরা ব্যাবহারকারী থেকে নিয়েছিলাম।


ফ্যাক্টোরিয়াল ফাংশন কল হাবার পর এই ফাংশন একটি  n নামের ভেরিয়েবল এ সে  n এর মান স্টোর করবে। এখানে  n নামে না দিয়ে আন্য নামেও আমরা ভেরিএবল ডিক্লিয়ার করাতে পারাতাম। এখন আমরা একটি কন্ডিশন দিয়েছি যে  n মান 1 আথবা n এর মান 0 হয় তাহলে রিটার্ন করবো 1। আর যদি কন্ডিশন মিথ্যা হয় তাহলে এলস এ যাবে এবং এলস এর কাজ গুলা করবে। এখন যদি খেয়াল করো এলস এর ভেতর আমরা সেই একই ফাংশন  ফ্যাক্টোরিয়াল কে কল করেছি একেই বলে রিকার্সন। এখন আমরা যখন ফ্যাক্টোরিয়াল কে কল করছি তখন n এর মান আমরা 1 কমিয়ে কল করছি ধরি, n এর মান ব্যাবহারকারী ৫ দিয়েছিলো ইনপুট হিসাবে n * factorial(n - 1)। এবার n  এর মান 4 নিয়ে আবার ফ্যাক্টোরিয়াল ফাংশন কল হবে এবার আবার কন্ডিশন (n == 1 || n == 0) চ্যাক করবে দেখবে  n এর মান 4 যা 0 ও 1 থেকে বেসি তো সর্ত্য মিথ্যা আবার সে এলস এ আসবে এবং আবার সে  ফ্যাক্টোরিয়াল কে কল করবে n * factorial(n – 1) এবং ইনপুট হিসাবে n  এর মান 1 কমিয়ে কল করবে। এবার n  এর মান 3 নিয়ে আবার ফ্যাক্টোরিয়াল ফাংশন কল হবে এবার আবার কন্ডিশন (n == 1 || n == 0) চ্যাক করবে দেখবে  n এর মান 3  যা 0 ও 1 থেকে বেসি তো সর্ত্য মিথ্যা আবার সে এলস এ আসবে এবং আবার সে  ফ্যাক্টোরিয়াল কে কল করবে n * factorial(n – 1) এবং ইনপুট হিসাবে n  এর মান 1 কমিয়ে কল করবে।  এবার n  এর মান 2  নিয়ে আবার ফ্যাক্টোরিয়াল ফাংশন কল হবে এবার আবার কন্ডিশন (n == 1 || n == 0) চ্যাক করবে দেখবে  n এর মান 2 যা 0 ও 1 থেকে বেসি তো সর্ত্য মিথ্যা আবার সে এলস এ আসবে এবং আবার সে  ফ্যাক্টোরিয়াল কে কল করবে n * factorial(n – 1) এবং ইনপুট হিসাবে n  এর মান 1 কমিয়ে কল করবে। এবার n  এর মান 1  নিয়ে আবার ফ্যাক্টোরিয়াল ফাংশন কল হবে এবার আবার কন্ডিশন (n == 1 || n == 0) চ্যাক করবে দেখবে  n এর মান 1  যা 1 এর সমান কিন্তু 0 এর সমান  না তো সত্য সত্যি রিটার্ন হিসাবে 1 ফেরত পাঠাবে ফ্যাক্টোরিয়াল ফাংশন এর কাছে।  এখানে আমরা অর গেট ব্যাবহার করেছি  যা যে কোন একটা সর্ত্য সত্য হলেই সর্ত্য সত্য হয়।

এখন এইযে যে এতো বার ফ্যাক্টোরিয়াল ফাংশন নিজেই নিজে কে কল করলো তা কিন্তু স্ট্যাকে  এর সকল ফাংশন কলের তথ্য জমা করেছে তো আমরা দেখি আসলে তা কিভাবে জমা হয়েছে তার একটি গ্রাফিক্যাল চিত্র দেখাচ্ছি।



তো তুমরা কি এই গ্রাফিক্যাল চিত্র দেখে কিছু বুঝতে পেরেছো না পারলেও সমস্যা নেই আমি বুঝিয়ে দিচ্ছি। আসলে আমাদের প্রোগ্রাম এ যতগুলা ফাংশন আছে তা যখন কল হয় তখন স্ট্যাক এ এভাবে তাদের কল করা ফাংশন গুলার ডাটা স্ট্যাক এ জমা হয়ে থাকে যখন
রিটার্ন করে কোন ফাংশন তখন তা সবার উপরের থেকে শুরু করে নিচের দিকে আসতে থাকে  এটাই হলো স্ট্যাক এর নিয়ম। যে ফাংশন কে আগে কল করা হয়েছে তা স্ট্যাক এ সবার নিচে থাকে এবং যে ফাংশন কে সবার শেষে কল করা হয়েছে সে ফাংশন এর তথ্য স্ট্যাক এর সবার উপরে থাকে এবং তাকে সবার আগে স্ট্যাক থেকে রিটার্ন করা হয় ।

Return   n * factorial(n – 1) ফাংশন রিটার্ন বর্ননা । 
        1 * 1 = 1
             2 * 1 = 2
             3 * 2 = 6
             4 * 6 = 24
             5 * 24 = 120

যখন স্ট্যাক থেকে সবার উপরের ফাংশন রিটার্ন করে n * factorial(n – 1) তখন রিটার্ন ভ্যালু 1 পাঠাচ্ছে এখানে যখন ফাংশন শেষবারের  মত কল হয় তখন 0 পাস হয়ে কল হয়। তখন একটি সর্ত্য চ্যাক করে সেটি হলো if( == 0 || n ==1) এই দুটি একটি সত্য হলেই রিটার্ন  1  হবে।  এবং n এর মান 1 তাহলে তো  1 * 1 = 1 । এভাবে স্ট্যাক এর  শেষ ফাংশন  পর্যন্ত রিটার্ন করবে যতগুলা ফাংশন স্ট্যাক এ স্টোর ছিলো। 

এখন স্ট্যাক এর উপর থেকে নিচের ২য় ফাংশন রিটার্ন করবে  n * factorial(n – 1) এখানে  n এর মান 2 তো ফাংশন কল হবার সময় 2 - 1  = 1 পাস হয়ে কল হচ্ছে  তো এখানেও কিন্তু আমাদের আগের সর্ত্য টা পূর্ন করছে তাই এখানে ও রিটার্ন হিসাবে ফাংশন ১ পাঠাবে তো এখন  n এর মান ২ এবং রটার্ন ভ্যালু 1 তাই 
2 * 1 = 2 

এখন স্ট্যাক এর উপর থেকে নিচের ৩য় ফাংশন রিটার্ন করবে  n * factorial(n – 1) এখানে  n এর মান 3  তো ফাংশন কল হবার সময় 3 - 1  = 2 পাস  হয়ে কল হচ্ছে  তো এখানে কিন্তু আমাদের আগের সর্ত্য টা আর পূর্ন করছে না তাই এখানে ও রিটার্ন হিসাবে আগের ফাংশন এর রিটার্ন ভ্যালু 2 পাঠাবে তো এখন  n এর মান 3  এবং রিটার্ন ভ্যালু 2 তাই  3 * 2 = 6 

এখন স্ট্যাক এর উপর থেকে নিচের ৪র্থ ফাংশন রিটার্ন করবে  n * factorial(n – 1) এখানে  n এর মান 4  তো ফাংশন কল হবার সময় 4 - 1 = 3 পাস  হয়ে কল হচ্ছে  তো এখানে কিন্তু আমাদের আগের সর্ত্য টা আর পূর্ন করছে না তাই এখানে ও রিটার্ন হিসাবে আগের ফাংশন এর রিটার্ন ভ্যালু 6 পাঠাবে তো এখন  n এর মান 4  এবং রিটার্ন ভ্যালু 6 তাই  4 * 6 = 24 

এখন স্ট্যাক এর উপর থেকে নিচের ৫ম ফাংশন রিটার্ন করবে  n * factorial(n – 1) এখানে  n এর মান 5  তো ফাংশন কল হবার সময় 5 - 1  = 4 পাস  হয়ে কল হচ্ছে  তো খানে কিন্তু আমাদের আগের সর্ত্য টা আর পূর্ন করছে না তাই এখানে ও রিটার্ন হিসাবে আগের ফাংশন এর রিটার্ন ভ্যালু ২৪ পাঠাবে তো এখন  n এর মান ৫  এবং রিটার্ন ভ্যালু 2 তাই  
5 * 24 = 120। সর্বশেষে বাহিরের  factorial(n – 1) এর কাছে 120 পাঠিয়ে দিবে এবাং তা মেইন ফাংশন প্রিন্ট করে প্রোগ্রাম টারমিনেট করে দিবে।  এই রিটার্ন স্টেপ টুকু এক্সট্রা লিখলাম যাতে করে তুমাদের বুঝতে সুবিধা হয়।  তুমরা নিচের লিখাটুকু পড়তে পারো। এখানে আসলে ফানশন রিটার্ন স্টেপমেন্ট নিয়ে লিখা হয়েছে। আসা করি তুমারা বুঝতে পারবে। 


এখন স্ট্যাক এর উপর থেকে এক এক করে ফাংশন রিটার্ন করা হবে, এখন N এর মান  1  এবং n * factorial(n – 1) কল করা হয়  তখন factorial(n – 1) মানে 0  পাস হয়ে কল হয় তার পর কন্ডিশন চ্যাক  if (n == 0  || n == 1) করে দেখে লজিক সত্য কি না  n এর মান
 0 == 0   হ্যা সত্য  তখন 1 রিটার্ন করে,  এখানে 1 রিটার্ন  করে স্ট্যাক এ থাকা উপরের ফাংশন এর কাছে n * factorial(n – 1) এখন  N এর মান 1 এবং রিটার্ন করা মান ও 1   
n * factorial(n – 1) →  1 * 1 =  1 (এখানে এই * এর পরের1 হলো রিটার্ন ভেলু টা ) কারন  factorial(n – 1) এখানে 0  পাস হয়ে কল হয়েছিলো  রিটার্ন করেছে 1 । এখন স্ট্যাক এ থাকা সবার উপরের প্রথম  ফাংশন টি স্ট্যাক থেকে মুছে যাবে কারন এই ফাংশন ভ্যালু রিটার্ন করে দিয়েছে।

এখন স্ট্যাক এর উপর থেকে দ্বিতীয়  ফাংশন রিটার্ন করা হবে এখন N এর মান 2  এবং n * factorial(n – 1) কল করা হয়  তখন factorial(n – 1) মানে ১  পাস হয়ে কল হয় তার পর কন্ডিশন চ্যাক  if (n == 0  || n == 1) করে দেখে লজিক সত্য কি না  n এর মান
1 == 1  হ্যা সত্য  তখন 1 রিটার্ন করে,  এখানে 1 রিটার্ন  করে স্ট্যাক এ থাকা উপরের   দ্বিতীয় ফাংশন এর কাছে n * factorial(n – 1) এখন  N এর মান 2 এবং রিটার্ন করা মান 1  
n * factorial(n – 1) →  2 * 1 =  1 (এখানে এই * এর পরের1 হলো রিটার্ন ভেলু টা ) কারন  factorial(n – 1) এখানে 1 পাস হয়ে কল হয়েছিলো  রিটার্ন করেছে 1 ।

এখন স্ট্যাক এর উপর থেকে ৩য়  ফাংশন রিটার্ন করা হবে এখন N এর মান ৩  এবং n * factorial(n – 1) কল করা হয়  তখন factorial(n – 1) মানে ২  পাস হয়ে কল হয় তার পর কন্ডিশন চ্যাক  if (n == 0  || n == 1) করে দেখে লজিক সত্য কি না  n এর মান
2 == 1  সত্য না । n * factorial(n – 1) রিটার্ন করে 2 ।  এখানে রিটান করা মান 2 এবং  n এর মান 3   n * factorial(n – 1) →  3 * 2  =  6  ।

এখন স্ট্যাক এর উপর থেকে ৪র্থ  ফাংশন রিটার্ন করা হবে এখন N এর মান 4  এবং n * factorial(n – 1) কল করা হয়  তখন factorial(n – 1) মানে 3  পাস হয়ে কল হয় তার পর কন্ডিশন চ্যাক  if (n == 0  || n == 1) করে দেখে লজিক সত্য কি না  n এর মান
3 == 1  সত্য না । n * factorial(n – 1) রিটার্ন করে 6 ।  এখানে রিটান করা মান 6 এবং  n এর মান 4   n * factorial(n – 1) →  4 * 6  =  24 ।


এখন স্ট্যাক এর উপর থেকে ৫ম  ফাংশন  রিটার্ন করা হবে এখন N এর মান 5  এবং n * factorial(n – 1) কল করা হয়  তখন factorial(n – 1) মান 4  পাস হয়ে কল হয় তার পর কন্ডিশন চ্যাক  if (n == 0  || n == 1) করে দেখে লজিক সত্য কি না  n এর মান
4 == 1  সত্য না । n * factorial(n – 1) রিটার্ন করে 24 ।  এখানে রিটান করা মান 24 এবং  n এর মান 5   n * factorial(n – 1) →  5* 24  =  120 ।

এখন স্ট্যাক থেকে সবার শেষের ফাংশন এর রিটার্ন n * factorial(n – 1) inside এর ভ্যালু factorial(n) outside ফাংশন এর কাছে পাঠিয়ে দেবে এবং তার পর তা প্রিন্ট করবে সবশেষে মেইন ফাংশন রিটার্ন করে প্রোগ্রাম টারমিনেট করে দেবে। এবং স্ট্যাক এর সব স্টোর করা ফাংশন গুলা মুছে যাবে।

বিদ্রঃ বানান বা কোন কিছু ভুল হলে আমাকে জানাতে পারো। 
Email: habibor.rahaman0101@gmail.com

লিখেছেনঃ হাবিবুর রহমান।