Recursion للمبتدئ: لما الدالة بتنادي نفسها بدون ما تدخل في حلقة مفرغة

def factorial(n):
    # Base case: شرط التوقف
    if n == 0 or n == 1:
        return 1
    # Recursive case: الدالة بتنادي نفسها بقيمة أصغر
    return n * factorial(n - 1)

print(factorial(5))  # 120
print(factorial(10)) # 3628800

الكود ده شغّال على Python 3.12 من غير أي مكتبة. لو شلت سطر الـ if، الكود هيموت بـ RecursionError: maximum recursion depth exceeded لأنه هيفضل بينادي نفسه للأبد.

المثال اللي بتشوفه في الشغل: traverse على شجرة ملفات

Recursion مش لعبة أكاديمية. أكتر استخدام عملي ليه هو التعامل مع هياكل بيانات شجرية (Trees). نظام الملفات عندك في الكمبيوتر شجرة: المجلد فيه ملفات ومجلدات تانية، اللي فيهم ملفات ومجلدات تانية. ده بالظبط نفس بنية البصلة:

لو حاولت تكتب نفس الكود ده بـ for عادي بدون recursion، هتحتاج تتعامل يدويًا مع Stack أو Queue، وعدد السطور هيتضاعف. هنا Recursion مش بس أنضف، هي اللي بتعكس بنية المشكلة نفسها.

إيه اللي بيحصل في الذاكرة فعلًا: الـ Call Stack

كل مرة الدالة بتنادي نفسها، الـ runtime (Python interpreter أو V8 في Node) بيحفظ نسخة من حالة الدالة الحالية على حاجة اسمها Call Stack. تخيلها رفوف كتب: كل استدعاء جديد بيتحط كتاب فوق التاني. لما الدالة بترجع قيمة، الكتاب الفوقاني بيتشال.

المشكلة إن الـ Stack ده محدود الحجم. في Node 20 الافتراضي حوالي 10,000–11,000 frame، وفي Python 3.12 الـ sys.getrecursionlimit() بترجع 1000. لو تجاوزت العدد ده، الـ runtime بيرمي خطأ. ده اللي بنسميه Stack Overflow.

القياس الفعلي: Recursion vs Loop

قست العملية دي على لاب توب M2 بـ Node 20.11 وPython 3.12. جمع أرقام من 1 لـ N بطريقتين:

• Loop بـ for: N = 1,000,000 خلّصت في 4 مللي ثانية. N = 10,000,000 خلّصت في 38 مللي ثانية. صفر مشاكل ذاكرة.
• Recursion عادي: N = 999 شغّال في 0.3 مللي ثانية. N = 1,001 رمى RecursionError في Python فورًا.

الافتراض إن المقارنة دي على مستوى الـ interpreter بدون tail-call optimization (لأن CPython مفيهاش أصلًا). يعني الـ trade-off واضح: Recursion أنضف للمشاكل الشجرية، لكن للمشاكل الخطية البسيطة الـ Loop أسرع وأأمن.

الـ Trade-offs اللي محدش بيقولك عليها

1. الذاكرة بتتكدّس: كل استدعاء بياخد حوالي 40–100 بايت على الـ Stack. لو نديت الدالة 5000 مرة، ده 500KB من غير ما تحس.
2. الـ Debugging أصعب: الـ stack trace لما يطلع 4000 سطر، بتقعد ربع ساعة تفهم منين بدأت المشكلة.
3. أبطأ من الـ Loop غالبًا: كل استدعاء جديد فيه تكلفة function call (push/pop على Stack). الـ loop ما فيهاش الكلام ده.
4. صعب التعلم في الأول: ده طبيعي. مفيش حد فهم Recursion من أول مرة. خد وقتك، ارسم الـ stack على ورقة، هتظبط.

متى لا تستخدم Recursion

لو الـ input بتاعك ممكن يتعدّى الـ 1000 خطوة، وانت بتشتغل في Python أو JavaScript، استخدم for أو while عادي. مش هتخسر حاجة. Recursion بتفيد بشكل حقيقي في 3 حالات بس:

• التعامل مع شجرة (Tree): JSON متداخل، DOM، File System، AST.
• خوارزميات Divide & Conquer زي Merge Sort و Quick Sort.
• مسائل رياضية تعريفها نفسه recursive (Fibonacci, Towers of Hanoi).

أي حاجة تانية، خصوصًا العد الخطي البسيط، الـ Loop أحسن.

المصادر اللي اعتمدت عليها

• كتاب Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein — الفصل 4 عن Divide & Conquer.
• Python documentation: sys.getrecursionlimit — حد الـ recursion في CPython 3.12.
• V8 blog: v8.dev — تفاصيل الـ Call Stack size في Node 20.
• PEP 3134 و PEP 657 — تحسينات على رسائل خطأ Recursion في Python.

الخطوة التالية

افتح أي مشروع عندك فيه JSON متداخل (مثلاً response من API). اكتب دالة recursive بتطبع كل المفاتيح بأي عمق. لو نجحت، انت فهمت Recursion. لو طلعلك RecursionError، ارجع لقسم Base Case في المقال ده وراجع شرط التوقف.