মডিউল ১৭ঃ রিকার্শন

মডিউল ১৭-১ঃ Call Stack

কল স্ট্যাক" (Call Stack) হলো কম্পিউটার প্রোগ্রামিং এর একটি গুরুত্বপূর্ণ ধারণা, বিশেষ করে ফাংশন কল (function call) এর ক্ষেত্রে। C ভাষাতেও Call Stack একটি গুরুত্বপূর্ণ ভূমিকা রাখে।

কল স্ট্যাক কি?

1. কল স্ট্যাক হলো LIFO (Last In First Out) নীতি ভিত্তিক একটি ডাটা স্ট্রাকচার। এটি মূলত ফাংশন কল এর History ট্র্যাক করে রাখে।
2. প্রতিটি ফাংশন কল এর সময় তা কল স্ট্যাকে এড করে দেওয়া হয় (pushed)।
3. যখন কোন ফাংশন তার কাজ সম্পন্ন করে, তখন সেই ফাংশনের তথ্য কল স্ট্যাক থেকে মুছে ফেলা হয় (popped)।

কল স্ট্যাক C ভাষায় কিভাবে কাজ করে?

উদাহরণ:

Code:

#include <stdio.h>

void func2() {
 printf("I am func2\n");
}
void func1() {
 func2();
 printf("I am func1\n");
}
int main() {
 func1();
 printf("I am main funciton\n");
 return 0;
}

এই উদাহরণে, main ফাংশন func1 কে কল করে। func1 ফাংশনটি func2 কে কল করে। কল স্ট্যাক এই ফাংশন কলগুলো ট্র্যাক করে রাখে।

Output:

I am func2
I am func1
I am main funciton

Call Stack:

প্রথমে main ফাংশন কল স্ট্যাকে push হয়। তারপর main থেকে func1 কল হলে func1 push হয়। func1 থেকে func2 কল হলে func2 push হয়। func2 এর কাজ শেষ হলে func2 pop হয়, তারপর func1 এর কাজ শেষ হলে func1 pop হয়, এবং সবশেষে main এর কাজ শেষ হলে main pop হয়।

---

মডিউল ১৭-২ + ১৭-৩: রিকার্সন

রিকার্সন (Recursion) কি?

রিকার্সন হলো এমন একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেকেই কল করে। এটি সাধারণত সমস্যা সমাধানের জন্য ব্যবহৃত হয় যা সাব-প্রবলেম (sub-problem) থেকে গঠিত।

রিকার্সন কিভাবে কাজ করে:

1. বেস কেস (Base Case): রিকার্সিভ ফাংশনে এমন একটি শর্ত থাকতে হবে যা রিকার্সন বন্ধ করে দেয়। এই শর্তকে "বেস কেস" বলা হয়।
2. রিকার্সিভ কল (Recursive Call): রিকার্সিভ ফাংশন নিজেকেই নিজে কল করে, এবং কল করা ফাংশনটি মূল ফাংশনের সাব-প্রবলেম সমাধান করে।
3. সমাধান একত্রিত করা (Combining Solutions): রিকার্সিভ কল থেকে ফেরত আসার পর, মূল ফাংশন সাব-প্রবলেমের সমাধানগুলো একত্রিত করে সামগ্রিক সমাধান তৈরি করে।

উদাহরণ:

Code:

#include <stdio.h>
void fun(int i, int n)
{
    if(i==n+1) return; // বেস কেস
    printf("%d\n", i);
    fun(i+1, n);  // রিকার্সিভ কল
}
int main()
{
    int n;
    scanf("%d", &n);
    fun(1, n);
    return 0;
}

এই কোডে fun ফাংশনটি নিজেকেই কল করছে। এটি ১ থেকে n পর্যন্ত সংখ্যা প্রিন্ট করবে। বেস কেস হলো যখন i এর মান n+1 এর সমান হয়, তখন ফাংশনটি return করে এবং রিকার্সন বন্ধ হয়ে যায়।

---

মডিউল ১৭-৪ + ১৭-৫: Print From 1 to n Using Recursion

Code:

#include <stdio.h>
void fun(int i, int n)
{
    if(i==n+1) return; // Base case
    printf("%d\n", i);
    fun(i+1, n);
}
int main()
{
    int n;
    scanf("%d", &n);
    fun(1, n);
    return 0;
}

যদি n=3 হয়, তাহলে প্রোগ্রাম যেভাবে কাজ করবে তা নিচে দেখানো হলো:

1. scanf("%d", &n); দ্বারা প্রোগ্রাম n এর মান প্রাপ্ত করে। এখানে n=3 হলে, এটি একেবারে নিচের মতো হবে:

n = 3

2. fun(1,n); কল হবে এবং সাথে দুটি আর্গুমেন্ট পাঠানো হবে i=1 এবং n=3।

3. fun() ফাংশনের মধ্যে, i=1 এবং n=3 হিসেবে প্যারামিটার পাস হয়েছে।

4. শুরুতে ফাংশনের ভেতরে যাওয়া হবে if(i==n+1) return; শর্ত চেক করে, যে যদি i এর মান n+1 এর সমান হয়, তাহলে ফাংশন থেকে বের হয়ে যাওয়া হবে। এখানে i=1 এবং n=3, সুতরাং এই শর্ত পূরণ হবে না।

5. পরবর্তী লাইন printf("%d\n",i); দ্বারা i এর মান 1 প্রিন্ট করা হবে এবং নতুন লাইনে চলে আসবে। এই সময় আউটপুট হবে:

1

6. পরবর্তী লাইনে, fun(i+1,n); দ্বারা ফাংশনকে নিজেকে নিজের মধ্যে কল করা হবে প্যারামিটার i এর মান এক বাড়িয়ে এবং এই সময় i=2 হবে।

7. আবার ফাংশনে প্রবেশ হবে, এবং এইবার প্রথম লাইনের শর্ত চেক হবে। যে প্রথম আগের প্রোগ্রামে এই শর্ত পূরণ হবে না।

8. এখন printf("%d\n",i); লাইনে i এর মান 2 প্রিন্ট হবে এবং নতুন লাইনে চলে আসবে। আউটপুট হবে:

1
2

9. আবার ফাংশনকে কল করে i এর মান 3 প্রিন্ট হবে এবং ফাংশন থেকে বের হয়ে আসা হবে কারণ i এর মান এখন n+1 এর সমান হয়েছে। আউটপুট হবে:

1
2
3

10. সবশেষে, মেইন ফাংশনে রিটার্ন ০ করে প্রোগ্রাম শেষ হবে।

---

মডিউল ১৭-৬ + ১৭-৭ + ১৭-৮: Print From 5 to 1 using Recursion

কোডঃ

Code:

#include <stdio.h>
void fun(int i)
{
    // base case
    if(i==0) return;
    printf("%d\n", i);
    fun(i-1);
}
int main()
{
    fun(5);
    return 0;
}

এই প্রোগ্রামটি একটি সিম্পল রিকার্সিভ ফাংশন ব্যবহার করে একটি নির্দিষ্ট সংখ্যার পর্যন্ত পূর্ণসংখ্যাগুলি প্রিন্ট করে। এটির প্রোগ্রামের কাজ নিম্নলিখিত:

1. fun() ফাংশনটি নেওয়া হলো একটি পূর্ণসংখ্যা i এর মান নিয়ে।
2. যদি i এর মান 0 হয়, অর্থাৎ যদি i এর মান নিকটতম বেস কেস হয়, তবে ফাংশন থেকে বাহির হতে হবে। এই ধরণের কেস হলো বেস কেস বা মৌলিক কেস।
3. যদি i এর মান 0 না হয়, তবে একটি লাইন প্রিন্ট করা printf("%d\n",i); এবং একটি রিকার্সিভ কল করা হবে fun(i-1); যেখানে i-1 হচ্ছে এই ফাংশনের আর্গুমেন্ট এবং এই রিকার্সিভ কল মাধ্যমে আমরা সংখ্যাগুলি ক্রমিকভাবে কমাতে থাকব।
4. প্রথমে ফাংশন কল হওয়ার সময়, সংখ্যা 5 প্রিন্ট করা হবে, এবং তারপরে সিস্টেম একটি রিকার্সিভ কল করে i-1=4 এর সাথে ফাংশনটি কল করবে।
5. পরের ধাপে, ফাংশন আবার কল হবে এবং সংখ্যা 4 প্রিন্ট করা হবে, এবং পরের সংখ্যা 3 এর জন্য আবার একটি রিকার্সিভ কল করা হবে।
6. এই পদক্ষেপ প্রক্রিয়া চলবে যতক্ষণ না i এর মান 0 হয়ে যায়। এই রিকার্সিভ কলের প্রতিটি সময় i এর মান 0 না হয়ে গেলে, তার আগের সংখ্যা প্রিন্ট হবে এবং সে সংখ্যার জন্য আবার একটি রিকার্সিভ কল করা হবে যার মান এক কম।
7. সবশেষে, যখন i এর মান 0 হয়ে যাবে, ফাংশন থেকে বের হতে হবে এবং মেইন ফাংশনে রিটার্ন ০ করে প্রোগ্রাম শেষ হবে।

এই রিকার্সিভ ফাংশনটি ব্যবহার করে আমরা একে একে সংখ্যাগুলি প্রিন্ট করে একে একে কমিয়ে যাচ্ছি। তার ফলে আমরা প্রথমে 5 থেকে শুরু করে 1 পর্যন্ত সংখ্যা প্রিন্ট করতে পারব।

---

মডিউল ১৭-৯ + ১৭-১০: প্রিন্টিং এরে উসিং রিকার্শন

রিকার্শন ব্যবহার করে অ্যারে প্রিন্ট করা

আমরা রিকার্শন (recursion) ব্যবহার করে একটি অ্যারে প্রিন্ট করার প্রোগ্রাম দেখব। নিচে সি প্রোগ্রামিং ভাষায় লেখা কোডটি দেওয়া হলো, যার প্রতিটি লাইনের বিস্তারিত ব্যাখ্যা দেওয়া হয়েছে।

কোড

Code:

#include <stdio.h>

void print_array(int a[], int n, int i)
{
if (i == n)
{
return;
}
printf("%d\n", a[i]);
print_array(a, n, i + 1);
}

int main()
{
int n;
scanf("%d", &n);
int a[n];
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}

print_array(a, n, 0);

return 0;
}

লাইন বাই লাইন ব্যাখ্যা

১. #include <stdio.h>

• এটি একটি হেডার ফাইল, যা ইনপুট-আউটপুট ফাংশন (printf, scanf ইত্যাদি) ব্যবহারের জন্য প্রয়োজন।

২. void print_array(int a[], int n, int i)

• এখানে print_array নামে একটি রিকার্সিভ ফাংশন ডিক্লেয়ার করা হয়েছে।
• প্যারামিটার হিসেবে নেয়:
• int a[]: একটি ইন্টিজার অ্যারে।
• int n: অ্যারের সাইজ।
• int i: বর্তমান ইনডেক্স, যেখান থেকে প্রিন্ট শুরু হবে।

৩. if (i == n) { return; }

• এটি বেস কেস (base case) চেক করে।
• যদি i অ্যারের সাইজ n-এর সমান হয়, তাহলে রিকার্শন থেমে যায় এবং ফাংশন থেকে বের হয়ে আসে।

৪. printf("%d\n", a[i]);

• অ্যারের i-তম ইনডেক্সের ভ্যালু প্রিন্ট করে।

৫. print_array(a, n, i + 1);

• ফাংশন নিজেকে আবার কল করে, কিন্তু এবার i + 1 ইনডেক্স দিয়ে।
• এভাবে রিকার্সিভলি পরবর্তী ইনডেক্সের ভ্যালু প্রিন্ট হয়।

৬. int main()

• প্রোগ্রামের মূল ফাংশন, যেখান থেকে এক্সিকিউশন শুরু হয়।

৭. int n; scanf("%d", &n);

• ইউজার থেকে ইনপুট নেয় n-এর মান (অ্যারের সাইজ)।

৮. int a[n];

• n সাইজের একটি ইন্টিজার অ্যারে ডিক্লেয়ার করা হয়েছে।

৯. for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }

• লুপ ব্যবহার করে ইউজার থেকে অ্যারের প্রতিটি এলিমেন্ট ইনপুট নেওয়া হয়।

১০. print_array(a, n, 0);

• print_array ফাংশন কল করা হয়, যার শুরু ইনডেক্স 0, এখান থেকে রিকার্সিভ প্রিন্টিং শুরু হয়।

১১. return 0;

• প্রোগ্রাম সফলভাবে শেষ হয়েছে বোঝাতে 0 রিটার্ন করা হয়।

উদাহরণ

ইনপুট:

5
10 20 30 40 50

আউটপুট:

10
20
30
40
50