البرمجة الوظيفية من وجهة نظر EcmaScript. العودية وأنواعها

مرحبا يا هبر!

نواصل اليوم بحثنا حول البرمجة الوظيفية في سياق EcmaScript ، والتي تعتمد مواصفاتها على JavaScript. في المقالات السابقة من الدورة ، تم النظر في المواضيع التالية:

1. وظائف نقية ، lambdas ، الحصانة
2. التكوين ، الكاري ، التطبيق الجزئي

العودية

كما هو الحال دائمًا ، تساعدنا Wikipedia في العثور على تعريف:

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

بالنسبة للبرمجة ، يشير العودية إلى العمليات التي تستدعي نفسها في أجسامها . تحتوي الدالة العودية على عدة مكونات إلزامية:

• حالة المحطة - حالة الإنهاء
• القاعدة التي تتحرك في عمق العودية

النظر في المثال الأكثر شعبية من العودية - حساب فصيل.

const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); } 

نحن نميز المكونات المميزة لوظيفة عودية. حالة المحطة

  if (n === 0) { return 1; } 

وحكم العودية

 return n * factorial(n - 1); 

من المهم أن ندرك أن الإعادة ليست ميزة محددة لـ JS ، ولكنها تقنية شائعة جدًا في البرمجة.

عمليات تكرارية وتكرارية

يمكن تنظيم العودية بطريقتين: من خلال عملية تكرارية أو من خلال عملية تكرارية.

لقد رأينا بالفعل عملية العودية:

 const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); } 

سيبدو الحل التكراري لمشكلة الفصائل كما يلي:

 const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); }; 

كل من هذه الخيارات هي العودية. يتميز كلا الحلين بخاصية المميزة للتكرار: حالة المحطة وقاعدة الحركة على طول العودية. دعنا ننظر إلى خلافاتهم.

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

يبدو شيء مثل هذا:

 factorial(3); // 6  ,    3 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6; 

كما ترون ، الفكرة الأساسية لعملية تكرارية هي تأجيل الحساب إلى النهاية.
تولد مثل هذه العملية حالة زمنية مختلفة يتم تخزينها "في مكان ما" خارج استدعاء الوظيفة الحالية.

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

تختلف العملية التكرارية عن العملية المتكررة في عدد محدد من الحالات. في كل خطوة ، تراعي العملية التكرارية كل ما يمكن حسابه ، لذلك كل خطوة من العودية موجودة بشكل مستقل عن الخطوة السابقة.

يبدو مثل هذا:

 iter(3, 1); // iter(3 - 1, 1 * 3); // ,      6, iter(2, 3); // iter(2 - 1, 2 * 3);//   ,      3 iter(1, 6); // counter === 1, return 6 6; 

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

شجرة العودية

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

لفهم تكرار شجرة بشكل أفضل ، دعونا نلقي نظرة على مثال بسيط وشائع - أرقام فيبوناتشي.

أرقام فيبوناتشي - عناصر من تسلسل رقمي 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ، 233 ، 377 ، 610 ، 987 ، 1597 ، 2584 ، 4181 ، 6765 ، 10946 ، 17711 ، ... (التسلسل A000045 في OEIS) ، حيث يكون الرقمان الأولان إما 1 و 1 ، أو 0 و 1 ، وكل رقم لاحق يساوي مجموع الرقمين السابقين. سمي على اسم عالم الرياضيات من القرون الوسطى ليوناردو بيزا (المعروف باسم فيبوناتشي).

من الناحية الرياضية ، من السهل جدًا صياغة وصف (والبرمجة التوضيحية هي الوصف) لهذا التسلسل:

 fib(n) = [  0  n = 0,//(1)  1  n = 1,//(2) fib(n-1) + fib(n-2)     ] 

الآن دعنا ننتقل من الرياضيات إلى التفكير المنطقي (بعد كل شيء ، نحتاج إلى كتابة منطق البرنامج). لحساب fib (5) ، يتعين علينا حساب fib (4) و fib (3). لحساب fib (4) ، يتعين علينا حساب fib (3) و fib (2). لحساب fib (3) ، يتعين علينا حساب fib (2) وما إلى ذلك حتى نصل إلى القيم المعروفة (1) و (2) في نموذجنا الرياضي.

ما هي الأفكار التي ينبغي أن يقودنا إليها منطقنا؟ من الواضح ، يجب علينا استخدام العودية. يمكن صياغة الحالة الحرارية كـ n <= 1. ومع ذلك ، بدلاً من فرع واحد من العودية (كما في الأمثلة السابقة) ، سيكون لدينا فرعين: fib (n-1) ، fib (n-2).

 const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2)); 

هذا الحل لديه ناقص كبير! وهو يأخذ في الاعتبار نتيجة نفس القيمة n عدة مرات في فروع مختلفة. لحل هذه المشكلة ، هناك تقنية برمجة وظيفية تسمى memoization ، والتي نتحدث عنها في أحد المقالات التالية.

استنتاج

العودية هي أداة برمجة قوية للغاية. اسمحوا لي أن أذكرك بأننا ، كقاعدة عامة ، نستخدم عملية تكرارية. يجدر استخدام عملية تكرارية فقط إذا لم نتمكن من حساب النتيجة الوسيطة في كل خطوة من خطوات العودية.