>> ZAMYLA: समझने के क्रम में प्रत्यावर्तन, तुम चाहिए
पहले प्रत्यावर्तन को समझते हैं.
कार्यक्रम के डिजाइन का मतलब प्रत्यावर्तन के बाद आप आत्म referential है कि
परिभाषाएँ.
पुनरावर्ती डाटा संरचनाओं, उदाहरण के लिए, डेटा संरचनाओं हैं कि
में खुद को शामिल उनकी परिभाषा.
लेकिन आज, हम ध्यान केंद्रित करने जा रहे हैं पुनरावर्ती कार्यों पर.
>> , कार्यों आदानों ले याद है कि तर्क, और के रूप में एक मूल्य वापसी उनके
द्वारा प्रतिनिधित्व किया उत्पादन यहाँ इस चित्र.
हम शरीर के रूप में बॉक्स के बारे में सोचता हूँ सेट की युक्त समारोह,
व्याख्या कि निर्देश इनपुट और आउटपुट प्रदान करते हैं.
शरीर के अंदर एक करीब देखो ले रहा है समारोह के लिए कॉल बता सकता है
अन्य कार्यों के रूप में अच्छी तरह से.
इस सादे समारोह, Foo, लो कि निवेश के रूप में एक स्ट्रिंग लेता है और
प्रिंट कितने पत्र कि स्ट्रिंग है.
स्ट्रिंग की लंबाई के लिए समारोह strlen,, जिसका उत्पादन है, कहा जाता है
printf के लिए कॉल के लिए जरूरी है.
>> अब, क्या एक पुनरावर्ती समारोह बनाता है विशेष यह है कि खुद फोन है.
हम इस पुनरावर्ती प्रतिनिधित्व कर सकते हैं इस नारंगी तीर के साथ फोन
वापस स्वयं पाशन.
लेकिन फिर खुद को क्रियान्वित ही होगा एक और पुनरावर्ती फोन करना, और
एक और एक और.
लेकिन पुनरावर्ती कार्य अनंत नहीं हो सकता.
वे किसी भी तरह समाप्त करने के लिए है, या आपके कार्यक्रम हमेशा के लिए चला जाएगा.
>> तो हम तोड़ने के लिए एक रास्ता खोजने की जरूरत पुनरावर्ती कॉल के बाहर.
हम आधार मामले कहते हैं.
बेस मामले शर्त पूरी करते हैं, समारोह बनाने के बिना रिटर्न
एक और पुनरावर्ती कॉल.
एक शून्य समारोह, हाय, इस समारोह लो कि निवेश के रूप में एक पूर्णांक n लेता है.
आधार के मामले पहले आता है.
N शून्य से भी कम, प्रिंट अलविदा और है तो अन्य सभी मामलों के लिए बदले,
समारोह हाय प्रिंट और अमल करेंगे पुनरावर्ती कॉल.
साथ समारोह हाय करने के लिए एक और फोन एक decremented इनपुट मूल्य.
>> अब, हम, हाय मुद्रित भले ही समारोह समाप्त नहीं होगा जब तक हम
अपनी वापसी प्रकार लौटने, इस मामले शून्य में.
तो हर n आधार मामले के अलावा अन्य के लिए, इस समारोह हाय हाय वापसी करेंगे
n के शून्य से 1.
इस समारोह हालांकि शून्य है, हम यहाँ स्पष्ट रूप से वापसी प्रकार नहीं होगा.
हम सिर्फ समारोह को अंजाम देंगे.
तो हाय बुला (3) हाय प्रिंट और होगा हाय (2) (1) एक हाय कार्यान्वित जो निष्पादित
हाय कार्यान्वित जो (0), जहां बेस मामले शर्त पूरी कर रहा है.
तो हाय (0) अलविदा प्रिंट और रिटर्न.
>> ठीक है.
तो अब हम की मूल बातें समझ है कि जरूरत है कि वे पुनरावर्ती कार्यों,
कम से कम एक आधार के मामले के साथ ही एक पुनरावर्ती कॉल, चलो एक पर चलते हैं
अधिक सार्थक उदाहरण.
अभी वापस नहीं करता है कि एक कोई बात नहीं क्या शून्य.
>> के भाज्य पर एक नज़र रखना आपरेशन में सबसे अधिक इस्तेमाल किया
संभावना गणना.
N के भाज्य हर उत्पाद है से सकारात्मक पूर्णांक कम
और एन के बराबर.
तो भाज्य पांच 5 गुना 4 गुना है 3 बार 2 बार 1 120 देने के लिए.
चार भाज्य 4 बार 3 बार है 2 बार 1 24 देने के लिए.
और यही नियम लागू होता है किसी भी सकारात्मक पूर्णांक के लिए.
>> तो कैसे हम एक पुनरावर्ती लिख सकते हैं भाज्य की गणना करता है कि समारोह
एक नंबर की?
खैर, हम दोनों की पहचान करने की आवश्यकता होगी आधार के मामले और पुनरावर्ती कॉल.
पुनरावर्ती कॉल में ही होगा आधार के अलावा सभी मामलों के लिए
मामला है, जो हम करना होगा कि इसका मतलब हमें देना होगा कि एक पैटर्न पता हमारे
वांछित परिणाम.
>> इस उदाहरण के लिए, कैसे 5 भाज्य देखना 1 से 2 से 3 से 4 गुणा शामिल
और वह बहुत ही गुणन , यहां पाया जाता है
4 भाज्य की परिभाषा.
इसलिए हम 5 भाज्य है कि देखने सिर्फ 5 गुना 4 भाज्य.
अब इस पैटर्न को लागू करता है 4 के रूप में अच्छी तरह से भाज्य?
हां.
हम 4 भाज्य होता है कि देखते हैं गुणा 3 गुना 2 गुना 1,
3 भाज्य रूप में बहुत ही परिभाषा.
तो 4 भाज्य 4 गुना 3 के बराबर है भाज्य, और इतने पर और आगे हमारे
पैटर्न 1 भाज्य, जब तक चिपक जाती है जो परिभाषा से 1 के बराबर है.
>> कोई अन्य सकारात्मक नहीं है पूर्णांकों छोड़ दिया.
इसलिए हम के लिए पैटर्न है हमारे पुनरावर्ती कॉल.
n भाज्य एन बार करने के लिए बराबर है n के भाज्य शून्य से 1.
और अपने आधार का मामला?
वह सिर्फ हमारी परिभाषा हो जाएगा 1 भाज्य की.
>> तो अब हम लेखन के लिए पर स्थानांतरित कर सकते हैं समारोह के लिए कोड.
बेस मामले के लिए, हम होगा हालत n के बराबर होती है 1, के बराबर होती है, जहां
हम 1 वापस कर देंगे.
फिर पुनरावर्ती कॉल पर चलती है, हम एन बार वापस कर देंगे
n के भाज्य शून्य से 1.
>> अब देखते हैं कि यह हमारे परीक्षण करते हैं.
के भाज्य 4 कोशिश करते हैं.
हमारे समारोह प्रति यह बराबर है 4 बार भाज्य के लिए (3).
भाज्य (3) के बराबर है 3 बार भाज्य (2).
भाज्य (2) 2 बार के बराबर है भाज्य (1), जो 1 देता है.
भाज्य (2) अब 2 बार 1, 2 देता है.
भाज्य (3) अब लौट सकते हैं 3 गुना 2, 6.
और अंत में, भाज्य (4) 4 गुना 6, 24 देता है.
>> आप किसी भी कठिनाई का सामना कर रहे हैं पुनरावर्ती कॉल के साथ, कि नाटक
समारोह में पहले से ही काम करता है.
क्या मैं इस से क्या मतलब है आप चाहिए कि वापस जाने के लिए अपने पुनरावर्ती कॉल भरोसा
सही मूल्यों.
उदाहरण के लिए, अगर मुझे पता है कि भाज्य (5) 5 गुना के बराबर होती है
भाज्य (4), मैं उस पर भरोसा करने के लिए जा रहा हूँ भाज्य (4) मुझे 24 दे देंगे.
आप अगर एक चर के रूप में सोचो करेंगे, अगर आप पहले से ही परिभाषित के रूप में अगर
भाज्य (4).
इसलिए किसी भी भाज्य के लिए (एन), यह है n के उत्पाद और
पिछले भाज्य.
और यह पिछले भाज्य फोन करके प्राप्त किया जाता है
n के भाज्य शून्य से 1.
>> आप लागू कर सकते हैं, तो अब देखते हैं, एक पुनरावर्ती अपने आप कार्य करते हैं.
अपने टर्मिनल अप लोड, या run.cs50.net, और एक समारोह योग लिखना
कि एक पूर्णांक लेता है और रिटर्न सभी लगातार सकारात्मक का योग
n से 1 को पूर्णांकों.
मैं कुछ की रकम बाहर लिखा है आप मदद करने के लिए मानों हमारे.
सबसे पहले, यह पता लगाने बेस मामले हालत.
फिर, राशि पर देखने के लिए (5).
आप शब्दों में व्यक्त कर सकते हैं एक और राशि की?
अब, क्या योग के बारे में (4)?
आप कैसे योग व्यक्त कर सकते हैं (4) एक और राशि के संदर्भ में?
>> आप योग एक बार (5) और राशि (4) अन्य रकम के संदर्भ में व्यक्त की, देखें
आप एक पहचान कर सकते हैं राशि (एन) के लिए पैटर्न.
यदि नहीं, तो कुछ दूसरे नंबर की कोशिश और उनकी रकम में व्यक्त
एक और संख्या के लिहाज से.
असतत के लिए पैटर्न की पहचान करके संख्या, आप अपने रास्ते पर अच्छी तरह से कर रहे हैं
किसी भी n के लिए पैटर्न की पहचान.
>> Recursion एक बहुत शक्तिशाली उपकरण है, इसलिए निश्चित रूप से यह करने के लिए सीमित नहीं है
गणितीय कार्य करता है.
Recursion बहुत प्रभावी ढंग से इस्तेमाल किया जा सकता है उदाहरण के लिए पेड़ों के साथ काम करते हैं.
एक के लिए पेड़ों पर कम बाहर की जाँच करें अधिक गहन समीक्षा, लेकिन अब के लिए
में, कि द्विआधारी खोज पेड़ याद विशेष रूप से, प्रत्येक, नोड्स के बने होते हैं
एक मूल्य और दो नोड संकेत के साथ.
आमतौर पर, यह द्वारा प्रतिनिधित्व किया है एक लाइन इशारा होने के माता पिता के नोड
बाईं बच्चे के नोड और एक को सही बच्चा नोड के लिए.
एक द्विआधारी खोज की संरचना पेड़ अच्छी तरह से बख्शी
एक पुनरावर्ती खोज करने के लिए.
पुनरावर्ती कॉल या तो गुजरता बाईं या दाईं नोड, लेकिन अधिक
पेड़ संक्षेप में इस बात का.
>> आप पर कोई कार्रवाई करने के लिए कहना चाहता हूँ एक द्विआधारी पेड़ में हर एक नोड.
तुम उस के बारे में जाना हो सकता है?
ठीक है, तुम एक पुनरावर्ती लिख सकता है कार्रवाई करता है कि समारोह
माता पिता के नोड पर और एक पुनरावर्ती बनाता है एक ही समारोह के लिए कॉल,
बाएँ में गुजर रहा है और सही बच्चे नोड्स.
उदाहरण के लिए, इस समारोह, Foo, कि एक भी नोड के मूल्य और परिवर्तन
1 करने के लिए अपने बच्चों के सभी.
एक अशक्त नोड कारणों के आधार मामले समारोह का संकेत है, वापस जाने के लिए
किसी भी नोड्स वहाँ नहीं कर रहे हैं कि उप पेड़ में छोड़ दिया.
>> चलो यह माध्यम से चलते हैं.
पहले माता - पिता 13 है.
हम 1 का मूल्य परिवर्तन, और फिर कॉल हमारे बाईं तरफ के समारोह के रूप में अच्छी तरह से
अधिकार के रूप में.
समारोह foo बाईं तरफ कहा जाता है प्रथम उप पेड़, इसलिए छोड़ दिया नोड
1 और foo को फिर नियत किया जाएगा कि नोड के बच्चों पर कहा जा,
पहले छोड़ दिया और फिर सही, और इतने पर और बहुत आगे है.
और शाखाओं की जरूरत नहीं है कि उन्हें बताना किसी भी अधिक बच्चों को तो एक ही प्रक्रिया
सही बच्चों के लिए जारी रहेगा पूरे पेड़ नोड्स रहे हैं जब तक
1 को reassigned.
>> आप देख सकते हैं, आप ही सीमित नहीं हैं सिर्फ एक पुनरावर्ती कॉल.
काम मिल जाएगा बस के रूप में कई.
तुम एक पेड़ था क्या अगर जहां प्रत्येक नोड तीन बच्चों की थी,
वाम, मध्य, और सही?
कैसे आप foo संपादित होगा?
खैर, सरल.
बस एक पुनरावर्ती कॉल जोड़ने और मध्य नोड सूचक में गुजरती हैं.
>> Recursion बहुत शक्तिशाली है और नहीं करने के लिए है सुरुचिपूर्ण उल्लेख है, लेकिन यह एक हो सकता है
पहली बार में कठिन अवधारणा है, तो हो सकता है रोगी और अपना समय ले लो.
आधार के मामले के साथ शुरू करो.
यह आमतौर पर पहचान करने के लिए सबसे आसान है, और तब आप काम कर सकते हैं
पीछे की ओर वहाँ से.
आप तक पहुँचने की जरूरत है आपके बेस मामला है, इसलिए कि हो सकता है
आपको कुछ संकेत दे.
में एक विशिष्ट मामले को व्यक्त करने का प्रयास करें अन्य मामलों के संदर्भ, या उप सेट में.
>> इस छोटे से देखने के लिए धन्यवाद.
बहुत कम से कम, अब आप कर सकते हैं इस तरह से मजाक समझते हैं.
मेरा नाम Zamyla है, और इस CS50 है.
>> हाय, इस समारोह लो, एक लेता है कि शून्य समारोह
एक पूर्णांक, एन, निवेश के रूप में.
आधार के मामले पहले आता है.
एन 0 से कम, प्रिंट है तो "अलविदा" और बदले.