دعنا نعود إلى الوظائف وندرسها بتعمق أكبر.
موضوعنا الأول سيكون التكرار .
إذا لم تكن جديدًا في البرمجة، فمن المحتمل أن تكون مألوفًا ويمكنك تخطي هذا الفصل.
العودية هو نمط برمجة مفيد في المواقف التي يمكن فيها تقسيم المهمة بشكل طبيعي إلى عدة مهام من نفس النوع، ولكن بشكل أبسط. أو عندما يمكن تبسيط المهمة إلى إجراء سهل بالإضافة إلى نسخة أبسط من نفس المهمة. أو، كما سنرى قريبًا، للتعامل مع هياكل بيانات معينة.
عندما تقوم إحدى الوظائف بحل مهمة ما، يمكنها في هذه العملية استدعاء العديد من الوظائف الأخرى. إحدى الحالات الجزئية لذلك هي عندما تستدعي الدالة نفسها . وهذا ما يسمى العودية .
لشيء بسيط للبدء به - دعنا نكتب دالة pow(x, n) ترفع x إلى قوة طبيعية لـ n . بمعنى آخر، يضرب x في نفسه n مرات.
الأسرى (2، 2) = 4 الأسرى (2، 3) = 8 الأسرى (2، 4) = 16
هناك طريقتان لتنفيذه.
التفكير التكراري: حلقة for :
وظيفة الأسرى (س، ن) {
دع النتيجة = 1؛
// ضرب النتيجة × ن مرات في الحلقة
لـ (دع i = 0; i < n; i++) {
النتيجة *= س؛
}
نتيجة الإرجاع؛
}
تنبيه(أسرى(2, 3)); // 8التفكير العودي: تبسيط المهمة واستدعاء الذات:
وظيفة الأسرى (س، ن) {
إذا (ن == 1) {
العودة س؛
} آخر {
إرجاع x * الأسرى(x, n - 1);
}
}
تنبيه(أسرى(2, 3)); // 8يرجى ملاحظة كيف يختلف المتغير العودي بشكل أساسي.
عند استدعاء pow(x, n) ، ينقسم التنفيذ إلى فرعين:
إذا ن==1 = س
/
الأسرى (س، ن) =
آخر = س * الأسرى (س، ن - 1) إذا كانت n == 1 ، فكل شيء تافه. يطلق عليه قاعدة العودية، لأنه ينتج على الفور النتيجة الواضحة: pow(x, 1) يساوي x .
بخلاف ذلك، يمكننا تمثيل pow(x, n) كـ x * pow(x, n - 1) . في الرياضيات، يمكن كتابة x n = x * x n-1 . وهذا ما يسمى بالخطوة العودية : نقوم بتحويل المهمة إلى إجراء أبسط (الضرب في x ) واستدعاء أبسط لنفس المهمة ( pow مع n أقل). الخطوات التالية تبسط الأمر أكثر فأكثر حتى تصل n إلى 1 .
يمكننا أيضًا أن نقول أن pow يدعو نفسه بشكل متكرر حتى n == 1 .
على سبيل المثال، لحساب pow(2, 4) يقوم المتغير العودي بالخطوات التالية:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
لذا، فإن التكرار يقلل استدعاء دالة إلى استدعاء أبسط، ثم إلى استدعاء أكثر بساطة، وهكذا، حتى تصبح النتيجة واضحة.
العودية عادة ما تكون أقصر
عادة ما يكون الحل العودي أقصر من الحل التكراري.
هنا يمكننا إعادة كتابة نفس الشيء باستخدام العامل الشرطي ? بدلاً if جعل pow(x, n) أكثر إيجازًا ولا يزال قابلاً للقراءة جدًا:
وظيفة الأسرى (س، ن) {
العودة (ن == 1) ؟ x : (x * الأسرى(x, n - 1));
} يُطلق على الحد الأقصى لعدد المكالمات المتداخلة (بما في ذلك المكالمة الأولى) عمق العودية . في حالتنا، سيكون بالضبط n .
الحد الأقصى لعمق العودية محدود بمحرك JavaScript. يمكننا الاعتماد على كونها 10000، وبعض المحركات تسمح بأكثر من ذلك، ولكن من المحتمل أن يكون 100000 خارج الحد الأقصى بالنسبة لغالبيتها. هناك تحسينات تلقائية تساعد في تخفيف هذه المشكلة ("تحسينات المكالمات الخلفية")، لكنها غير مدعومة في كل مكان حتى الآن وتعمل فقط في الحالات البسيطة.
وهذا يحد من تطبيق التكرار، لكنه لا يزال واسعًا جدًا. هناك العديد من المهام حيث توفر طريقة التفكير العودية تعليمات برمجية أبسط وأسهل في الصيانة.
الآن دعونا نفحص كيفية عمل المكالمات العودية. لذلك سننظر تحت غطاء الوظائف.
يتم تخزين المعلومات حول عملية تنفيذ وظيفة قيد التشغيل في سياق التنفيذ الخاص بها.
سياق التنفيذ عبارة عن بنية بيانات داخلية تحتوي على تفاصيل حول تنفيذ دالة: أين يوجد تدفق التحكم الآن، والمتغيرات الحالية، وقيمة this (لا نستخدمها هنا) وبعض التفاصيل الداخلية الأخرى.
يحتوي استدعاء دالة واحدة على سياق تنفيذ واحد مرتبط به بالضبط.
عندما تقوم دالة بإجراء مكالمة متداخلة، يحدث ما يلي:
تم إيقاف الوظيفة الحالية مؤقتًا.
يتم تذكر سياق التنفيذ المرتبط به في بنية بيانات خاصة تسمى مكدس سياق التنفيذ .
يتم تنفيذ المكالمة المتداخلة.
وبعد انتهائه، يتم استرداد سياق التنفيذ القديم من المكدس، ويتم استئناف الوظيفة الخارجية من حيث توقفت.
دعونا نرى ما يحدث أثناء استدعاء pow(2, 3) .
في بداية استدعاء pow(2, 3) سيخزن سياق التنفيذ المتغيرات: x = 2, n = 3 ، ويكون تدفق التنفيذ في السطر 1 من الوظيفة.
يمكننا رسمها على النحو التالي:
السياق: { س: 2، ن: 3، في السطر 1 } الأسرى (2، 3)
وذلك عندما تبدأ الوظيفة في التنفيذ. الشرط n == 1 غير صحيح، لذلك يستمر التدفق في الفرع الثاني من if :
وظيفة الأسرى (س، ن) {
إذا (ن == 1) {
العودة س؛
} آخر {
إرجاع x * الأسرى(x, n - 1);
}
}
تنبيه(أسرى(2, 3));المتغيرات هي نفسها، ولكن الخط يتغير، وبالتالي فإن السياق الآن:
السياق: { س: 2، ن: 3، في السطر 5 } الأسرى (2، 3)
لحساب x * pow(x, n - 1) ، نحتاج إلى إجراء استدعاء فرعي لـ pow باستخدام الوسائط الجديدة pow(2, 2) .
لإجراء مكالمة متداخلة، تتذكر JavaScript سياق التنفيذ الحالي في مكدس سياق التنفيذ .
هنا نسمي نفس الدالة pow ، لكن هذا لا يهم على الإطلاق. العملية هي نفسها بالنسبة لجميع الوظائف:
يتم "تذكر" السياق الحالي أعلى المكدس.
يتم إنشاء السياق الجديد للمكالمة الفرعية.
عند انتهاء الاستدعاء الفرعي - يتم إخراج السياق السابق من المكدس، ويستمر تنفيذه.
إليك مكدس السياق عندما دخلنا المكالمة الفرعية pow(2, 2) :
السياق: { س: 2، ن: 2، في السطر 1 } الأسرى (2، 2)
السياق: { س: 2، ن: 3، في السطر 5 } الأسرى (2، 3)
سياق التنفيذ الحالي الجديد موجود في الأعلى (واضح)، والسياقات السابقة التي تم تذكرها موجودة أدناه.
عندما ننتهي من الاستدعاء الفرعي، من السهل استئناف السياق السابق، لأنه يحتفظ بالمتغيرات والمكان الدقيق للكود الذي توقف فيه.
يرجى الملاحظة:
هنا في الصورة نستخدم كلمة "خط"، كما في مثالنا يوجد استدعاء فرعي واحد فقط في السطر، ولكن بشكل عام قد يحتوي سطر واحد من التعليمات البرمجية على عدة استدعاءات فرعية، مثل pow(…) + pow(…) + somethingElse(…) .
لذلك سيكون أكثر دقة أن نقول إن التنفيذ يستأنف "مباشرة بعد المكالمة الفرعية".
تتكرر العملية: يتم إجراء استدعاء فرعي جديد في السطر 5 ، الآن باستخدام الوسائط x=2 , n=1 .
يتم إنشاء سياق تنفيذ جديد، ويتم دفع السياق السابق أعلى المكدس:
السياق: { س: 2، ن: 1، في السطر 1 } الأسرى (2، 1)
السياق: { س: 2، ن: 2، في السطر 5 } الأسرى (2، 2)
السياق: { س: 2، ن: 3، في السطر 5 } الأسرى (2، 3)
يوجد الآن سياقان قديمان وسياق واحد قيد التشغيل حاليًا لـ pow(2, 1) .
أثناء تنفيذ pow(2, 1) ، على عكس السابق، يكون الشرط n == 1 صادقًا، لذا فإن الفرع الأول من if يعمل:
وظيفة الأسرى (س، ن) {
إذا (ن == 1) {
العودة س؛
} آخر {
إرجاع x * الأسرى(x, n - 1);
}
} لم تعد هناك مكالمات متداخلة، وبالتالي تنتهي الوظيفة، وترجع 2 .
عند انتهاء الوظيفة، لن تكون هناك حاجة إلى سياق التنفيذ الخاص بها، لذلك تتم إزالتها من الذاكرة. تتم استعادة العنصر السابق من أعلى المكدس:
السياق: { س: 2، ن: 2، في السطر 5 } الأسرى (2، 2)
السياق: { س: 2، ن: 3، في السطر 5 } الأسرى (2، 3)
يتم استئناف تنفيذ pow(2, 2) . يحتوي على نتيجة الاستدعاء الفرعي pow(2, 1) ، لذلك يمكنه أيضًا إنهاء تقييم x * pow(x, n - 1) ، وإرجاع 4 .
ثم يتم استعادة السياق السابق:
السياق: { س: 2، ن: 3، في السطر 5 } الأسرى (2، 3)
عندما ينتهي، لدينا نتيجة pow(2, 3) = 8 .
وكان عمق العودية في هذه الحالة: 3 .
كما نرى من الرسوم التوضيحية أعلاه، عمق التكرار يساوي الحد الأقصى لعدد السياق في المكدس.
لاحظ متطلبات الذاكرة. السياقات تأخذ الذاكرة. في حالتنا، الرفع إلى قوة n يتطلب في الواقع ذاكرة لسياقات n ، لجميع القيم الأدنى لـ n .
تعتبر الخوارزمية المستندة إلى الحلقة أكثر توفيرًا للذاكرة:
وظيفة الأسرى (س، ن) {
دع النتيجة = 1؛
لـ (دع i = 0; i < n; i++) {
النتيجة *= س؛
}
نتيجة الإرجاع؛
} يستخدم pow التكراري سياقًا واحدًا يغير i result إلى العملية. متطلبات الذاكرة الخاصة به صغيرة وثابتة ولا تعتمد على n .
يمكن إعادة كتابة أي تكرار كحلقة. عادةً ما يمكن جعل متغير الحلقة أكثر فعالية.
…ولكن في بعض الأحيان تكون إعادة الكتابة غير تافهة، خاصة عندما تستخدم الوظيفة استدعاءات فرعية متكررة مختلفة اعتمادًا على الظروف وتدمج نتائجها أو عندما يكون التفرع أكثر تعقيدًا. وقد يكون التحسين غير ضروري ولا يستحق كل هذا الجهد على الإطلاق.
يمكن أن يعطي العودية رمزًا أقصر وأسهل في الفهم والدعم. التحسينات ليست مطلوبة في كل مكان، وغالبًا ما نحتاج إلى رمز جيد، ولهذا السبب يتم استخدامه.
تطبيق آخر رائع للتكرار هو الاجتياز العودي.
تخيل، لدينا شركة. يمكن تقديم هيكل الموظفين ككائن:
دع الشركة = {
مبيعات: [{
الاسم: "جون"،
الراتب : 1000
}، {
الاسم: "أليس"،
الراتب : 1600
}]،
تطوير: {
المواقع: [{
الاسم: "بيتر"،
الراتب : 2000
}، {
الاسم: "أليكس"،
الراتب : 1800
}]،
الداخلية: [{
الاسم: "جاك"،
الراتب : 1300
}]
}
};بمعنى آخر، الشركة لديها أقسام.
قد يكون لدى القسم مجموعة من الموظفين. على سبيل المثال، قسم sales لديه موظفين: جون وأليس.
أو قد ينقسم القسم إلى أقسام فرعية، مثل أن يكون development فرعين: sites internals . كل واحد منهم لديه موظفيه الخاصين.
ومن الممكن أيضًا أنه عندما ينمو القسم الفرعي، فإنه ينقسم إلى أقسام فرعية (أو فرق).
على سبيل المثال، قد يتم تقسيم قسم sites في المستقبل إلى فرق لـ siteA و siteB . ومن المحتمل أن يتمكنوا من الانقسام أكثر. هذا ليس في الصورة، مجرد شيء يجب أن نأخذه في الاعتبار.
لنفترض الآن أننا نريد دالة للحصول على مجموع جميع الرواتب. كيف يمكننا أن نفعل ذلك؟
النهج التكراري ليس سهلا، لأن الهيكل ليس بسيطا. قد تكون الفكرة الأولى هي إنشاء for فوق company باستخدام حلقة فرعية متداخلة فوق أقسام المستوى الأول. ولكن بعد ذلك نحتاج إلى المزيد من الحلقات الفرعية المتداخلة للتكرار على الموظفين في أقسام المستوى الثاني مثل sites ... ثم نحتاج إلى حلقات فرعية أخرى داخل تلك الأقسام الخاصة بأقسام المستوى الثالث التي قد تظهر في المستقبل؟ إذا وضعنا 3-4 حلقات فرعية متداخلة في الكود لاجتياز كائن واحد، فسيصبح الأمر قبيحًا إلى حد ما.
دعونا نحاول العودية.
كما نرى، عندما تحصل وظيفتنا على مجموع قسم، هناك حالتان محتملتان:
إما أن يكون قسمًا "بسيطًا" يضم مجموعة من الأشخاص - فيمكننا بعد ذلك جمع الرواتب في حلقة بسيطة.
أو أنه كائن يحتوي على N أقسام فرعية - ثم يمكننا إجراء N استدعاءات متكررة للحصول على مجموع كل قسم من الأقسام الفرعية ودمج النتائج.
الحالة الأولى هي أساس العودية، الحالة التافهة، عندما نحصل على مصفوفة.
الحالة الثانية عندما نحصل على كائن هي الخطوة العودية. يتم تقسيم المهمة المعقدة إلى مهام فرعية للأقسام الأصغر. وقد ينقسمون بدورهم مرة أخرى، ولكن عاجلاً أم آجلاً سينتهي الانقسام عند (1).
ربما تكون الخوارزمية أسهل في القراءة من الكود:
Let Company = { // نفس الكائن، مضغوطًا للإيجاز
المبيعات: [{الاسم: 'جون'، الراتب: 1000}، {الاسم: 'أليس'، الراتب: 1600 }]،
تطوير: {
المواقع: [{الاسم: 'بيتر'، الراتب: 2000}، {الاسم: 'أليكس'، الراتب: 1800 }]،
الداخليون: [{الاسم: "جاك"، الراتب: 1300}]
}
};
// الوظيفة للقيام بهذه المهمة
دالة مجموع الرواتب (القسم) {
إذا (Array.isArray(department)) {// الحالة (1)
قسم العودة. تقليل ((السابق، الحالي) => السابق + الحالي. الراتب، 0)؛ // جمع المصفوفة
} آخر {// الحالة (2)
دع المبلغ = 0؛
لـ (دع القسم الفرعي لـ Object.values(department)) {
sum += sumSalaries(subdep); // استدعاء الأقسام الفرعية بشكل متكرر، وجمع النتائج
}
مبلغ الإرجاع؛
}
}
تنبيه(sumSalaries(شركة)); // 7700الكود قصير وسهل الفهم (نأمل؟). هذه هي قوة العودية. كما أنه يعمل على أي مستوى من تداخل الأقسام الفرعية.
إليك الرسم البياني للمكالمات:
يمكننا أن نرى بسهولة المبدأ: بالنسبة للكائن {...} يتم إجراء استدعاءات فرعية، في حين أن المصفوفات [...] هي "أوراق" شجرة العودية، فهي تعطي نتيجة فورية.
لاحظ أن الكود يستخدم الميزات الذكية التي تناولناها من قبل:
تم شرح طريقة arr.reduce في الفصل طرق المصفوفة للحصول على مجموع المصفوفة.
قم بإجراء حلقة for(val of Object.values(obj)) للتكرار عبر قيم الكائنات: تقوم Object.values بإرجاع مصفوفة منها.
بنية البيانات العودية (المحددة بشكل متكرر) هي بنية تنسخ نفسها في أجزاء.
لقد رأينا ذلك للتو في مثال هيكل الشركة أعلاه.
قسم الشركة هو :
إما مجموعة من الناس.
أو كائن مع الإدارات .
بالنسبة لمطوري الويب، هناك أمثلة أكثر شهرة: مستندات HTML وXML.
في مستند HTML، قد تحتوي علامة HTML على قائمة بما يلي:
قطع النص.
تعليقات HTML.
علامات HTML الأخرى (والتي بدورها قد تحتوي على أجزاء نصية/تعليقات أو علامات أخرى وما إلى ذلك).
هذا مرة أخرى تعريف عودي.
من أجل فهم أفضل، سنغطي بنية متكررة أخرى تسمى "القائمة المرتبطة" والتي قد تكون بديلاً أفضل للمصفوفات في بعض الحالات.
تخيل أننا نريد تخزين قائمة مرتبة من الكائنات.
سيكون الاختيار الطبيعي عبارة عن مصفوفة:
Let arr = [obj1, obj2, obj3];
…ولكن هناك مشكلة مع المصفوفات. تعتبر عمليات "حذف العنصر" و"إدراج العنصر" باهظة الثمن. على سبيل المثال، يجب أن تقوم عملية arr.unshift(obj) بإعادة ترقيم جميع العناصر لإفساح المجال obj جديد، وإذا كان المصفوفة كبيرة، فسيستغرق الأمر وقتًا. نفس الشيء مع arr.shift() .
التعديلات الهيكلية الوحيدة التي لا تتطلب إعادة ترقيم جماعي هي تلك التي تعمل مع نهاية المصفوفة: arr.push/pop . لذلك يمكن أن تكون المصفوفة بطيئة جدًا بالنسبة لقوائم الانتظار الكبيرة، عندما يتعين علينا العمل مع البداية.
وبدلاً من ذلك، إذا كنا بحاجة حقًا إلى الإدراج/الحذف السريع، فيمكننا اختيار بنية بيانات أخرى تسمى القائمة المرتبطة.
يتم تعريف عنصر القائمة المرتبطة بشكل متكرر ككائن مع:
value .
تشير الخاصية next إلى عنصر القائمة المرتبطة التالي أو null إذا كانت هذه هي النهاية.
على سبيل المثال:
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
};التمثيل البياني للقائمة:
رمز بديل للإنشاء:
اسمحوا القائمة = {القيمة: 1}؛
list.next = {القيمة: 2};
list.next.next = { القيمة: 3 };
list.next.next.next = { القيمة: 4 };
list.next.next.next.next = null; هنا يمكننا أن نرى بشكل أكثر وضوحًا أن هناك كائنات متعددة، كل منها له value ويشير next إلى جاره. متغير list هو الكائن الأول في السلسلة، لذا باتباع المؤشرات next منه يمكننا الوصول إلى أي عنصر.
يمكن تقسيم القائمة بسهولة إلى أجزاء متعددة ثم ضمها مرة أخرى لاحقًا:
دع SecondList = list.next.next; list.next.next = null;
للانضمام:
list.next.next = SecondList;
وبالتأكيد يمكننا إدراج العناصر أو إزالتها في أي مكان.
على سبيل المثال، لإضافة قيمة جديدة، نحتاج إلى تحديث رأس القائمة:
اسمحوا القائمة = {القيمة: 1}؛
list.next = {القيمة: 2};
list.next.next = { القيمة: 3 };
list.next.next.next = { القيمة: 4 };
// إضافة القيمة الجديدة إلى القائمة
list = { value: "new item"، next: list }; لإزالة قيمة من المنتصف، قم بتغيير القيمة next للقيمة السابقة:
list.next = list.next.next;
لقد جعلنا list.next يقفز فوق 1 إلى القيمة 2 . تم الآن استبعاد القيمة 1 من السلسلة. إذا لم يتم تخزينه في أي مكان آخر، فسيتم إزالته تلقائيًا من الذاكرة.
على عكس المصفوفات، لا يوجد إعادة ترقيم جماعي، يمكننا بسهولة إعادة ترتيب العناصر.
وبطبيعة الحال، القوائم ليست دائما أفضل من المصفوفات. وإلا فإن الجميع سيستخدمون القوائم فقط.
العيب الرئيسي هو أنه لا يمكننا الوصول بسهولة إلى العنصر من خلال رقمه. في مصفوفة سهلة: arr[n] هو مرجع مباشر. لكن في القائمة علينا أن نبدأ من العنصر الأول وننتقل next N مرات للحصول على العنصر N.
…لكننا لا نحتاج دائمًا إلى مثل هذه العمليات. على سبيل المثال، عندما نحتاج إلى قائمة انتظار أو حتى deque - البنية المرتبة التي يجب أن تسمح بإضافة/إزالة العناصر بسرعة كبيرة من كلا الطرفين، ولكن ليس هناك حاجة للوصول إلى وسطها.
يمكن تعزيز القوائم:
يمكننا إضافة خاصية prev بالإضافة إلى next للإشارة إلى العنصر السابق، للرجوع للخلف بسهولة.
يمكننا أيضًا إضافة متغير باسم tail يشير إلى العنصر الأخير في القائمة (وتحديثه عند إضافة/إزالة عناصر من النهاية).
…قد تختلف بنية البيانات وفقًا لاحتياجاتنا.
شروط:
العودية هو مصطلح برمجة يعني استدعاء دالة من نفسها. يمكن استخدام الوظائف العودية لحل المهام بطرق أنيقة.
عندما تستدعي دالة نفسها، فهذا يسمى خطوة العودية . أساس العودية هو وسيطات الوظيفة التي تجعل المهمة بسيطة جدًا بحيث لا تقوم الوظيفة بإجراء المزيد من الاستدعاءات.
بنية البيانات المحددة بشكل متكرر هي بنية بيانات يمكن تعريفها باستخدام نفسها.
على سبيل المثال، يمكن تعريف القائمة المرتبطة على أنها بنية بيانات تتكون من كائن يشير إلى قائمة (أو فارغة).
القائمة = {القيمة، التالي -> القائمة }الأشجار مثل شجرة عناصر HTML أو شجرة الأقسام من هذا الفصل هي أيضًا متكررة بشكل طبيعي: لها فروع ويمكن أن يكون لكل فرع فروع أخرى.
يمكن استخدام الدوال العودية لتسييرها كما رأينا في مثال sumSalary .
يمكن إعادة كتابة أي دالة عودية إلى دالة تكرارية. وهذا مطلوب أحيانًا لتحسين الأشياء. ولكن بالنسبة للعديد من المهام، يكون الحل العودي سريعًا بدرجة كافية وأسهل في الكتابة والدعم.
الأهمية: 5
اكتب دالة sumTo(n) تحسب مجموع الأعداد 1 + 2 + ... + n .
على سبيل المثال:
المجموع(1) = 1 مجموع(2) = 2 + 1 = 3 مجموع(3) = 3 + 2 + 1 = 6 مجموع(4) = 4 + 3 + 2 + 1 = 10 ... مجموع (100) = 100 + 99 + ... + 2 + 1 = 5050
قم بإنشاء 3 متغيرات للحل:
باستخدام حلقة for.
باستخدام التكرار، السبب sumTo(n) = n + sumTo(n-1) لـ n > 1 .
باستخدام صيغة التقدم الحسابي.
مثال على النتيجة:
دالة sumTo(n) { /*... الكود الخاص بك ... */ }
تنبيه(مجموع(100)); // 5050ملاحظة: ما هو البديل الحل الأسرع؟ الأبطأ؟ لماذا؟
PPS هل يمكننا استخدام العودية لحساب sumTo(100000) ؟
الحل باستخدام الحلقة :
دالة مجموع (ن) {
دع المبلغ = 0؛
لـ (دع i = 1؛ i <= n؛ i++) {
مجموع += أنا؛
}
مبلغ الإرجاع؛
}
تنبيه(مجموع(100));الحل باستخدام العودية:
دالة مجموع (ن) {
إذا (ن == 1) قم بإرجاع 1؛
return n + sumTo(n - 1);
}
تنبيه(مجموع(100)); الحل باستخدام الصيغة: sumTo(n) = n*(n+1)/2 :
دالة مجموع (ن) {
العودة ن * (ن + 1) / 2؛
}
تنبيه(مجموع(100)); ملاحظة: بطبيعة الحال، الصيغة هي الحل الأسرع. يستخدم 3 عمليات فقط لأي رقم n . الرياضيات تساعد!
متغير الحلقة هو الثاني من حيث السرعة. في كل من البديل العودي والحلقة، نقوم بجمع نفس الأرقام. لكن العودية تتضمن مكالمات متداخلة وإدارة مكدس التنفيذ. وهذا يتطلب أيضًا موارد، لذا فهو أبطأ.
تدعم بعض المحركات تحسين "المكالمة الخلفية": إذا كانت المكالمة المتكررة هي الأخيرة في الوظيفة، دون إجراء أي حسابات أخرى، فلن تحتاج الوظيفة الخارجية إلى استئناف التنفيذ، لذلك لا يحتاج المحرك إلى تذكر سياق التنفيذ الخاص به. وهذا يزيل العبء عن الذاكرة. ولكن إذا كان محرك JavaScript لا يدعم تحسين الاستدعاء الخلفي (معظمهم لا يدعمه)، فسيكون هناك خطأ: تم تجاوز الحد الأقصى لحجم المكدس، لأنه عادة ما يكون هناك قيود على إجمالي حجم المكدس.
الأهمية: 4
مضروب العدد الطبيعي هو رقم مضروب في "number minus one" ، ثم في "number minus two" ، وهكذا حتى 1 . يُشار إلى مضروب n بالرمز n!
يمكننا أن نكتب تعريف العامل مثل هذا:
ن! = ن * (ن - 1) * (ن - 2) * ...*1
قيم مضروبات n المختلفة :
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120
المهمة هي كتابة factorial(n) الذي يحسب n! باستخدام المكالمات العودية.
تنبيه(مضروب(5)); // 120
تلميح ملاحظة: n! يمكن كتابتها كـ n * (n-1)! على سبيل المثال: 3! = 3*2! = 3*2*1! = 6
بحكم التعريف، مضروب n! يمكن كتابتها كـ n * (n-1)! .
بمعنى آخر، يمكن حساب نتيجة factorial(n) على شكل n مضروبًا في نتيجة factorial(n-1) . ويمكن أن ينزل استدعاء n-1 بشكل متكرر إلى الأسفل ثم إلى الأسفل حتى 1 .
مضروب الدالة (ن) {
العودة (ن ! = 1) ؟ ن * مضروب(ن - 1): 1;
}
تنبيه(مضروب(5)); // 120 أساس العودية هو القيمة 1 . يمكننا أيضًا أن نجعل 0 هو الأساس هنا، وهذا لا يهم كثيرًا، لكنه يعطي خطوة عودية أخرى:
مضروب الدالة (ن) {
العودة ن؟ ن * مضروب(ن - 1): 1;
}
تنبيه(مضروب(5)); // 120الأهمية: 5
تسلسل أرقام فيبوناتشي له الصيغة F n = F n-1 + F n-2 . بمعنى آخر، الرقم التالي هو مجموع الرقمين السابقين.
أول رقمين هما 1 ، ثم 2(1+1) ، ثم 3(1+2) ، 5(2+3) وهكذا: 1, 1, 2, 3, 5, 8, 13, 21... .
ترتبط أرقام فيبوناتشي بالنسبة الذهبية والعديد من الظواهر الطبيعية من حولنا.
اكتب دالة fib(n) تُرجع رقم فيبوناتشي n-th .
مثال على العمل:
وظيفة fib(n) { /* الكود الخاص بك */ }
تنبيه (كذوب (3))؛ // 2
تنبيه (كذوب (7))؛ // 13
تنبيه (كفي (77))؛ // 5527939700884757 ملحوظة: يجب أن تكون الوظيفة سريعة. يجب ألا يستغرق استدعاء fib(77) أكثر من جزء من الثانية.
الحل الأول الذي يمكننا تجربته هنا هو الحل العودي.
أرقام فيبوناتشي متكررة حسب التعريف:
وظيفة فيب (ن) {
العودة ن <= 1؟ ن : فيب(ن - 1) + فيب(ن - 2);
}
تنبيه(كذوب(3)); // 2
تنبيه(كذوب(7)); // 13
// فيب (77)؛ // سيكون بطيئا للغاية! …ولكن بالنسبة للقيم الكبيرة لـ n يكون الأمر بطيئًا جدًا. على سبيل المثال، قد يوقف fib(77) المحرك لبعض الوقت ويستهلك جميع موارد وحدة المعالجة المركزية.
وذلك لأن الوظيفة تقوم بإجراء عدد كبير جدًا من الاستدعاءات الفرعية. ويتم إعادة تقييم نفس القيم مرارًا وتكرارًا.
على سبيل المثال، دعونا نرى جزءًا من العمليات الحسابية لـ fib(5) :
... فيب(5) = فيب(4) + فيب(3) فيب(4) = فيب(3) + فيب(2) ...
هنا يمكننا أن نرى أن قيمة fib(3) مطلوبة لكل من fib(5) و fib(4) . لذلك سيتم استدعاء fib(3) وتقييمه مرتين بشكل مستقل تمامًا.
إليك شجرة العودية الكاملة:
يمكننا أن نلاحظ بوضوح أنه يتم تقييم fib(3) مرتين ويتم تقييم fib(2) ثلاث مرات. ينمو المبلغ الإجمالي للحسابات بشكل أسرع بكثير من n ، مما يجعله هائلاً حتى بالنسبة لـ n=77 .
يمكننا تحسين ذلك من خلال تذكر القيم التي تم تقييمها بالفعل: إذا تم حساب قيمة fib(3) مرة واحدة، فيمكننا إعادة استخدامها في الحسابات المستقبلية.
البديل الآخر هو التخلي عن العودية واستخدام خوارزمية مختلفة تمامًا تعتمد على الحلقة.
بدلاً من الانتقال من n إلى قيم أقل، يمكننا عمل حلقة تبدأ من 1 و 2 ، ثم نحصل على fib(3) كمجموعهما، ثم fib(4) كمجموع القيمتين السابقتين، ثم fib(5) ويصعد ويصعد حتى يصل إلى القيمة المطلوبة. في كل خطوة نحتاج فقط إلى تذكر القيمتين السابقتين.
فيما يلي خطوات الخوارزمية الجديدة بالتفصيل.
البداية:
// a = fib(1)، b = fib(2)، هذه القيم حسب التعريف 1 دع أ = 1، ب = 1؛ // احصل على c = fib(3) كمجموعهم دع ج = أ + ب؛ /* لدينا الآن أكذوبة (1)، أكذوبة (2)، أكذوبة (3) أ ب ج 1، 1، 2 */
الآن نريد الحصول على fib(4) = fib(2) + fib(3) .
دعنا نغير المتغيرات: a,b سيحصل على fib(2),fib(3) و c سيحصل على مجموعهم:
أ = ب؛ // الآن أ = فيب (2) ب = ج؛ // الآن ب = فيب (3) ج = أ + ب؛ // ج = فيب (4) /* الآن لدينا التسلسل: أ ب ج 1، 1، 2، 3 */
الخطوة التالية تعطي رقم تسلسلي آخر:
أ = ب؛ // الآن أ = فيب (3)
ب = ج؛ // الآن ب = فيب (4)
ج = أ + ب؛ // ج = فيب (5)
/* الآن التسلسل هو (رقم آخر):
أ ب ج
1، 1، 2، 3، 5
*/...وهكذا حتى نحصل على القيمة المطلوبة. وهذا أسرع بكثير من العودية ولا يتضمن أي حسابات مكررة.
الكود الكامل:
وظيفة فيب (ن) {
دع = 1؛
دع ب = 1؛
لـ (دع i = 3؛ i <= n؛ i++) {
دع ج = أ + ب؛
أ = ب؛
ب = ج؛
}
العودة ب؛
}
تنبيه(كذوب(3)); // 2
تنبيه(كذوب(7)); // 13
تنبيه(كذوب(77)); // 5527939700884757 تبدأ الحلقة بـ i=3 ، لأن قيم التسلسل الأول والثاني يتم ترميزهما بشكل ثابت في متغيرات a=1 , b=1 .
يُطلق على هذا النهج اسم البرمجة الديناميكية من أسفل إلى أعلى.
الأهمية: 5
لنفترض أن لدينا قائمة مرتبطة واحدة (كما هو موضح في فصل العودية والمكدس):
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
}; اكتب وظيفة printList(list) التي تقوم بإخراج عناصر القائمة واحدًا تلو الآخر.
قم بعمل نوعين مختلفين من الحل: استخدام الحلقة واستخدام العودية.
ما هو الأفضل: مع العودية أو بدونها؟
البديل القائم على الحلقة للحل:
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
};
وظيفة طباعة القائمة (قائمة) {
دع tmp = قائمة؛
بينما (تمب) {
تنبيه (tmp.value)؛
tmp = tmp.next;
}
}
printList(list); يرجى ملاحظة أننا نستخدم متغيرًا مؤقتًا tmp للتجول في القائمة. من الناحية الفنية، يمكننا استخدام list معلمات الدالة بدلاً من ذلك:
وظيفة طباعة القائمة (قائمة) {
بينما (قائمة) {
تنبيه(list.value);
قائمة = list.next;
}
} … ولكن هذا لن يكون من الحكمة. في المستقبل قد نحتاج إلى توسيع وظيفة ما، أو القيام بشيء آخر بالقائمة. إذا قمنا بتغيير list ، فإننا نفقد هذه القدرة.
عند الحديث عن أسماء المتغيرات الجيدة، list هنا هي القائمة نفسها. العنصر الأول منه. ويجب أن يبقى الأمر كذلك. هذا واضح وموثوق.
من الجانب الآخر، دور tmp هو حصرًا اجتياز القائمة، كما هو i في حلقة for .
يتبع المتغير العودي لـ printList(list) منطقًا بسيطًا: لإخراج قائمة، يجب علينا إخراج list العناصر الحالية، ثم نفعل الشيء نفسه مع list.next :
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
};
وظيفة طباعة القائمة (قائمة) {
تنبيه(list.value); // إخراج العنصر الحالي
إذا (القائمة التالية) {
printList(list.next); // افعل الشيء نفسه بالنسبة لبقية القائمة
}
}
printList(list);الآن ما هو أفضل؟
من الناحية الفنية، الحلقة أكثر فعالية. هذين المتغيرين يفعلان نفس الشيء، لكن الحلقة لا تنفق الموارد لاستدعاءات الوظائف المتداخلة.
من ناحية أخرى، يكون المتغير العودي أقصر وأسهل في بعض الأحيان للفهم.
الأهمية: 5
إخراج قائمة مرتبطة واحدة من المهمة السابقة إخراج قائمة مرتبطة واحدة بترتيب عكسي.
قم بإجراء حلين: استخدام الحلقة واستخدام التكرار.
المنطق العودي صعب بعض الشيء هنا.
نحتاج أولاً إلى إخراج بقية القائمة ثم إخراج القائمة الحالية:
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
};
وظيفة طباعة عكسية (قائمة) {
إذا (القائمة التالية) {
printReverseList(list.next);
}
تنبيه(list.value);
}
printReverseList(list);
يعد متغير الحلقة أيضًا أكثر تعقيدًا قليلاً من الإخراج المباشر.
لا توجد طريقة للحصول على القيمة الأخيرة في list . نحن أيضاً لا نستطيع "العودة".
إذن ما يمكننا فعله هو أولاً مراجعة العناصر بالترتيب المباشر وتذكرها في مصفوفة، ثم إخراج ما تذكرناه بالترتيب العكسي:
قائمة السماح = {
القيمة: 1،
التالي: {
القيمة: 2،
التالي: {
القيمة: 3،
التالي: {
القيمة: 4،
التالي: فارغة
}
}
}
};
وظيفة طباعة عكسية (قائمة) {
دع arr = [];
دع tmp = قائمة؛
بينما (تمب) {
arr.push(tmp.value);
tmp = tmp.next;
}
لـ (دع i = arr.length - 1; i >= 0; i--) {
تنبيه (arr[i])؛
}
}
printReverseList(list);يرجى ملاحظة أن الحل العودي يفعل الشيء نفسه تمامًا: فهو يتبع القائمة، ويتذكر العناصر الموجودة في سلسلة الاستدعاءات المتداخلة (في مكدس سياق التنفيذ)، ثم يقوم بإخراجها.