جافا سكريبت الذيل العودية الأمثل

مرحبا القارئ.

في بعض الأحيان لحل المشكلة ، عليك استخدام Recursion ، الذي له إيجابيات وسلبيات. واجهت مشكلة تجاوز سعة المكدس.

الحد الأقصى لعمق العودية محدد بواسطة محرك JavaScript. يمكنك الاعتماد بدقة على 10000 مكالمة متداخلة ، يسمح بعض المترجمين الفوريين بالمزيد ، لكن بالنسبة لمعظمهم 100000 مكالمة خارج نطاق القدرات. هناك تحسينات تلقائية تساعد على تجنب تجاوز مكدس المكالمة ("تحسين تكرار العودية الذيل") ، لكنها غير مدعومة بعد في كل مكان وتعمل فقط للحالات البسيطة.

مثال على دالة متكررة:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

يتيح الرجوع إلى الذيل تحسين المكالمات من قبل المترجم وهو موجود بالفعل في المعيار ES6 ، لكن دعم المتصفح يترك الكثير مما هو مرغوب فيه .

مثال على وظيفة ذيل العودية:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

ولكن بدون دعم المستعرض ، سنواجه نفس المشكلة - تجاوز سعة مكدس الذاكرة المؤقتة. يمكننا محاولة استخدام جنبا إلى جنب مع الترامبولين .

سنقوم بكتابة ديكور يأخذ وظيفة عودية معدلة (الخطوة التالية) وتنفيذها في حلقة ، دون زيادة عمق المكالمة.

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

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

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

نستخدم:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

هذا هو مقالي الأول. حاولت عدم إعادة سرد المفاهيم وأشرت إلى وجود صلة بالمصادر. هذا الموضوع ليس فريدًا وقد وجد منذ فترة طويلة على مواقع باللغة الإنجليزية ، لكنني لم أجده باللغة الروسية لسوء الحظ.

شكرا لاهتمامكم اتمنى لك يوم لطيف :)

تحديث
الأداء:

# 1 العودية




# 2 التكرار




# 3 ذيل العودية والترامبولين




# 4 ذيل الإعادة والترامبولين (عدد كبير)




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