كودك بـ Recursion نفسه ؟
السلام عليكم ورحمة الله وبركاته
الفهرس
المقدمة
سنتحدث اليوم عن موضوع مهم في عالم البرمجة وهو الـ Recursion او الـ Recursive
وسنتحدث بشكل محدد عن الـ Recursion Function وهى دالة تستدعي نفسها
- سنستخدم لغة
javascriptللتطبيق العملي لا اكثر، لكن كل ما سنشرحه هنا ينطبق على جميع اللغات
مفهوم الـ Stack
قبل ان ندخل في الـ Recursion دعنا نتعرف عن مفهوم الـ Stack وكيف يتعامل مع الدوال بشكل عام
الـ stack هو يشبه الوعاء مفتوح من الاعلى ومغلق من الاسفل ويتم وضع فيه الاشياء فوق بعضها
ويتعامل بطريقة الـ LIFO أي Last In First Out بمعنى ما يدخل أخرًا يخرج أولًا
جرب احضار ثلاث كتب ورقم تلك الكتب الثلاثة من 1 الى 3
جرب ان تضع الكتب الثلاثة فوق بعضها ابتداءًا من رقم 1 الى رقم 3
ستلاحظ ان الكتاب الاول اصبح في القاع والكتاب الثالث وهو اخر ما وضعته في القمة
ان قلت لك اخرج اخر كتاب فستحضر لي الكتاب رقم ثلاثة لانه اخر كتاب وضعته
وهذا هو معنى ما يدخل أخرًا يخرج أولًا - Last In First Out
والذاكرة الخاصة بالجهاز الـ memory ram تحتوي على stack، هو الذي يتعامل مع الاكواد التي نكتبها لينفذها البرنامج بالترتيب الصحيح ويسمى call 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
- الـ
topهو مؤشر يشير على اخر شيء دخل الى الـstack، وبمعنى اصح هو يشير على اعلى الـstack
function f1() {
console.log('f1 called');
f2();
}
الآن الدالة f1 طبعت جملة f1 called ثم استدعت الدالة f2
| |
| |
| |
| |
| f2() | <- top
| f1() |
--------
اصبحت الـf2 في اعلى الـ stack والـ f1 في اسفل
بالتالي اصبح الـ top في الـ stack هو الـ f2
- لاحظ ان الدالة
f1مازالت في الـstackمعنى هذا انها لم تنتهى بعد ولم يتم حذفها من الذاكرةmemory ram
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) |
----------
- مفهوم الرجوع للدالة السابقة يدعى
backtrackingسنشرحه بشكل من التفصيل في نهاية المقالة
الآن بعد خروج دالة 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('f1 received result', res, 'from f2');
console.log('f1 res: ', res);
}
function f2(n) {
console.log('f2 called', n);
const res = f3(n);
// backtracking in f2 after f3 finished
console.log('f2 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('f1 received result', res, 'from f2');
console.log('f1 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('f2 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('f2 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('f2 received result', res, 'from f3');
return res + res;
}
نرجع إلى الدالة f2(5) ونكمل من حيث توقفنا وقيمة الـ res تساوي 15
هنا لدينا جملة طباعة f2 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('f1 received result', res, 'from f2');
console.log('f1 res: ', res);
}
نحن كنا قد توقفنا عند const res = f2(n) / 5; بعد تنفيذ f2(5) أصبح قيمتها 30 بالتالي قيمة الـ res ستساوي 3 لأن res = 30 / 5 = 6
الآن نكمل سنجد جملة طباعة f1 received result 6 from f2
ثم جملة طباعة الناتج النهائي f1 res: 6
وانتهت دالة f1(5) أخيرًا لذا سنخرجها من الـ stack
| |
| |
| |
| |
| |
| |
--------- <- top
تسلسل جمل الطباعة كان هكذا
f1 called 5
f2 called 5
f3 called 5
f2 received result 15 from f3
f1 received result 6 from f2
f1 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، أرجو أن تكون الفكرة وصلت هنا
مثال مضروب العدد | Factorial
سنقوم بتطبيق مثال آخر باستعمال مفهوم الـ 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, return func(5) as 120
لاحظ أنه الدالة
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 وبدأت تتخيله