रिकर्सन म्हणजे काय?

Question

रिकर्सन म्हणजे काय?

Accepted Answer

**रिकर्सन** हे असते जेव्हा एक फंक्शन समान समस्येच्या लहान आवृत्तीचे समाधान करण्यासाठी स्वतःला कॉल करते. प्रत्येक रिकर्सनला **बेस केस** आवश्यक आहे जो ते थांबवतो आणि **रिकर्सिव केस** ज्याचा आधार बेस केसकडे जातो.

## कल्पना

एक समस्या लहान एकसारख्या सबप्रॉब्लेम्समध्ये विभाजित करा. प्रत्येक कॉल **कॉल स्टॅकवर** एक फ्रेम पुश करतो; रिटर्न त्यांना पॉप करतात.

## उदाहरण

```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 optimization नाही.
- ओव्हरलॅपिंग सबप्रॉब्लेम्सची पुनर्गणना घातांकीय वेळेपर्यंत ती सकते (memoization सह दुरुस्त करा).

## हे महत्त्वाचे का आहे

रिकर्सन स्वाभाविकपणे स्व-समान समस्या व्यक्त करते — झाडे, आलेख, विभाजन आणि विजय — लूप्सपेक्षा बरेच स्वच्छपणे.

हे merge sort, backtracking, आणि dynamic programming मागील मानसिक मॉडेल आहे.

कॉल स्टॅक समजून घेणे तुम्हाला डीबगिंग आणि मेमरी बद्दल कारणे देण्यात अधिक चांगले बनवते.