रिकर्सन क्या है?

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 अनुकूलन नहीं है।
- ओवरलैपिंग उप-समस्याओं को फिर से गणना करना घातांक समय तक उड़ सकता है (memoization के साथ ठीक करें)।

## यह महत्वपूर्ण क्यों है

रिकर्सन स्वाभाविक रूप से आत्म-समान समस्याओं को व्यक्त करता है — पेड़, ग्राफ, विभाजित और जीतो — लूप की तुलना में बहुत अधिक स्पष्ट रूप से।

यह merge sort, backtracking, और dynamic programming के पीछे की मानसिक मॉडल है।

कॉल स्टैक को समझना आपको डीबगिंग और मेमोरी के बारे में तर्क करने में भी बेहतर बनाता है।