ما هي العودية (Recursion)؟

Question

Accepted Answer

**العودية (Recursion)** هي عندما تستدعي دالة نفسها لحل نسخة أصغر من نفس المشكلة. كل عودية تحتاج إلى **حالة أساسية (base case)** توقفها و**حالة عودية (recursive case)** تتحرك نحو الحالة الأساسية.

## الفكرة

قسّم المشكلة إلى مشاكل جزئية متطابقة أصغر. كل استدعاء يدفع إطاراً (frame) على **مكدس الاستدعاءات (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)** مساحة المكدس (إطار واحد لكل استدعاء).

## المخاطر

- **حالة أساسية مفقودة** -> عودية لا نهائية -> تجاوز مكدس.
- العودية العميقة قد تستنزف المكدس؛ بعض اللغات تفتقر إلى تحسين الاستدعاء الطرفي (tail-call optimization).
- إعادة حساب المشاكل الجزئية المتداخلة قد يصل إلى وقت أسي (أصلحه باستخدام memoization).

## لماذا يهم

تعبّر العودية بشكل طبيعي عن المشاكل ذاتية التشابه — الأشجار والرسوم البيانية وفرق تسد — بشكل أنظف بكثير من الحلقات.

هي النموذج الذهني وراء merge sort والتراجع (backtracking) والبرمجة الديناميكية.

فهم مكدس الاستدعاءات يجعلك أيضاً أفضل في تصحيح الأخطاء والتفكير حول الذاكرة.