प्रेरण और पुनरावृत्ति के बीच सबूत के बीच संबंध क्या है?

Question

प्रेरण और पुनरावृत्ति के बीच सबूत के बीच संबंध क्या है?

मान लीजिए कि fn(n) दो,

प्रत्यावर्तन fn(n) ही मिलने base condition जब तक कॉल है,

प्रेरण तब होता है जब base condition मिलती है, (base case + 1) साबित करने का प्रयास भी सही है।

ऐसा लगता है प्रत्यावर्तन और प्रेरण अलग दिशा में कर रहे हैं। एक, n से base case शुरू होता है अन्य base case से infinite के लिए शुरू है।

कोई विवरण में विचार की व्याख्या कर सकते हैं?

Answer 1

Recursion और प्रेरण बहुत ज्यादा एक ही बात कर रहे हैं! यह स्पष्ट हो जाता है यदि आप एग्डा जैसे आश्रित प्रकारों के साथ प्रोग्रामिंग भाषा का उपयोग करते हैं, लेकिन इसे बिना किसी सीमा के प्रदर्शित किया जा सकता है।

याद रखें, Curry-Howard correspondence के कारण, प्रकार प्रस्ताव हैं और कार्यक्रम सबूत हैं। जब आप प्रकार Nat -> Nat (मैं हास्केल संकेतन का उपयोग होगा) के एक समारोह में लिख रहे हैं, तो आप यह है कि साबित करने के लिए कोशिश कर रहे हैं एक प्राकृतिक संख्या को देखते हुए अपने कार्यक्रम समाप्त और एक अन्य प्राकृतिक संख्या का उत्पादन करेगा। अब हम इस तरह की एक परिभाषा हो सकता है:

f 0 = 1 
f (1 + n) = n * f n 

जो दोनों f की एक पुनरावर्ती परिभाषा और एक ही समय में अपनी समाप्ति के एक आगमनात्मक सबूत है!

आप एक के बाद रास्ते में एक सबूत के रूप में यह पढ़ सकते हैं:

चलो साबित होता है कि च x किसी भी एक्स के लिए समाप्त हो जाता है।

• बेस केस: हमारे पास परिभाषा के अनुसार f 0 स्थिर है इसलिए यह समाप्त हो जाता है।
• अपरिवर्तनीय मामला: अगर हम मानते हैं कि f n टर्मियेट्स, f (1 + n) भी समाप्त हो जाता है (क्योंकि सभी फ़ंक्शंस इसे समाप्त करते हैं)।

ध्यान दें कि जैसे ही रिकर्सन अपने काउंटर को कम करने वाले फ़ंक्शन तक ही सीमित नहीं है, प्रेरण प्राकृतिक संख्या तक ही सीमित नहीं है। संरचनात्मक प्रेरण भी है, संरचनात्मक रिकर्सन के अनुरूप, दोनों गणित/प्रोग्रामिंग में बहुत लोकप्रिय हैं। इन्हें अधिक जटिल डेटा संरचनाओं (सूचियों/पेड़/आदि) पर चीजों को साबित करने/परिभाषित करने की कोशिश करते समय उपयोग किया जाना चाहिए।

अब, रिकर्सन/प्रेरण की "दिशा" के बारे में आपकी चिंता का समाधान करने के लिए। यहां "मांग की दिशा" और "आपूर्ति की दिशा" पर विचार करना सहायक है, जो विपरीत हैं।

जब आप रिकर्सिव फ़ंक्शन को परिभाषित करते हैं, तो मांग (विधि कॉल) बड़े मानों से बेस केस तक बहती है। दूसरी तरफ, बेस केस से आपूर्ति (वापसी मूल्य) प्रवाह पैरामीटर के बड़े मूल्यों तक बहती है। आपूर्ति के बारे में सोचने का एक और तरीका "परिभाषा" है। यह आधार के मामले में शुरू होता है और रिकर्सिव केस के माध्यम से अनंतता तक फैलता है।

अब, जब आप अपरिवर्तनीय सबूत कर रहे हैं, तो प्रमेय आपकी आपूर्ति हैं जबकि लक्ष्यों की आपकी मांग है।आप बेस केस से प्रमेय टी 0 बना सकते हैं और फिर बड़े टी में सुधार कर सकते हैं, आपको अपरिवर्तनीय मामले का उपयोग करना पसंद है: आपकी आपूर्ति 0 से अनंत तक बहती है। अब यदि आपके पास लक्ष्य जी एन है, तो आप शून्य तक पहुंचने तक अपरिवर्तनीय चरण का उपयोग करके जी (एन-के) को एक छोटे से लक्ष्य बना सकते हैं। इस तरह आपकी मांग एन से 0

जैसा कि आप देख सकते हैं, दोनों मामलों में आपूर्ति की दिशा "अनंतता" है और मांग की दिशा दोनों मामलों में "शून्य" है।

प्रेरण है जब साबित होता है कि पी एन रखती है जब आप पहली बार बार-बार लगाने से पी 0 के लिए अपने लक्ष्य को कम करने की जरूरत:

तुम भी उनके अर्थ को बदले बिना प्रेरण और प्रत्यावर्तन के वर्णन में स्पष्ट आदेश को पलट सकता है अनिवार्य मामला और उसके बाद मूल मामले का उपयोग कर परिणामी लक्ष्य साबित करें।

इसी प्रकार, रिकर्सन तब होता है जब आप पहले बेस केस को परिभाषित करते हैं और फिर पिछले मानों के संदर्भ में आगे के मूल्यों को परिभाषित करते हैं। देखें, दिशानिर्देश आसानी से बदल दिए गए हैं!