Data Structure: Recursion (Definition, Advantages and Limitations)

Recursion হলো এমন একটি পদ্ধতি যেখানে একটি function নিজেকেই বারবার call করে একটি সমস্যার সমাধান করে। এটি programming-এর একটি গুরুত্বপূর্ণ ধারণা।

---

১. Recursion কী?

Recursion হলো এমন একটি process যেখানে একটি function নিজেকেই call করে যতক্ষণ না একটি নির্দিষ্ট condition পূরণ হয়।

সহজভাবে:

Function নিজেকে call করে → Problem ছোট হয় → শেষ পর্যন্ত solution পাওয়া যায়

---

২. Base Case এবং Recursive Case

Recursion-এর দুইটি গুরুত্বপূর্ণ অংশ:

• Base Case → যেখানে recursion বন্ধ হয়
• Recursive Case → যেখানে function নিজেকে call করে

---

৩. Example: Factorial Program

#include <stdio.h>

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

int main() {
    int result = factorial(5);
    printf("Factorial = %d", result);
    return 0;
}

---

৪. Recursion কীভাবে কাজ করে?

Example: factorial(3)

factorial(3)
= 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1 * factorial(0)
= 3 * 2 * 1 * 1
= 6

এখানে function বারবার নিজেকে call করে এবং শেষে base case-এ এসে থামে।

---

৫. Recursion-এর সুবিধা (Advantages)

• ✔ Code সহজ এবং ছোট হয়
• ✔ Complex problem সহজে solve করা যায়
• ✔ Divide and conquer technique-এ ব্যবহার হয়
• ✔ Tree, graph, sorting algorithm-এ ব্যবহার হয়

---

৬. Recursion-এর সীমাবদ্ধতা (Limitations)

• ❌ বেশি memory ব্যবহার করে (stack memory)
• ❌ slow হতে পারে
• ❌ base case না দিলে infinite loop হবে
• ❌ debugging কঠিন

---

৭. Recursion vs Loop

বিষয়	Recursion	Loop
Structure	Function call	Iteration
Memory	বেশি লাগে	কম লাগে
Code	ছোট ও সহজ	বড় হতে পারে

---

৮. বাস্তব জীবনের উদাহরণ

• Mirror reflection (আয়নায় আয়না)
• Russian dolls (একটার ভিতরে আরেকটা)

---

উপসংহার

Recursion একটি powerful technique যা complex problem সহজভাবে সমাধান করতে সাহায্য করে। তবে এটি ব্যবহারের সময় base case নিশ্চিত করা এবং memory usage মাথায় রাখা জরুরি।

---

Quick Revision

• Recursion → function নিজেকে call করে
• Base case → stopping condition
• Recursive case → repeat call
• Advantage → code সহজ
• Limitation → memory বেশি লাগে