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

Question

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

IT Interview Practice · 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 मागील मानसिक मॉडेल आहे.

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

कल्पना

उदाहरण

ट्रेस

जटिलता

त्रुटी

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

संबंधित प्रश्न