مقدمة
التعاود الذَّيلي
تكون الدالة تعاودية ذيلية إذا كان آخر شيء تُنفذه الدالة هو استدعاء لنفسها.
في كل مرة تُستدعى فيها أي دالة، يُوضع إطار مكدس مع متغيراته المحلية ووسائطه فوق مكدس استدعاء الدوال.
وعندما تُرجع دالة، يُزال إطار المكدس من المكدس.
تتيح الدوال التعاودية الذيلية تحسين استدعاء الذيل (أو إزالة استدعاء الذيل).
وهو تحسين يسمح بإعادة استخدام إطار المكدس الأخير بواسطة استدعاء الدالة التالي عندما يُضمن أن الدالة السابقة لم تعد بحاجة إليه.
وهذا يخفف من مخاوف تجاوز سعة مكدس استدعاء الدوال، وهي حالة توجد فيها إطارات كثيرة جدًا على مكدس استدعاء الدوال بحيث لا تبقى أي ذاكرة لإنشاء إطار آخر.
تحسين استدعاء الذيل في Elm
تحت شرط معين، يستطيع مترجم Elm أن يُجري تلقائيًا تحسين استدعاء الذيل عند الترجمة إلى JavaScript.
يمكن أن يحدث التحسين في دالة تعاودية عندما تكون العملية الأخيرة في فرع ما عبارة عن استدعاء الدالة نفسها في تطبيق دالة بسيط.
لنلقِ نظرة على بعض الأمثلة:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
التنفيذ أعلاه ليس تعاوديًا ذيليًا، لأن العملية الأخيرة في فرع else هي ضرب n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
التنفيذ أعلاه تعاودي ذيلي وسيتم تحسينه، لأن العملية الأخيرة في فرع else هي استدعاء factorialHelper لنفسه.
لن يكون هذا ممكنًا لدالة بتوقيع النوع Int -> Int، وعمليًا غالبًا ما يتحقق تحسين استدعاء الذيل من خلال تعريف دوال مساعدة.
التعليمات
بيبر شغوفة جدًا بخبز الفطائر.
لا أحد يعرف إن كانت قد اختارت خبز الفطائر بسبب اسمها، أم أنها غيّرت اسمها ليطابق هوايتها.
للوهلة الأولى، لا يبدو الاحتمال الأخير مرجحًا، لكن كما ترى، فبيبر مفتونة بالفطائر تمامًا.
إنها دائمًا ما تقضي وقتها في التجربة داخل المطبخ، وتعدّل وصفاتها، وتحسّن صنعتها، مما يسعد أصدقاءها سعادة غامرة.
ما أحدث اهتماماتها؟
خبز فطائر دائرية قدر الإمكان، إلى حد الكمال الرياضي، بمساعدة رقمها المفضل، وقد خمّنته: π.
وجدت بيبر صيغة بديعة لحساب π بشكل تكراري، وهي تحويل التقارب لنيوتن/أويلر:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
ساعد بيبر على خبز فطيرتها المثالية رياضيًا بحساب π.
1. المضروب
لنبدأ بالتسخين أولًا.
يُعرَّف عامل المضروب، الذي يُكتب عادةً !، كما يلي:
0! = 1
n! = 1 * 2 * 3 * ... * n
عرّف الدالة factorial التي ستحسب المضروب بطريقة تعاودية ذيلية.
factorial 4
-- 24
2. المضروب المزدوج
يُعرَّف عامل المضروب المزدوج، الذي يُكتب عادةً !!، كما يلي:
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
عرّف الدالة doubleFactorial التي ستحسب المضروب المزدوج بطريقة تعاودية ذيلية.
factorial 5
-- 15
factorial 6
-- 48
3. تحويل التقارب لنيوتن/أويلر
عرّف الدالة pipersPi، التي ستقرّب π باستخدام عدد محدد من الحدود من صيغة تحويل التقارب لنيوتن/أويلر بطريقة تعاودية ذيلية.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
لنحسب الحد الأول معًا.
من أجل حد أعلى قيمته 0 (بدلًا من اللانهاية)، نحصل على:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
كل حد إضافي سيحسّن التقريب.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
تمرين تعلّمي
