هذا المقال يتطلب مستوى: مبتدئ. هتفهم بعده يعني إيه دالة بتنادي نفسها، ليه أحيانًا الكود بيموت بـ Stack Overflow، وإمتى Recursion بيكون أنضف من الـ loop العادي.

Recursion للمبتدئ: لما الدالة بتنادي نفسها

لو كتبت دالة بسيطة بتجمع أرقام من 1 لـ 100 ولقيت Node بيرمي RangeError: Maximum call stack size exceeded، المشكلة مش في الـ RAM ولا في السيرفر. المشكلة إن دالتك بتنادي نفسها بدون شرط توقّف. ركز على الجملة دي كويس، لأنها المفتاح لكل حاجة جاية في المقال.

المشكلة باختصار

كل مبتدئ بيتعلم البرمجة بيقابل لحظة واحدة بتلخبطه: شوية كود قصير جدًا بيعمل حاجة معقدة، ومش فاهم إزاي. الكود ده غالبًا بيستخدم Recursion. وبدون ما تفهمه، هتلاقي نفسك بتكتب 40 سطر بـ for و while في مكان كان ممكن يتحل في 5 سطور.

لكن نفس Recursion ده، لو ما عرفتش تحطله شرط توقف، بيوقع الـ runtime كله. الموضوع مش نظري، ده بيحصل في production فعلًا.

مثال البصلة: تخيّل قبل ما تشوف الكود

تخيّل إن قدامك بصلة كبيرة، وعايز توصل لقلبها. إنت بتعمل إيه بالظبط؟ بتقشّر طبقة واحدة، وتلاقي بصلة أصغر جوّه. تعمل بيها نفس الحاجة: تقشّر طبقة، تلاقي بصلة أصغر، وهكذا. الموضوع بيقف لما توصل لطبقة مفيش جواها حاجة. دي بالظبط فكرة Recursion:

• كل مرة بتعمل نفس الخطوة (تقشير).
• المشكلة بتصغر مع كل خطوة (البصلة بتقل طبقاتها).
• في حالة نهائية بتخلّيك تقف (مفيش طبقات تانية).

لو نسيت الحالة النهائية، هتفضل تقشّر للأبد. نفس الكلام في الكود.

التعريف العلمي بدون رغي

في كتاب Introduction to Algorithms (المعروف بـ CLRS - Cormen, Leiserson, Rivest, Stein - الفصل 4)، التعريف بسيط: Recursion هي تقنية بتحل المشكلة الكبيرة عن طريق تقسيمها لنسخة أصغر من نفس المشكلة، وحل النسخة الأصغر بنفس الطريقة، لحد ما توصل لحالة بسيطة بتعرف تحلها مباشرة.

التعريف ده عنده ركنين أساسيين، ولازم يكونوا في كل دالة recursive:

1. Base Case (الحالة الأساسية): الشرط اللي بيخلّي الدالة تقف وترجع قيمة من غير ما تنادي نفسها تاني.
2. Recursive Case (الحالة المتكررة): الدالة بتنادي نفسها بقيمة أصغر بتقرّبها للـ Base Case.

أول مثال شغّال: factorial بـ Python

factorial بتاع رقم n هو حاصل ضرب الأرقام من 1 لـ n. يعني 5! = 5 × 4 × 3 × 2 × 1 = 120. لاحظ إن 5! = 5 × 4!، و 4! = 4 × 3!، وهكذا. ده تعريف بيقول حرفيًا "المشكلة الكبيرة = خطوة + نسخة أصغر من نفس المشكلة". مثالي لـ 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). نظام الملفات عندك في الكمبيوتر شجرة: المجلد فيه ملفات ومجلدات تانية، اللي فيهم ملفات ومجلدات تانية. ده بالظبط نفس بنية البصلة:

// Node.js 20 — يطبع كل ملف داخل مجلد بأي عمق
const fs = require("fs");
const path = require("path");

function listAllFiles(dir) {
  const entries = fs.readdirSync(dir, { withFileTypes: true });
  for (const entry of entries) {
    const fullPath = path.join(dir, entry.name);
    if (entry.isDirectory()) {
      listAllFiles(fullPath); // الدالة بتنادي نفسها على المجلد الجوّاني
    } else {
      console.log(fullPath); // Base case ضمنيًا: الملف مش مجلد فبنطبعه ونرجع
    }
  }
}

listAllFiles("./project");

لو حاولت تكتب نفس الكود ده بـ 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 في المقال ده وراجع شرط التوقف.