كودك بـ Recursion نفسه ؟

السلام عليكم ورحمة الله وبركاته

وقت القراءة: 33 دقيقة

المقدمة

سنتحدث اليوم عن موضوع مهم في عالم البرمجة وهو الـ Recursion او الـ Recursive
وسنتحدث بشكل محدد عن الـ Recursion Function وهى دالة تستدعي نفسها

مفهوم الـ Stack

قبل ان ندخل في الـ Recursion دعنا نتعرف عن مفهوم الـ Stack وكيف يتعامل مع الدوال بشكل عام
الـ stack هو يشبه الوعاء مفتوح من الاعلى ومغلق من الاسفل ويتم وضع فيه الاشياء فوق بعضها ويتعامل بطريقة الـ LIFO أي Last In First Out بمعنى ما يدخل أخرًا يخرج أولًا

جرب احضار ثلاث كتب ورقم تلك الكتب الثلاثة من 1 الى 3
جرب ان تضع الكتب الثلاثة فوق بعضها ابتداءًا من رقم 1 الى رقم 3
ستلاحظ ان الكتاب الاول اصبح في القاع والكتاب الثالث وهو اخر ما وضعته في القمة
ان قلت لك اخرج اخر كتاب فستحضر لي الكتاب رقم ثلاثة لانه اخر كتاب وضعته
وهذا هو معنى ما يدخل أخرًا يخرج أولًا - Last In First Out

والذاكرة الخاصة بالجهاز الـ memory ram تحتوي على stack، هو الذي يتعامل مع الاكواد التي نكتبها لينفذها البرنامج بالترتيب الصحيح
وسنرى مثالًا عمليًا على هذا

إذا كان لدينا مجموعة من الدوال بهذا الشكل

function f1() {
  console.log('f1 called');
  f2();
}

function f2() {
  console.log('f2 called');
  f3();
}

function f3() {
  console.log('f3 called');
}

f1(); // calling the function

لدبنا هنا ثلاث دوال f1, f2 وf3 ونلاحظ ان في دالة f1 يتم استدعاء دالة f2 وفي دالة f2 يتم استدعاء دالة f3

عندما نستدعي الدالة f1 ماذا سيحدث ؟ أريدك ان تقف وتفكر قليلًا وأن تحاول ان تتبع الكود وتحاول معرفة ناتج الطباعة النهائي كيف سيكون

عندما نستدعى الدالة f1 سيتم تخذينها في الـ stack

        |      |
        |      |
        |      |  stack
        |      |
        |      |
        | f1() | <- top
        --------

بهذا الشكل،
فهنا لدينا الـ stack وهو كما قلنا مثل الوعاء وضعنا فيه الدالة f1 داخل هذا الوعاء
وما في اعلى الـ stack يتم وضع مؤشر يشير عليه وهو الـ top

function f1() {
  console.log('f1 called');
  f2();
}

الآن الدالة f1 طبعت جملة f1 called ثم استدعت الدالة f2

        |      |
        |      |
        |      |
        |      |
        | f2() | <- top
        | f1() |
        --------

اصبحت الـf2 في اعلى الـ stack والـ f1 في اسفل
بالتالي اصبح الـ top في الـ stack هو الـ f2

function f2() {
  console.log('f2 called');
  f3();
}

الآن الدالة f2 طبعت جملة f2 called ثم استدعت الدالة f3

        |      |
        |      |
        |      |
        | f3() | <- top
        | f2() |
        | f1() |
        --------

تم إدخال الدالة f3 إلى الـ stack والـ top الآن اصبح هو الـ f3

function f3() {
  console.log('f3 called');
}

الدالة f3 كما ترون هنا ستطبع جملة f3 called فقط ثم تنتهي!
بما انها انتهت تماما ولن تفعل او تستدعي اي شيء إضافي فسيتم حذفها من الـ stack

        |      |
        |      |
        |      |
        |      |
        | f2() | <- top
        | f1() |
        --------

تم إخراج الدالة f3 من الـ stack والـ top الآن اصبح هو الـ f2

الآن ماذا سيحدث ؟ سيتم الآن الذهاب للدالة f2 مجددًا
لكن سنكمل من حيث توقفنا

function f2() {
  console.log('f2 called');
  f3();
}

فنحن هنا كنا قد توقفنا عندما استدعينا الدالة f3, ونحن نعلم اننا انهينا الدالة f3 وحُذفت من الـ stack بالفعل
الآن نكمل في الدالة f2 من بعد سطر استدعاء دالة f3

سنلاحظ ان الدالة f2 انتهت أيضًا ولا يوجد تكملة لها اي وصلت لنهايتها
لذا سنحذفها هي أيضًا من الـ stack

        |      |
        |      |
        |      |
        |      |
        | f1() | <- top
        --------

تم إخراج الدالة f2 من الـ stack والـ top الآن اصبح هو الـ f1
نكرر نفس الامر سنذهب الى الدالة f1 مجددًا ونبدأ من بعد سطر استدعاء دالة f2

function f1() {
  console.log('f1 called');
  f2();
}

سنلاحظ مجددًا انه لا يوجد تكملة لدالة f1 لذلك سيتم حذفها من الـ stack

        |      |
        |      |
        |      |
        |      |
        |      |
        -------- <- top

الآن الـ stack فارغ ولا يوجد شيء فيه وقيمة الـ top هي -1 او null او اي شيء يوحي ان الـ stack فارغ (يعتمد على طريقة بناء الـ stack)

الآن فهمنا كيف يتعامل البرنامج او الـ compiler مع استدعاءات الدوال
وهي عن طريق تخزين كل دالة في الـ stack وعندما تنتهي يتم حذفها من الـ stack

ناتج الطباعة النهائي هو

f1 called
f2 called
f3 called

الآن دعنا نعود لموضوعنا وهو الـ recursion function

ما هي الـ Recursion Function ؟

هي ببساطة دالة تنادي نفسها
دعنا نأخذ مثال

function fun() {
  fun();
}

أنشأنا دالة تدعى fun تقوم فقط باستدعاء نفسها

هل يمكن ان تتخيل شكل الـ stack كيف سيكون إن تم تنفيذ الدالة fun ؟

       stack overflow
            ٨
            |
        | fun() | <- top
        | fun() |
        | fun() |
        | fun() |
        | fun() |
        | fun() |
        | fun() |
        | fun() |
        | fun() |
        ---------

ستلاحظ أن الدالة سيتم استدعاءها بشكل لانهائي وهذا سيسبب stack overflow أي امتلاء تام للـ stack
وهذا يسبب امتلاء تام لذاكرة الجهاز بالتالي يعطل الجهاز نفسه وسيضطر البرنامج الى اغلاق نفسه

لهذ يجب وضع حد او شرط لوقف هذه الدالة عن استدعاء ذاتها الى مالانهاية

تجنب مشكلة Stack Overflow

تعد مشكلة الـ stack overflow من أكبر المشاكل التي يجب الانتباه لها حين نتعامل مع الـ recursion function

يوجد طرق متعددة لحل هذا الأمر لكن أريدك أن تقف وتفكر قليلًا في جعل الدالة تستدعى نفسها 3 مرات فقط

function fun(num) {
  if (num == 0) return; // base case, condition to stop recursion

  console.log('fun called', num);

  num--;
  fun(num);
}

fun(3); // calling the function

الفكرة الأساسية انك يجب أن يكون لديك شرط ما يخبر الدالة أن تتوقف عن استدعاء نفسها
ونحن نريدها ان تتوقف عندما تستدعى ثلاث مرات فقط
لذا وضعنا متغير نرسله مع الدالة عند استدعاءها fun(3)

        |        |
        |        |
        |        |
        |        |
        |        |
        | fun(3) | <- top
        ----------

هنا تم وضع الدالة في الـ stack
أول شيء سيقابلنا هو هذا الشرط if (num == 0) return;
وهذا هو الشرط التي ستتوقف عنده سلسلة الاستدعاءات النهائية وهو يسمى base case أي الحالة الأساسية التي ينتهي كل شيء عندها

أي أنه في حالة ان الرقم وصل الى الصفر اخرج من الدالة ولا تكمل
الـ num حاليًا بـ 3 لذا لن يتحقق الشرط وسيكمل
سيقابلنا السطر التالي console.log('fun called', num); لذا سيتم طباعة fun called 3
ثم سنجد num-- لتصبح قيمتها 2 وسنقوم باستدعاء الدالة مرة أخرى ونعطيها قيمة الـ num الجديدة fun(2)

سيتم وضعها في الـ stack بالطبع

        |        |
        |        |
        |        |
        |        |
        | fun(2) | <- top
        | fun(3) |
        ----------

قيمة الـ num الآن هي 2, هنا سيتفقد الشرط if (num == 0) return; سيجده لا يساوي الـ 0
لذا سيكمل تنفيذ الاكواد ولن يخرج
سيقابلنا سطر الطباعة مجددًا console.log('fun called', num); لذا سيتم طباعة fun called 2
ثم يكمل وسيقابل num-- لذا ستصبح قيمة الـ num الجديدة 1 ثم السطر التالي سيقوم باستدعاء الدالة مجددًا ويعطيها قيمة الـ num الجديدة fun(1)

        |        |
        |        |
        |        |
        | fun(1) | <- top
        | fun(2) |
        | fun(3) |
        ----------

سيقوم بتكرار نفس الأمور بأن يتفقد الشرط سيجده لا يتحقق ثم يكمل ويطبع fun called 1
ثم ينقص قيمة الـ num الى 0 ثم يستدعي نفسه بالقيمة الجديدة fun(0)

        |        |
        |        |
        | fun(0) | <- top
        | fun(1) |
        | fun(2) |
        | fun(3) |
        ----------

ماذا سيحدث هنا الآن ؟

function fun(num) {
  if (num == 0) return;

  console.log('fun called', num);

  num--;
  fun(num);
}

قيمة num الآن تساوي 0، بالتالي سيتحقق الشرط if (num == 0) return; وستخرج دالة fun(0)
من الـ stack الآن

لاحظ اننا لم نقم بطباعة fun called 0 لأنها خرجت من الـ stack فورًا لتحقق الشرط بالتالي لم يتم تكملة تنفيذ باقي أكواد الدالة بالتالم لم يتم استدعاء الدالة مجددًا

        |        |
        |        |
        |        |
        | fun(1) | <- top
        | fun(2) |
        | fun(3) |
        ----------

الآن بعد خروج دالة fun(0) من الـ stack سنرجع للدالة fun(1) للسطر الذي توقفنا عنده سنجد انه لا يوجد أي أوامر أخرة ليتم تنفيذها لذا سنخرج fun(1) من الـ stack

        |        |
        |        |
        |        |
        |        |
        | fun(2) | <- top
        | fun(3) |
        ----------

نرجع للدالة fun(2) وسنجد انه لا يوجد أي أوامر أخرة ليتم تنفيذها لذا سنخرجها من الـ stack

        |        |
        |        |
        |        |
        |        |
        |        |
        | fun(3) | <- top
        ----------

أخيرًا نرجع للدالة fun(3) وسنجد انه لا يوجد أي أوامر أخرة ليتم تنفيذها لذا سنخرجها من الـ stack

        |        |
        |        |
        |        |
        |        |
        |        |
        |        |
        ----------

ناتج الطباعة النهائي هو

fun called 1
fun called 2
fun called 3

هكذا انتهينا من التحدي وجعلنا الدالة تستدعى نفسها 3 مرات فقط

مفهوم الـ Backtracking

حسنًا الـ backtracking هو يعد اهم مفهوم في عالم الـ recursion وهو يعطي للـ recursion
القدرة على حل مشاكل معقدة بشكل بسيط وهو ما يميز الـ recursion ويعطيه امتيازات وقدرات لا توجد الا فيه

ان كان لدينا دالتين الدالة الاولى f1 استدعت الدالة f2
هنا الـ backtracking بشكل عام هي عملية يتم تنفيذها في الدالة الاولى بعد انتهاء البرنامج من تنفيذ الدالة الثانية
بمعنى بعد ما خرج الدالة f2 من الـ stack سيرجع البرنامج للـ f1 من حيث استدعاءه للدالة f2 ليكمل تنفيذ الاوامر من حيث توقف
عملية الرجوع للدالة السابقة لتنفيذ الاوامر المتبقية إن وجدت هذه العملية تسمى backtracking

مثال عملي للتوضيح لدينا الآن الدالة f1 استدعت الدالة f2

بهذا الشكل

function f1() {
  console.log('f1 called');
  f2();
  console.log('f1 end');
}

function f2() {
  console.log('f2 called');
}

f1(); // calling the function

هنا سيدخل إلى f1 ويطبع جملة f1 called ثم سيدخل إلى f2 ويطبع جملة f2 called

سيكون شكل الـ stack هكذا

        |      |
        |      |
        |      |
        |      |
        | f2() | <- top
        | f1() |
        --------

بعد الانتهاء من الـ f2 ستخرج من الـ stack

        |      |
        |      |
        |      |
        |      |
        |      |
        | f1() | <- top
        --------

الآن سيتم الذهاب للدالة f1 وسنكمل من حيث تم استدعاء الدالة f2

function f1() {
  console.log('f1 called');
  f2();
  console.log('f1 end');
}

بمعنى أننا بعد انتهائنا من الدالة f2 وخروجها من الـ stack سنكمل في الدالة f1 من بعد سطر استدعاء دالة f2

سنجد انه تبقى سطر واحد وهو طباعة f1 end
هذا الجزء الذي تم تنفيذه في الدالة f1 بعد انتهاءه من تنفيذ الدالة f2 يدعى backtracking لأننا بعد استدعاء الدالة f2 وانتهائها عدنا الى الدالة f1 مجددًا لنكمل من بعد سطر استدعاء الدالة f2

هذا هو المعنى الحرفي لكلمة backtracking وهو الرجوع من حيث اتيت لاستكمال الاكواد المتبقية

function f1() {
  console.log('f1 called');
  f2();
  // backtracking in f1 after f2 finished
  console.log('f1 end');
}

ناتج الطباعة النهائي هو

f1 called
f2 called
f1 end

هو هنا في f1 طبع f1 called ثم ذهب الى f2 وطبع f2 called ثم عاد مجددًا الى f1 وطبع f1 end

مثال تطبيقي على الـ Backtracking

سنأخذ مثالًا آخر للـ backtracking لنوضح الأمر

function f1(n) {
  console.log('f1 called', n);
  const res = f2(n) / 5;
  // backtracking in f1 after f2 finished
  console.log('received result', res, 'from f2');
  console.log('res: ', res);
}

function f2(n) {
  console.log('f2 called', n);
  const res = f3(n);
  // backtracking in f2 after f3 finished
  console.log('received result', res, 'from f3');
  return res + res;
}

function f3(n) {
  console.log('f3 called', n);
  return n * 3;
}

f1(5); // calling the function

أظنك فهمت الأمر لذا لنأخذ تحدي آخر هنا، قف وتتبع الأكواد وحاول أن ترسم الـ stack وتتبع تسلسل الكود لتعرف الناتج النهائي

إن وصلت للناتج النهائي وهو 6 فهنيئًا لك
سنقوم فقط بشرح الخطوات وتتبع الأكواد خطوة خطوة في حالة اختلطت عليك الأمور ولم تتمكن من ايجاد الناتج الصحيح

أول شيء نستدعي f1(5)

        |       |
        |       |
        |       |
        |       |
        |       |
        | f1(5) | <- top
        ---------

لنلقي نظرة على دالة f1

function f1(n) {
  console.log('f1 called', n);
  const res = f2(n) / 5;
  // backtracking in f1 after f2 finished
  console.log('received result', res, 'from f2');
  console.log('res: ', res);
}

أول شيء قيمة الـ n الحالية تساوي 5
واول سطر في الدالة سيطبع f1 called 5
ثم نتحرك للسطر التالي سنجد const res = f2(n) / 5;
هنا عرفنا متغير res قيمته تساوي القيمة الراجعة من f2(5) مقسومة على 3
بمعنى ان قيمة الـ res ستحدد بالقيمة التي سنحصل عليها بعد تنفيذ f2(5)
والـ f2 ما هي إلا دالة لذا سيتم وضعها في الـ stack الآن وسيتم تنفيذها الآن

        |       |
        |       |
        |       |
        |       |
        | f2(5) | <- top
        | f1(5) |
        ---------

الآن نحن في الدالة f2(5)

function f2(n) {
  console.log('f2 called', n);
  const res = f3(n);
  // backtracking in f2 after f3 finished
  console.log('received result', res, 'from f3');
  return res + res;
}

قيمة الـ n مازالت تساوي 5 ثم سنجد جملة طباعة عادية f2 called 5
بعد ذلك سنجد const res = f3(n); وهو متغير يدعى res متعرف في f2
وقيمته تعتمد على دالة f3(5)
لذا سنقوم بعمل نفس الأمر بأن نضع f3(5) في الـ stack ونبدأ بتنفيذها

        |       |
        |       |
        |       |
        | f3(5) | <- top
        | f2(5) |
        | f1(5) |
        ---------

سنجد دالة f3 بسيطة جدًا

function f3(n) {
  console.log('f3 called', n);
  return n * 3;
}

فقط نطبع f3 called 5
ثم يقوم بإرجاع قيمة n * 3 وبما ان قيمة الـ n هي 5 فسوف يقوم بإرجاع قيمة 15
وتكون انهينا تنفيذ الدالة f3 الآن نخرجها من الـ stack

        |       |
        |       |
        |       |
        |       |
        | f2(5) | <- top, return f3(5) as 15
        | f1(5) |
        ---------

هنا أخرجنا f3(5) من الـ stack لكن القيمة الراجعة منها هي 15
كيف نستفيد منها وهي سترجع الى أين ؟

سنعود من حيث أتينا, تتذكر مفهوم الـ backtracking
سنعود إلى f2(5) إلى اللحظة الذي تركناها فيه قبل ان نستدعي f3(5) ونكمل تنفيذ الأكواد المتبقية

function f2(n) {
  console.log('f2 called', n);
  const res = f3(n);
  // backtracking in f2 after f3 finished
  console.log('received result', res, 'from f3');
  return res + res;
}

الآن نحن تركنا f2(5) عندما استعينا f(5) هنا const res = f3(n); تتذكر ؟
ثم وضعنا f3(5) في الـ stack ونفذناها وانتهينا منها والآن هي أرجعت لنا قيمة 15
لذا قيمة f3(5) في هذا السطر const res = f3(n); تساوي 15
بالتالي سيراها المترجم او البرنامج الآن كهذا const res = 15;
لأن f3(5) أرجعت لنا 15 كما وضحنا
الآن قيمة الـ res في الدالة f2(5) تساوي 15

function f2(n) {
  console.log('f2 called', n);
  const res = f3(n); // res = 15
  // backtracking in f2 after f3 finished
  console.log('received result', res, 'from f3');
  return res + res;
}

نرجع إلى الدالة f2(5) ونكمل من حيث توقفنا وقيمة الـ res تساوي 15
هنا لدينا جملة طباعة received result 15 from f3
ثم return res + res; بالتالي دالة f2(5) انتهت وسترجع قيمة 30 لأن res + res = 15 + 15 = 30

        |       |
        |       |
        |       |
        |       |
        |       |
        | f1(5) | <- top, return f2(5) as 30
        ---------

الآن أنا أفترض أنك فهمت الحكاية بعد اخراج f2(5) من الـ stack سنرجع نكمل من عند f1(5)
وقيمة f2(5) تساوي 30 الآن

function f1(n) {
  console.log('f1 called', n);
  const res = f2(n) / 5;
  // backtracking in f1 after f2 finished
  console.log('received result', res, 'from f2');
  console.log('res: ', res);
}

نحن كنا قد توقفنا عند const res = f2(n) / 5; بعد تنفيذ f2(5) أصبح قيمتها 30 بالتالي قيمة الـ res ستساوي 3 لأن res = 30 / 5 = 6

الآن نكمل سنجد جملة طباعة received result 6 from f2
ثم جملة طباعة الناتج النهائي res: 6
وانتهت دالة f1(5) أخيرًا لذا سنخرجها من الـ stack

        |       |
        |       |
        |       |
        |       |
        |       |
        |       |
        --------- <- top

تسلسل جمل الطباعة كان هكذا

f1 called 5
f2 called 5
f3 called 5
received result 15 from f3
received result 6 from f2
res: 6

ستلاحظ ان قيمة n نحن استخدمناها فقط في الدالة f3 فنحن مررناها إبتدائًا من f1 إلى f2 ثم إلى f3 حيث استعملناها فقط هناك حيث ارجعنا القيمة return n * 3; ثم استعملنا الناتج الراجع من f3 في الدالة f2 ثم في f1 بطريقة عكسية وهذا تمثيل للـ backtracking أنك تتعمق داخل الدوال والـ stack لتقوم بعمل بعض العمليات ثم ترجع بإتجاه عكسي لتكمل باقي العملية اسنادًا على العمليات التي قمت بها وأنت ذاهب

بمعنى أنك بدأت بالدالة f1 وكان معك n تساوي 5 تلك الـ n أنت استخدمتها في الـ f3 فقط ولم تقم بأي عملية في f1 وf2 أثناء ذهابك إلى f3
الآن أنت أثناء رجوعك إلى f2 وf1 سوف تستفيد من العملية التي قمت بها في الدالة f3
لتقوم بعمل عمليات في الدالة f1 وf2 استنادًا إلى القيمة الراجعة من f3، أرجو أن تكون الفكرة وصلت هنا

مثال مضروب العدد

سنقوم بتطبيق مثال أخير باستعمال مفهوم الـ recursion function
سنقوم بعمل دالة تستقبل رقم كمتغير ثم تجلب لنا مضروب هذا العدد
سنقوم بعمل تلك الدالة باستعمال الـ recursion function

هذا تحدي يمكنك أن تتوقف عن القراءة وتفكر بحل هذه المسألة ثم أرجع وأكمل قراءة

لنفكر قليلًا عندما نريد ان نحصل على مضروب الرقم 5 ماذا نفعل ؟ ستقول لي نضرب الرقم 5 في كل الارقام الأصغر منها لغاية الرقم 1
ليكون مضروب الرقم 5 هو 5 * 4 * 3 * 2 * 1 = 120

يمكننا ان نكتب هذا القانون بشكل آخر ؟ نعم، يمكننا ان نقول أن مضروب الرقم 5 هو الرقم 5 نفسه مضروب في مضروب الرقم 4
ليكون الناتج بهذا الشكل 5 * factorial(4) = 120
هنا نستنتج القانون العام وهو factorial(n) = n * factorial(n-1)

القانون كأنه يمكنك أن تكتبه كدالة، لذا سنحاول ان نكتبه كدالة

function factorial(n) {
  return n * factorial(n - 1);
}

حسنًا الأمور تبدو بسيطة لكن لاحظ أن الدالة الآن اصبحت recursion function
ولاحظ أنها هكذا تستدعي نفسها إلى مالانهائية وهذا سيسبب مشكلة الـ stack overflow

هل تتذكر كيف نحل هذه المشكلة ؟ هل تتذكر حين قلت لك ان تجعل الدالة تستدعي نفسها 3 مرات؟
ماذا فعلنا ؟ قمنا بعمل شرط يوقف الدالة عن استدعاء نفسها وكان يدعى base case
إذا نحتاج لشرط يوقف هذه الدالة، عندما نرجع لأصل المضروب سنجد أنه مضروب الرقم نفسه مع كل الأرقام الأصغر من الرقم نفسه يتوقف دائما عند الـ 1
ونعرف أيضًا أن مضروب الـ 1 يساوي 1 ومضروب الـ 0 يساوي 1
لذا يمكننا أن نوقف الدالة من استدعاء نفسها عندما تصل إلى الـ 0
وأخرنا الـ 0 ليكون هو الـ base case بدلًا من الـ 1
لأن الـ 0 أصغر الأرقام التي لها مضروب وقيمة مضروبه هي 1

شكل الدالة الآن ستصبح هكذا

function fact(n) {
  if (n === 0) return 1; // base case

  return n * fact(n - 1); // recursion call
}

console.log(fact(5)); // calling the function and print the result

لاحظ إننا إن أردنا مضروب الـ 0 فسيتم إحضار الناتج بشكل مباشر وهو 1 لأنه سيجلبها من الـ base case بشكل مباشر ولن تضطر الدالة أن تستدعي نفسها من الأساس

حسنًا هذه هي المضروب باستعمال الـ recursion تأمل في الدالة قليلًا
معقدة لأي شخص لم يفهم كيفية عمل الـ recursion بشكل صحيح
وبسيطة لمن يعرف كيفية رسم الـ stack ويتبع الكود بشكل صحيح مع الرسم

الآن نبدأ بأخذ مثال عن مضروب الـ 5 لنشرح عليها وهنا نبدأ بتنفيذ سطر الطباعة console.log(fact(5))
ستلاحظ أننا نستدعي الدالة fact(5)
نحن نعرف أنه سيتم طباعة ناتج fact(5) ونحن نعرف أن مضروب 5 هو 120 لكن دعنا نتبع الكود لنعرف كيف تم حساب الناتج عن طريق الدالة

نقوم بوضع fact(5) داخل الـ stack ونبدأ التنفيذ والرسم

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(5) | <- top
        -----------

هنا عند تنفيذ الدالة سنواجه أول سطر وهو الحالة التي سيوقف الدالة من استدعاء نفسها if(n === 0) return 1;
الشرط ببساطه ان لو كان قيمة n تسوي 0 فأخرج من الدالة وأرجع 1
قيمة الـ n تساوي 5 لذا فهو سيكمل الدالة إلى السطر التالي

والسطر التالي هو return n * fact(n - 1); ومعناه انه سيرجع قيمة n مضروبة في fact(n - 1)
ولو فكرت في الأمر فستجد انها منطقية لان مضروب الـ 5 نعرف انه يساوي 5 مضروبة في مضروب الـ 4

فمضروب n يساوي n مضروبة في مضروب n - 1 وهذه قاعدة عاملة نطبها هنا افي الدالة كما ترى return n * fact(n - 1);

الآن قيمة الـ n هي 5 فسيكون شكل الكود الخاص بـ fact(5) هكذا return 5 * fact(4); وهنا يجب ان نعرف قيمة fact(4) لنعرف قيمة fact(5) لذا هنا ستجد ان الدالة ستستدعي نفسها لكن بقيمة جديدة وهي fact(4) لأن هذا هو مبدأ قانون المضروب بشكل عام، بأن يجب ان تعرف مضروب الرقم السابق لتعرف مضروب الرقم الحالي

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(4) | <- top
        | fact(5) |
        -----------

ستجد انه سيعيد نفسه مجددًا بقيمة 4
لذا الشرط لم يتحقق، لذا سنكمل فسنجد return 4 * fact(3); فهنا سنجد أنه لنعرف مضروب الـ 4 يجب أن نعرف مضروب الـ 3
لذا ستستدعي الدالة نفسها برقم جديد وهو 3

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(3) | <- top
        | fact(4) |
        | fact(5) |
        -----------

حسنًا نحن فقط سنكرر الأمر لذا سنسرع الشرح قليلًا
هنا رقم 3 لا يساوي 0 لذا لن يتحقق الشرط
سنكمل فسنجد return 3 * fact(2);
هنا نبدأ بتنفيذ fact(2)

        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(2) | <- top
        | fact(3) |
        | fact(4) |
        | fact(5) |
        -----------

الـ 2 لا تساوي 0 لذا لن يتحقق الشرط
سنكمل فسنجد return 2 * fact(1); هنا نبدأ بتنفيذ fact(1)

        |         |
        |         |
        |         |
        |         |
        | fact(1) | <- top
        | fact(2) |
        | fact(3) |
        | fact(4) |
        | fact(5) |
        -----------

الـ 1 لا يساوي 0 لذا لن يتحقق الشرط سنكمل فسنجد return 1 * fact(0); هنا نبدأ بتنفيذ fact(0)

        |         |
        |         |
        |         |
        | fact(0) | <- top
        | fact(1) |
        | fact(2) |
        | fact(3) |
        | fact(4) |
        | fact(5) |
        -----------

هنا يبدأ الشرط بالتحقق لأن n تساوي 0 لذا سيتحقق الشرط وسترجع الدالة 1

هنا ستخرج fact(0) من الـ stack لكننا سترجع قيمة 1
الآن من استدعى fact(0) ? ستقول التي استدعتها هي fact(1)
لذا سنعود لها وهذا مفهوم الـ backtracking

        |         |
        |         |
        |         |
        |         |
        | fact(1) | <- top, return fact(0) as 1
        | fact(2) |
        | fact(3) |
        | fact(4) |
        | fact(5) |
        -----------

هنا في الدالة fact(1) وبعد استبدال قيمة n بـ 1 ستكون الدالة هكذا

function fact(1) {
  if (1 === 0) return 1;

  return 1 * fact(0);
}

لنركز على هذا الجزء return 1 * fact(0); الآن نحن نفذنا الدالة fact(0) وانتهت وأرجعت لنا قيمة 1 لذا سنضع قيمة 1 مكان fact(0)
سيبدو الكود هكذا return 1 * 1;

بالتالي الدالة fact(1) سترجع قيمة 1 وسنخرجها من الـ stack

        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(2) | <- top, return fact(1) as 1
        | fact(3) |
        | fact(4) |
        | fact(5) |
        -----------

هنا نحن الآن في fact(2)، لنركز على القيمة الراجعة من كل دالة لانها هي النقطة التي انطلقنا منها واستدعينا الدوال الأخرى

القيمة الراجعة من الدالة fact(2) هي return 2 * fact(1);
وعرفنا أن الدالة fact(1) ترجع قيمة 1
لذا ستنتهي الدالة fact(2) وسترجع لنا الناتج وهو 2

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(3) | <- top, return fact(2) as 2
        | fact(4) |
        | fact(5) |
        -----------

سنعيد تكرار نفس الأمور من جديد
القيمة الراجعة من الدالة fact(3) هي return 3 * fact(2);
وعرفنا أن الدالة fact(2) ترجع قيمة 2
لذا ستنتهي الدالة fact(3) وسترجع لنا الناتج وهو 6

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(4) | <- top, return fact(3) as 6
        | fact(5) |
        -----------

القيمة الراجعة من الدالة fact(4) هي return 4 * fact(3);
وعرفنا أن الدالة fact(3) ترجع قيمة 6
لذا ستنتهي الدالة fact(4) وسترجع لنا الناتج وهو 24

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        | fact(5) | <- top, return fact(4) as 24
        -----------

وصلنا للنهاية الآن ووصل لأول استدعاء لنا وهو fact(5)
القيمة الراجعة من الدالة fact(5) هي return 5 * fact(4);
الآن نحن خوضنا رحلة طويلة لنعرف قيمة الدالة fact(4) وهي 24
لذا ستنتهي الدالة fact(5) وسترجع لنا الناتج وهو 120

        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        |         |
        ----------- <- top

لاحظ أنه الدالة fact(0) انتهت وأرجعت لنا قيمة 1 وهو بالفعل مضروب الـ 0
والدالة fact(1) انتهت وأرجعت لنا قيمة 1 وهو بالفعل مضروب الـ 1 والدالة fact(2) انتهت وأرجعت لنا قيمة 2 وهو بالفعل مضروب الـ 2 والدالة fact(3) انتهت وأرجعت لنا قيمة 6 وهو بالفعل مضروب الـ 3 والدالة fact(4) انتهت وأرجعت لنا قيمة 24 وهو بالفعل مضروب الـ 4 والدالة fact(5) انتهت وأرجعت لنا قيمة 120 وهو بالفعل مضروب الـ 5

إلى هنا نكون قد انتهينا من هذا الدرس الطويل
أرجوا ان تراجعوها وأن ترسموا الـ stack جيدًا وأن تتبعوا الكود سطر سطر
لأن الأمر سيكون أسهل إن رسم الـ stack وبدأت تتخيله