تکراری کال (Recursion) کیا ہے؟

Question

Accepted Answer

**تکراری کال (Recursion)** وہ ہے جب کوئی فنکشن اپنے آپ کو کال کرے تاکہ اسی مسئلے کے ایک چھوٹے ورژن کو حل کرے۔ ہر تکراری کال کے لیے **بیس کیس** ضروری ہے جو اسے روک دے اور **تکراری کیس** جو بیس کی طرف بڑھے۔

## نظریہ

کسی مسئلے کو چھوٹے ایک جیسے سب مسائل میں تقسیم کریں۔ ہر کال **call stack** پر ایک frame کو push کرتا ہے؛ returns انہیں pop کرتے ہیں۔

## مثال

```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
```

## Trace

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexity

یہاں **O(n)** وقت اور **O(n)** stack space (ہر کال کے لیے ایک frame)۔

## خطرات

- **بیس کیس غائب ہو** -> لامحدود تکراری کال -> stack overflow۔
- گہری تکراری کال stack کو ختم کر سکتی ہے؛ کچھ languages میں tail-call optimization نہیں ہے۔
- overlapping subproblems کو دوبارہ شمار کرنا exponential وقت تک جا سکتا ہے (memoization سے ٹھیک کریں)۔

## اہمیت

تکراری کال خود سے ملتے جلتے مسائل کو قدرتی طریقے سے ظاہر کرتا ہے — درخت، گراف، divide and conquer — بہت زیادہ صاف ستھرے انداز میں loops سے۔

یہ merge sort، backtracking، اور dynamic programming کے پیچھے کا ذہنی نمونہ ہے۔

call stack کو سمجھنا آپ کو debugging اور memory کے بارے میں سوچنے میں بہتر بناتا ہے۔