રિકર્ઝન શું છે?

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)** સ્ટેક સ્પેસ (દરેક કૉલ પર એક ફ્રેમ)।

## તોટલીવાળા

- **બેઝ કેસ અપાયો** -> અનંત રિકર્ઝન -> સ્ટેક ઓવરફ્લો।
- ઊંડું રિકર્ઝન સ્ટેકને ખતમ કરી શકે છે; કેટલીક ભાષાઓમાં ટેલ-કૉલ ઓપ્ટિમાઇઝેશન નથી।
- ઓવરલેપિંગ સબપ્રોબલમ્સને ફરીથી કમ્પ્યુટ કરવું exponential સમય સુધી વધી શકે છે (મેમોઇઝેશન સાથે ઠીક કરો)।

## શા માટે તે મહત્વપૂર્ણ છે

રિકર્ઝન પ્રાકૃતિક રીતે આત્મ-સમાન સમસ્યાઓ વ્યક્ત કરે છે — વૃક્ષો, ગ્રાફ્સ, વિભાજિત અને વજન — લૂપ્સ કરતાં ઘણું વધુ સ્વચ્છ રીતે।

યह merge sort, backtracking, અને dynamic programming પાછળ માનસિક મોડલ છે।

કૉલ સ્ટેક સમજવું તમને ડીબગિંગ અને મેમરી વિશે તર્ક આપવા માટે વધુ સારું બનાવે છે।