# Recursion — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/recursion

> एक फ़ंक्शन जो छोटे इनपुट पर खुद को बुलाकर समस्या हल करता है।

## Base case + recursive case

हर recursion को चाहिए (1) **base case** जो बिना recurse किए लौटे, और (2) **recursive case** जो base की ओर प्रगति करे। Base case चूकें और stack overflow मिलता है।

## Call stack खुलता है

`factorial(3)` `factorial(2)` की प्रतीक्षा करता है जो `factorial(1)` की। फिर परिणाम वापस गुणा होते हैं।

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

# factorial(3)
# = 3 * factorial(2)
# = 3 * (2 * factorial(1))
# = 3 * (2 * 1) = 6
```

## रूसी गुड़िया

एक गुड़िया खोलें तो अंदर छोटी, जब तक छोटी ठोस (base case) न मिले। फिर उन्हें क्रम में बंद करें।

## Recursion → iteration

किसी भी recursion को स्पष्ट stack से फिर से लिखा जा सकता है। Tail recursion और दोहराए उप-समस्याएँ (Fibonacci) memoise या bottom-up जाने के संकेत हैं।