ਰਿਕਰਸ਼ਨ ਕੀ ਹੈ?

Question

ਰਿਕਰਸ਼ਨ ਕੀ ਹੈ?

Accepted Answer

**ਰਿਕਰਸ਼ਨ** ਇਹ ਹੈ ਕਿ ਜਦੋਂ ਇੱਕ ਫੰਕਸ਼ਨ ਆਪਣੇ ਆਪ ਨੂੰ ਕਾਲ ਕਰਦਾ ਹੈ ਤਾਂ ਉਹੀ ਸਮਸਿਆ ਦਾ ਛੋਟਾ ਸੰਸਕਰਣ ਹੱਲ ਕਰਨ ਲਈ। ਹਰ ਰਿਕਰਸ਼ਨ ਨੂੰ ਇੱਕ **base case** ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜੋ ਇਸ ਨੂੰ ਰੋਕਦਾ ਹੈ ਅਤੇ ਇੱਕ **recursive case** ਜੋ ਬੇਸ ਵੱਲ ਵਧਦਾ ਹੈ।

## ਵਿਚਾਰ

ਇੱਕ ਸਮਸਿਆ ਨੂੰ ਛੋਟੀਆਂ ਸਮਾਨ ਉਪ-ਸਮਸਿਆਵਾਂ ਵਿੱਚ ਵੰਡੋ। ਹਰ ਕਾਲ **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 ਨਹੀਂ ਹੈ।
- ਓਵਰਲੈਪਿੰਗ subproblems ਨੂੰ ਦੁਬਾਰਾ ਕੰਪਿਊਟ ਕਰਨਾ exponential ਸਮੇਂ ਤੱਕ ਫੁੱਲ ਸਕਦਾ ਹੈ (memoization ਨਾਲ ਠੀਕ ਕਰੋ)।

## ਇਹ ਮਹੱਤਵਪੂਰਣ ਕਿਉਂ ਹੈ

Rekursion ਕੁਦਰਤੀ ਤੌਰ ਉੱਤੇ ਆਪਣੇ ਜਿਹੇ ਸਮਸਿਆਵਾਂ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ — ਪੇੜ, ਗ੍ਰਾਫ, divide ਅਤੇ conquer — ਲੂਪਸ ਤੋਂ ਬਹੁਤ ਸਾਫ ਢੰਗ ਨਾਲ।

ਇਹ merge sort, backtracking, ਅਤੇ dynamic programming ਦੇ ਪਿੱਛੇ ਮਾਨਸਿਕ ਮਾਡਲ ਹੈ।

Call stack ਨੂੰ ਸਮਝਣਾ ਤਿਹਾੜ ਨੂੰ debug ਕਰਨ ਅਤੇ ਮੈਮੋਰੀ ਬਾਰੇ ਸੋਚ ਵਿਚ ਬਿਹਤਰ ਬਣਾਉਂਦਾ ਹੈ।