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

Question

Accepted Answer

**রিকার্সন (Recursion)** হল যখন একটি ফাংশন একই সমস্যার একটি ছোট সংস্করণ সমাধান করার জন্য নিজেকে ডাকে। প্রতিটি রিকার্সনের একটি **বেস কেস (base case)** দরকার যা এটি থেমে দেয় এবং একটি **রিকার্সিভ কেস (recursive case)** যা বেস কেসের দিকে এগিয়ে যায়।

## ধারণা

কোনো সমস্যাকে ছোট অভিন্ন উপসমস্যায় ভাগ করুন। প্রতিটি কল **কল স্ট্যাক (call stack)**-এ একটি ফ্রেম ঠেলে দেয়; রিটার্নগুলি সেগুলি পপ করে।

## উদাহরণ

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## ট্রেস

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## জটিলতা

এখানে **O(n)** সময় এবং **O(n)** স্ট্যাক স্পেস (প্রতিটি কলের জন্য এক ফ্রেম)।

## সমস্যা

- **বেস কেস মিসিং** -> অসীম রিকার্সন -> স্ট্যাক ওভারফ্লো।
- গভীর রিকার্সন স্ট্যাক শেষ করতে পারে; কিছু ভাষা tail-call অপ্টিমাইজেশন ছাড়ে।
- ওভারল্যাপিং সাবপ্রবলেম পুনরায় গণনা করা সূচকীয় সময়ে যেতে পারে (memoization দিয়ে ঠিক করুন)।

## কেন এটি গুরুত্বপূর্ণ

রিকার্সন স্বাভাবিকভাবে স্ব-সমরূপ সমস্যা প্রকাশ করে — গাছ, গ্রাফ, বিভক্ত এবং জয় — লুপের চেয়ে অনেক বেশি পরিষ্কারভাবে।

এটি merge sort, ব্যাকট্র্যাকিং এবং ডায়নামিক প্রোগ্রামিং এর পিছনের মানসিক মডেল।

কল স্ট্যাক বোঝা আপনাকে ডিবাগিং এবং মেমরি সম্পর্কে যুক্তি করতেও ভালো করে তোলে।