Recursion भनेको के हो?

Question

Accepted Answer

**Recursion** भनेको फंक्शनले आफैलाई कल गरेर एकै समस्याको सानो संस्करण समाधान गर्ने प्रक्रिया हो। प्रत्येक recursion को **base case** हुनुपर्छ जसले यसलाई रोक्छ र **recursive case** हुनुपर्छ जसले base तिरफ अग्रसर हुन्छ।

## विचार

एक समस्यालाई सानो समान उप-समस्याहरूमा विभाजन गर्नुहोस्। प्रत्येक कल **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)** stack स्पेस (एक कल प्रति फ्रेम)।

## समस्याहरू

- **Missing base case** -> अनन्त recursion -> stack overflow।
- गहिरो recursion ले stack समाप्त गर्न सक्छ; केही भाषाहरूमा tail-call optimization अभाव छ।
- Overlapping subproblems को पुनः गणना exponential समयमा वृद्धि गर्न सक्छ (memoization को साथ ठीक गर्नुहोस्)।

## किन महत्त्वपूर्ण छ

Recursion ले स्वाभाविक रूपमा आत्म-समान समस्याहरू - अनार, ग्राफ, divide and conquer - लूपहरू भन्दा धेरै सफलतापूर्वक व्यक्त गर्छ।

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

Call stack बुझ्नुले तपाईलाई debugging र memory को बारेमा तर्क गर्न बेहतर बनाउँछ।