EcmaScript के दृष्टिकोण से कार्यात्मक प्रोग्रामिंग। पुनरावृत्ति और इसके प्रकार

नमस्कार, हेब्र!

आज हम EcmaScript के संदर्भ में कार्यात्मक प्रोग्रामिंग पर अपना शोध जारी रखते हैं, जिसके विनिर्देशन जावास्क्रिप्ट पर आधारित हैं। श्रृंखला के पिछले लेखों में, निम्नलिखित विषयों पर ध्यान दिया गया था:

1. शुद्ध कार्य, लंबोदर, प्रतिरक्षा
2. रचना, करी, आंशिक आवेदन

प्रत्यावर्तन

हमेशा की तरह, विकिपीडिया हमें एक परिभाषा खोजने में मदद करता है:

पुनरावृत्ति - इस वस्तु के अंदर किसी वस्तु या प्रक्रिया की परिभाषा, विवरण, छवि या स्वयं प्रक्रिया, अर्थात वह स्थिति जब वस्तु स्वयं का हिस्सा होती है। शब्द "पुनरावृत्ति" का उपयोग ज्ञान के विभिन्न विशेष क्षेत्रों में किया जाता है - भाषाविज्ञान से तर्क तक, लेकिन गणित और कंप्यूटर विज्ञान में सबसे अधिक आवेदन पाता है।

प्रोग्रामिंग के लिए, पुनरावृत्ति उन प्रक्रियाओं को संदर्भित करता है जो अपने शरीर में खुद को आह्वान करते हैं । एक पुनरावर्ती फ़ंक्शन में कई अनिवार्य घटक होते हैं:

• टर्मिनल स्थिति - समाप्ति की स्थिति
• नियम जो पुनरावृत्ति में गहरा चलता है

पुनरावृत्ति के सबसे लोकप्रिय उदाहरण पर विचार करें - तथ्यात्मक गणना।

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

हम एक पुनरावर्ती फ़ंक्शन के विशेषता घटकों को भेद करते हैं। टर्मिनल की स्थिति

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

और पुनरावृत्ति नियम

 return n * factorial(n - 1); 

यह महसूस करना महत्वपूर्ण है कि पुनरावर्तन जेएस की कुछ विशिष्ट विशेषता नहीं है, लेकिन एक तकनीक प्रोग्रामिंग में बहुत आम है।

पुनरावर्ती और पुनरावृत्त प्रक्रियाओं

पुनरावृत्ति को दो तरीकों से आयोजित किया जा सकता है: पुनरावर्ती प्रक्रिया के माध्यम से या पुनरावृत्ति के माध्यम से।

हमने पहले ही पुनरावर्ती प्रक्रिया देखी है:

 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, 4341, 6765, 10946। 17711, ... (OEIS में अनुक्रम A000045), जिसमें पहले दो संख्याएँ 1 और 1, या 0 और 1 हैं, और प्रत्येक बाद की संख्या दो पिछली संख्याओं के योग के बराबर है। पीसा के मध्ययुगीन गणितज्ञ लियोनार्डो (जिसे फिबोनाची के रूप में जाना जाता है) के नाम पर रखा गया है।

गणितीय रूप से, इस क्रम का वर्णन (और घोषणात्मक प्रोग्रामिंग वर्णन है) तैयार करना काफी सरल है:

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

अब गणित से तार्किक तर्क की ओर बढ़ते हैं (आखिरकार, हमें प्रोग्राम लॉजिक लिखने की आवश्यकता है)। फ़ाइब (5) की गणना करने के लिए, हमें फ़ाइब (4) और फ़ाइब (3) की गणना करनी होगी। फ़ाइब (4) की गणना करने के लिए, हमें फ़ाइब (3) और फ़ाइब (2) की गणना करनी होगी। फ़ाइब (3) की गणना करने के लिए, हमें अपने गणितीय मॉडल में ज्ञात मानों (1) और (2) तक फ़ाइबर (2) और इसी तरह की गणना करनी होगी।

हमारे तर्क हमें किन विचारों की ओर ले जाएं? जाहिर है, हमें पुनरावृत्ति का उपयोग करना चाहिए। थर्मल स्थिति को n <= 1. के रूप में तैयार किया जा सकता है, हालांकि, पुनरावृत्ति की एक शाखा के बजाय (पिछले उदाहरणों में), हमारी दो शाखाएँ होंगी: फ़ाइब (n-1), फ़ाइबर (n-2)।

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

इस समाधान में एक महत्वपूर्ण माइनस है! यह विभिन्न शाखाओं में n के कई बार एक ही मूल्य के परिणाम पर विचार करता है। इस समस्या को हल करने के लिए, एक कार्यात्मक प्रोग्रामिंग तकनीक है जिसे मेमोइज़ेशन कहा जाता है, जिसके बारे में हम निम्नलिखित लेखों में से एक में बात करते हैं।

निष्कर्ष

रिकर्सियन एक बहुत शक्तिशाली प्रोग्रामिंग टूल है। मुझे आपको याद दिलाना है कि, एक नियम के रूप में, हम एक पुनरावृत्त प्रक्रिया का उपयोग करते हैं। यह केवल एक पुनरावर्ती प्रक्रिया का उपयोग करने के लायक है, जब हम पुनरावृत्ति के प्रत्येक चरण में मध्यवर्ती परिणाम की गणना नहीं कर सकते।