تعلم البرمجة باستخدام JavaScript


الدرس: اكتشف العودية: استدعاء الوظائف داخل نفسها


الصفحة السابقة

وظيفة تستدعي نفسها



و ظيفة متكررة هي وظيفة التي تستدعي نفسها بطريقة أو بأخرى.

لنأخذ كمثال: البحث الثنائي.

الهدف من التمرين: البحث عن عنصر في مصفوفة مرتبة لمعرفة ما إذا كان موجودًا.

سيكون النهج الأساسي (والبطيء نوعًا ما) هو:


const findElement = (array, thingToFind) {

 

for (let element of array) {



if (element === thingToFind) {



return true;



}



}



return false;



}
 
نتحرك للأمام ، عنصرًا عنصرًا ، في المصفوفة. إذا وجدنا عنصرًا يطابق ما نبحث عنه ، فستعيد الدالة    true  . إذا وصلنا إلى نهاية المصفوفة دون العثور عليها ، ننتقل إلى السطر التالي وترجع الدالة    false  .

من الواضح جدًا كنهج ، لكنه بطيء! الوقت المستغرق لكل بحث يمتد خطيًا مع القوائم الأطول!

تخيل مقاربة أخرى.


const binarySearch = (array, thingToFind, start, end) => {

 

 

 

}
 
نحن نعلم أن المصفوفة مرتبة ، لذلك يمكننا أن نعرف ، بالنسبة لعنصر معين ، ما إذا كان ما نبحث عنه من المحتمل أن يكون أعلى أو أقل في القائمة. على سبيل المثال ، إذا بحثنا عن الرقم 42 ووجدنا 32 ، فإننا نعلم أنه سيتعين علينا البحث عن العدد الأقل.

لذا ، لنبدأ بتحليل العنصر الأوسط في القائمة. يمكننا جمع فهرس البداية ومؤشر النهاية ، ثم القسمة على اثنين لإيجاد هذا العنصر (دعنا نقرب لأسفل للتأكد من أننا وجدنا عددًا صحيحًا:


const binarySearch = (array, thingToFind, start, end) => {

 

 

 

let mid = Math.floor((start + end) / 2);







}
 
ولكن لماذا نستخدم فهارس البداية والنهاية بدلاً من length   من خاصية    المصفوفة؟

سيسمح لنا استخدام الفهارس بإعادة استخدام نفس الكود في تحديدات أصغر وأصغر من المصفوفة ، حيث ستكتشف ذلك بسرعة!

الآن بعد أن أصبح لدينا العنصر الأوسط من المصفوفة ، دعنا نتحقق مما إذا كنا ، لحسن الحظ ، قد فهمناه بشكل صحيح.


const binarySearch = (array, thingToFind, start, end) => {

 

 

 

let mid = Math.floor((start + end) / 2);







if (array[mid] === thingToFind) {



return true;



}



}
 
ستعيد الوظيفة    true  إذا تم العثور على العنصر.

إذا كنا غير محظوظين ، فلا يهم: بما أن المصفوفة مرتبة ، فنحن نعرف نصف المصفوفة التي يجب البحث فيها! لذلك ، علينا فقط أداء نفس الوظيفة بالضبط على الجزء المعني! عليك فقط تعديل إما فهرس النهاية (للبحث في النصف الأول) أو فهرس البداية (للبحث في النصف الثاني):


const binarySearch = (array, thingToFind, start, end) => {

 

 

 

let mid = Math.floor((start + end) / 2);







if (array[mid] === thingToFind) {



return true;



}







if (thingToFind < array[mid]) {



// عليك أن تنظر في النصف الأول



return binarySearch(array, thingToFind, start, mid - 1); // نستخدم (mid - 1) لأننا نعلم أننا لسنا بحاجة إلى العنصر الأوسط ، فقد تم التحقق منه بالفعل!



} else {



// عليك أن تنظر في النصف الثاني



return binarySearch(array, thingToFind, mid + 1, end);



}



}
 
ستستمر الوظيفة في استدعاء نفسها حتى تجد ما تبحث عنه. لكن هناك شيء مفقود! ماذا يحدث إذا لم يكن ما تبحث عنه موجودًا في الجدول؟ يتطلب الأمر ما يسمى بالحالة الأساسية ، أو base case ، لإخبار الوظيفة بالتوقف.

ما هي الحالة الأساسية في هذه الخوارزمية؟

سنعرف أن الخوارزمية وصلت إلى النهاية إذا حاولنا تسميتها بفهرس بداية أكبر من فهرس النهاية.

لماذا ا ؟ حسنًا ، شيئًا فشيئًا ، نقسم المصفوفة ، مرارًا وتكرارًا ، حتى نجد تحديدًا لعنصر واحد: لذلك سيكون لدينا    start = mid = end  . لذلك ، عندما تستدعي الوظيفة مرة أخرى ، ستستخدم إما    start = mid + 1  أو    end = mid - 1  ، وفقًا لبحثنا. سيكون لدينا إذن    start > end  ، ويمكن أن تعيد الدالة    false  ، لأننا نعلم أنها وصلت إلى النهاية دون العثور على ما نبحث عنه.

لذلك نضع هذه الحالة الأساسية في بداية الدالة للتحقق مما إذا كانت هذه الحالة الأخيرة:


const binarySearch = (array, thingToFind, start, end) => {

 

 

 

if (start > end) {

 

return false;

 

}

 

 

 

   let mid = Math.floor((start + end) / 2);

 

 

 

if (array[mid] === thingToFind) {

 

return true;

 

}

 

 

 

if (thingToFind < array[mid]) {

 

return binarySearch(array, thingToFind, start, mid - 1);

 

} else {

 

return binarySearch(array, thingToFind, mid + 1, end);

 

}

 

}
 
وها أنت ذا! دالة تكرارية ، تستدعي نفسها ، تقوم بإجراء بحث عن عنصر في مصفوفة مرتبة ، وترجع    true  ما إذا كان العنصر موجودًا ، أو    false  إذا لم يكن موجودًا (بفضل الحالة الأساسية)!

حذاري ! دون الحالة الأساسية  (أو مع حالة اساسية غير صحيحة)، الوظائف المتكررة يمكن أن تسبب حلقات لانهائية و  stack overflows ، لأنها سوف نواصل الاستدعاء الى ما لا نهاية ، لذا كن حذرا!

تسمى هذه الخوارزمية البحث الثنائي ، وهي تمرين يُطلب غالبًا في مقابلات العمل ، لذلك اقتربت للتو من وظيفتك الأولى كمطور!

لا تتردد أيضًا في استكشاف الأمثلة الشائعة الأخرى للخوارزميات العودية: merge sort, index sort, tree traversal…... هناك الكثير منها!

تدرب على الوظائف العودية

JavaScript
عندما نتحدث عن العودية ، هناك وظيفة هي بالفعل واحدة من الكلاسيكيات العظيمة: الوظيفة الرياضية "العاملية"! بشكل ملموس ، n  يتم تعريف مضروب الرقم   على أنه   n  مضروب الرقم   n-1  ، ومضروب   1  هو   1  .

هنا تحليل عاملي 3 لفهم أفضل:

factorielle(3) = 3 * factorielle(3 - 1)

factorielle(3) = 3 * factorielle(2) =  3 * ( 2 * factorielle(2 - 1) )

factorielle(3) = 3 * factorielle(2) =  3 * ( 2 * factorielle(1) ) = 3 * 2 * 1 = 6

إنها في النهاية وظيفة يسهل فهمها لأنها مرئية للغاية:

factorielle(7) = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040

factorielle(4) = 4 * 3 * 2 * 1 = 24

عندما ننظر إلى تحلل العامل (3) ، نرى أننا نسمي العامل مرة أخرى بالقيمة n-1 ، لذلك نحن في حالة العودية.

انتقل إلى CodePen على هذا العنوان . . مهمتك هيكتابة كود سطر الدالة العاملية 13 كمعامل   number  . نقطة مهمة: نعتبر أن العامل المضروب للأرقام أكبر من 1 ، وإلا فإن العامل سيكون مساويًا لـ 1.

الحل المقترح


انتقل إلى CodePen في هذا العنوان  لمشاهدة التصحيح.

لذلك فإن الحل يأخذ سطرين فقط:


if(number <= 1) return 1;
 
كما تم شرحه ، إذا لم يكن رقمنا أكبر من 1 ، فإن العامل يرجع 1.

else return (number * factorielle(number-1));
 
وإلا (إذا كان الرقم أكبر من 1 ، فعندئذٍ) نرجع الرقم مضروبًا في مضروب الرقم ناقص 1.

باختصار


لقد رأيت في هذا الفصل:
  • أن الوظائف العودية هي وظائف تسمي نفسها ؛
  • أن الدالة العودية تحتاج حالة أساسية ، أو base case ، حتى تتمكن من معرفة وقت انتهاء عملها ؛
  • مثال على كيفية عمل الكود ؛
  • تمرين مع وظيفة العوامل الرياضية.
ابحث في الفصل التالي عن ملخص لما تعلمته خلال هذا الجزء 3.