16. Recursion - Fundamentals

রিকার্সন (Recursion) হলো এমন একটি পদ্ধতি যেখানে একটি ফাংশন নিজেকে নিজেই কল (Call) করে। এটি বড় এবং জটিল সমস্যাগুলোকে ছোট ছোট সাব-প্রবলেমে (Sub-problems) ভাগ করে সমাধান করার জন্য ব্যবহার করা হয়।

---

1. রিকার্সন কি? (What is Recursion?)

সহজ কথায়, একটি ফাংশন যখন তার নিজের ডেফিনিশনের ভেতরে নিজেকেই কল দেয়, তখন তাকে রিকার্সন বলে। এটি মূলত লুপের বিকল্প হিসেবে কাজ করতে পারে।

🛠 রিকার্সনের মূল অংশ (Core Parts)

রিকার্সন সাধারণত দুটি প্রধান অংশের ওপর নির্ভর করে:

1. Base Case: যা রিকার্সন লুপটি থামিয়ে দেয়। এটি না থাকলে ফাংশনটি অনন্তকাল চলতে থাকবে (Infinite Recursion)।
2. Recursive Case: যেখানে ফাংশনটি নিজেকে ডিফারেন্ট ইনপুট দিয়ে পুনরায় কল দেয়।

---

2. বেস কেস এবং রিকার্সিভ কেস (Example)

ধরা যাক, আমরা একটি সংখ্যার ফ্যাক্টোরিয়াল (Factorial) বের করব।
গাণিতিকভাবে: n! = n * (n-1)! এবং 0! = 1

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. চেক করুন n == 0 কি না?

• যদি হ্যাঁ হয়, তবে ১ রিটার্ন করুন (Base Case)।

2. যদি না হয়, তবে n * factorial(n - 1) রিটার্ন করুন (Recursive Case)।

Java Implementation

public int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1); // Recursive case
}

Python Implementation

def factorial(n):
    if n == 0: return 1 # Base case
    return n * factorial(n - 1) # Recursive case

---

3. কল স্ট্যাক (Call Stack)

ফাংশন যখন রিকার্সিভলি কল হয়, তখন কম্পিউটার মেমরিতে একটি Stack মেইনটেইন করে। প্রতিটি ফাংশন কল স্ট্যাকের উপরে জমা হতে থাকে। যখন বেস কেসে পৌঁছায়, তখন স্ট্যাক থেকে একটি একটি করে কল সম্পন্ন হয়ে ফিরে আসে।

---

4. রিকার্সনের প্রকারভেদ (Types of Recursion)

Direct vs Indirect Recursion

• Direct Recursion: ফাংশন A যখন সরাসরি ফাংশন A-কেই কল করে।
• Indirect Recursion: ফাংশন A যখন ফাংশন B-কে কল করে এবং ফাংশন B আবার ফাংশন A-কে কল করে।

টেইল রিকার্সন (Tail Recursion)

যদি রিকার্সিভ কলটি ফাংশনের একদম শেষ কাজ হয় (এরপর আর কোনো অপারেশন না থাকে), তবে তাকে টেইল রিকার্সন বলে। এটি মেমরি ব্যবহারে অনেক দক্ষ।

---

5. স্ট্যাক ওভারফ্লো (Stack Overflow)

যদি রিকার্সন কোনো বেস কেস ছাড়া চলতে থাকে অথবা ইনপুট সাইজ মেমরির লিমিটের চেয়ে বড় হয়, তবে Stack Overflow এরর দেখা দেয়। এর মানে হলো কল স্ট্যাকের জন্য বরাদ্দ মেমরি শেষ হয়ে গেছে।

---

6. রিকার্সন ট্রি (Recursion Tree)

রিকার্সন কীভাবে কাজ করছে তা বোঝার জন্য রিকার্সন ট্রি সবচেয়ে কার্যকর পদ্ধতি। ফিবোনাচ্চি (Fibonacci) সিরিজের ক্ষেত্রে এটি এমন দেখায়:

       f(4)
      /    \
    f(3)   f(2)
   /   \   /   \
 f(2) f(1) f(1) f(0)

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: এটি মূলত কতবার ফাংশনটি কল হচ্ছে তার ওপর নির্ভর করে। ফ্যাক্টোরিয়ালের জন্য এটি O(n) এবং ফিবোনাচ্চির জন্য O(2ⁿ)।
• Space Complexity: O(n) - কল স্ট্যাকের মেমরি ব্যবহারের জন্য।

---

7. রিকার্সন কখন ব্যবহার করবেন? (When to use)

• যখন সমস্যাটি ছোট সাব-প্রবলেমে ভাগ করা যায়।
• ট্রি (Tree) বা গ্রাফ (Graph) ট্রাভার্সাল করার সময়।
• ডিভাইড অ্যান্ড কনকোয়ার (Divide and Conquer) অ্যালগরিদমে।

IMPORTANT

সব রিকার্সিভ সমস্যার একটি ইটারেটিভ (Loop) সমাধানও থাকে। তবে রিকার্সন কোড অনেক সময় বেশি পরিচ্ছন্ন এবং পড়তে সহজ করে তোলে।

---

TIP

রিকার্সন শেখার সময় সব সময় একটি খাতা-কলমে রিকার্সন ট্রি একে সেটি কীভাবে মেমরিতে কাজ করছে তা বোঝার চেষ্টা করুন।