لو شفت كود فيه دالة جوّاها بتنادي نفس الدالة، حاسس إن ده غلط وهيدخل في لوب لا نهائي. الكود ده شغّال صح، اسمه Recursion، وبيحلّ مسائل معيّنة في 8 سطور بدل 50 سطر loop عادي. هنا هتفهم بالظبط ازاي بتشتغل، وامتى تستخدمها، وامتى تبعد عنها لأنها هتكسر تطبيقك.

Recursion: لما الدالة بتحلّ المسألة بإنها بتنادي نفسها

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

لو قلتلك "احسبلي مجموع كل أرقام الفولدرات المتداخلة في مشروعك، بما فيها الفولدرات اللي جوّا فولدرات تانية"، الـ for loop العادي مش هيعرف يوصل لكل المستويات بسهولة. لازم تكتب حلقة جوّا حلقة جوّا حلقة، وانت مش عارف الفولدرات هتنزل كام مستوى.

Recursion بتحل المشكلة دي بفكرة واحدة: الدالة بتفكّك المسألة لمسألة أصغر من نفس النوع، وبتنادي نفسها على المسألة الأصغر، لحد ما توصل لحالة بسيطة جدًا تعرف تردّ عليها مباشرة.

مثال للمبتدئ: دمى ماتريوشكا

تخيل معاك دمية ماتريوشكا روسية. بتفتحها، تلاقي جوّاها دمية أصغر، تفتحها، تلاقي أصغر منها، وهكذا لحد ما توصل لدمية صغيرة مفيهاش حاجة. الدماغ بتاعتك مش بتحسب من الأول كام دمية. كل ما تفتح واحدة، بتعمل نفس الخطوة على اللي جوّاها.

ده بالظبط اللي الـ Recursion بتعمله. كل استدعاء (call) للدالة هو "فتح دمية واحدة". لما توصل للدمية الفاضية، الـ recursion بتقف. الحالة دي بتُسمى Base Case، ومن غيرها الكود فعلاً هيدخل لوب لا نهائي ويكسر التطبيق.

التعريف الدقيق

الـ Recursion دالة بتعرّف نفسها بدلالة نفسها على إدخال أصغر. علميًا، أي دالة recursive لازم يكون فيها مكوّنين أساسيين موثقين في كل كتاب algorithms معتبر زي Introduction to Algorithms (Cormen et al., MIT Press):

1. Base Case: شرط بسيط، الدالة بترجع منه قيمة مباشرة من غير ما تنادي نفسها تاني.
2. Recursive Case: الجزء اللي الدالة بتنادي فيه نفسها، بشرط إن الإدخال الجديد يكون أصغر أو أقرب للـ base case من الإدخال الحالي.

لو ضيّعت أي شرط من الاتنين، هيحصل واحدة من اتنين: لوب لا نهائي يأكل الذاكرة، أو خطأ RangeError: Maximum call stack size exceeded في JavaScript أو RecursionError في Python.

كود فعلي: حساب factorial في 4 سطور

أبسط مثال شغّال. الـ factorial للرقم n هو حاصل ضرب كل الأرقام من 1 لـ n. يعني 5! = 5 × 4 × 3 × 2 × 1 = 120.

function factorial(n) {
  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1);  // Recursive case
}

console.log(factorial(5)); // 120

الـ base case هنا هو n <= 1. الـ recursive case بيقلل n بـ 1 في كل استدعاء. بعد 5 استدعاءات بنوصل للـ base case والقيم بترجع للوراء واحدة واحدة.

مثال أقرب للواقع: قراءة JSON متداخل

تخيل عندك ردّ من API فيه شجرة تعليقات (كل تعليق ممكن يكون تحته ردود، وكل ردّ ممكن يكون تحته ردود تانية). عايز تعدّ كل التعليقات في الشجرة.

function countComments(comment) {
  let total = 1; // التعليق الحالي نفسه
  for (const reply of comment.replies || []) {
    total += countComments(reply); // ندوس على كل ردّ ونعدّه هو وردوده
  }
  return total;
}

const root = {
  text: "أول تعليق",
  replies: [
    { text: "ردّ", replies: [{ text: "ردّ على ردّ", replies: [] }] },
    { text: "ردّ تاني", replies: [] }
  ]
};

console.log(countComments(root)); // 4

لو حاولت تكتب الكود ده بـ for loop عادي، هتحتاج Stack يدوي وهتكتب 25-30 سطر فيهم احتمال غلطات أكتر. الـ Recursion هنا بتختصر الفكرة لـ 6 سطور.

إيه اللي بيحصل في الذاكرة فعلًا؟

كل ما الدالة بتنادي نفسها، نظام التشغيل بيحجز قطعة جديدة من الذاكرة اسمها Stack Frame. الفريم بيخزّن المتغيرات المحلية والمكان اللي الدالة هترجع له بعد ما تخلص. كل الفريمات دي متراكمة فوق بعض في منطقة اسمها Call Stack.

الـ Call Stack ليه حجم أقصى. على Node.js v22 بمحرك V8 بإعدادات افتراضية، حجم الـ stack بيوصل لحوالي 10,416 frame قبل ما يرمي RangeError (الرقم ده مقاس فعليًا بسكربت بسيط بيعدّ n لحد ما يقع). في Python 3.12، الحد الافتراضي هو 1,000 استدعاء (sys.getrecursionlimit()). يعني لو شجرتك أعمق من كده، الـ recursion هتقع.

الـ Trade-offs الحقيقية

الـ Recursion مش حل سحري. فيه أربع مفاضلات لازم تعرفها:

• الذاكرة أعلى: كل استدعاء بياخد فريم في الـ stack. لـ 1,000 استدعاء ممكن تأكل 100 KB-1 MB ذاكرة، بينما الـ loop بياخد عشرات البايتس.
• أبطأ شوية: استدعاء الدالة بحد ذاته فيه overhead. على V8، استدعاء دالة بسيط بياخد حوالي 5-15 نانوثانية. على مليون استدعاء، الفرق بين recursion و loop ممكن يوصل لـ 8-12 ms مقاسة في micro-benchmark بسيط.
• أصعب في الـ debug: الـ stack trace بيبقى طويل جدًا، وأحيانًا بيتقطع في المنتصف.
• سهل تكتبها غلط: نسيان الـ base case أو حساب الـ recursive case غلط بيكسّر التطبيق فورًا، مش تدريجيًا.

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

الـ Recursion بتلمع في حالات معيّنة، وبتفشل في حالات تانية:

• لو الإدخال خطّي وفيه عدّاد واضح (احسب مجموع array من 1,000,000 رقم) — الـ loop أسرع وأبسط.
• لو ممكن العمق يوصل لآلاف المستويات (parsing لملفّات XML بحجم جيجا) — الـ Recursion هتقع، استخدم iterative approach مع stack يدوي.
• لو في hot path بيتنفّذ ملايين المرات في الثانية — overhead الاستدعاء بيتراكم. الـ loop بيوفّر 30-50% من الزمن في حالات زي دي.
• لو لغة البرمجة مش بتدعم Tail Call Optimization فعليًا (وده الواقع في V8 الحالي و CPython) — مفيش طريقة تتجنّب نمو الـ stack.

القاعدة العملية: استخدم Recursion لما البيانات نفسها recursive بطبيعتها (شجرة، graph، JSON متداخل، AST، file system). استخدم loop لما البيانات flat.

المصادر

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4th Edition, MIT Press, 2022 — الفصل 4 عن Divide-and-Conquer وحلّ recurrences.
• توثيق Node.js الرسمي عن الـ stack limits: --stack-size flag في nodejs.org/api/cli.html.
• توثيق Python الرسمي عن sys.getrecursionlimit() و sys.setrecursionlimit() في docs.python.org/3/library/sys.html.
• ECMAScript 2024 spec, الفقرة 9.4 — Execution Contexts و Call Stack semantics.
• V8 blog post عن Tail Calls و سبب عدم تفعيلها افتراضيًا في Chrome: v8.dev/blog.

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

افتح الـ terminal بتاعك دلوقتي واكتب دالة sumDirectorySize(path) بـ Node.js بتحسب حجم فولدر مع كل اللي جوّاه باستخدام fs.readdirSync و recursion. لو الفولدر فيه أكتر من 5 مستويات، ده بالظبط الموقف اللي recursion فيه أنضف من أي loop. لو الكود وقع بـ RangeError على فولدر node_modules، ده معناه إنك لقيت شجرة عميقة جدًا — وقتها استبدل الـ recursion بـ stack يدوي. ده تمرين عملي هتحتاجه فعلاً في أول task أوتوميشن جدّي.