[संगीत बजाना] 

डौग लॉयड: तुम्हें शायद लगता है कि कोड सिर्फ एक कार्य को पूरा करने के लिए प्रयोग किया जाता है। आप इसे लिखने के बाहर। यह कुछ भी करता है। कि यह बहुत सुंदर है। 

आप यह संकलन। आप इस कार्यक्रम चलाते हैं। तुम जाने के लिए अच्छे हैं। 

लेकिन यह विश्वास है या नहीं, यदि आप एक लंबे समय के लिए कोड आप वास्तव में देखने के लिए आ सकता है सुंदर है कि कुछ के रूप कोड। यह एक समस्या में हल करती है एक बहुत ही दिलचस्प तरीके से, या वास्तव में अभी कुछ भी नहीं है यह लगता है जिस तरह के बारे में साफ। आप हँस किया जा सकता है मुझ पर है, लेकिन यह सच है। और प्रत्यावर्तन एक ही रास्ता है एक तरह से इस विचार को पाने के लिए का सुंदर, सुंदर दिखने कोड। यह तरीकों में समस्याओं को हल करती है कि , कल्पना करने के लिए आसान है, दिलचस्प हैं और आश्चर्यजनक रूप से कम है। 

रास्ते प्रत्यावर्तन काम करता है एक पुनरावर्ती समारोह है, कहता है कि एक समारोह के रूप में परिभाषित किया गया है खुद को इसके क्रियान्वयन के हिस्से के रूप में। यही कारण है, थोड़ा अजीब लग सकता है और हम एक छोटा सा देखता हूँ इस एक पल में कैसे काम करता है के बारे में। लेकिन फिर, इन पुनरावर्ती प्रक्रियाओं हैं इतनी खूबसूरत होने जा रहा वे जा रहे हैं क्योंकि बिना इस समस्या को हल करने के लिए इन सभी अन्य कार्यों होने या इन लंबे छोरों। आप इन पुनरावर्ती देखेंगे कि प्रक्रियाओं इतनी कम देखने के लिए जा रहे हैं। और वे वास्तव में बनाने जा रहे हैं अपने कोड एक बहुत अधिक सुंदर लग रही हो। 

मैं आपको एक उदाहरण देता हूँ इस के देखने के लिए कैसे एक पुनरावर्ती प्रक्रिया में परिभाषित किया जा सकता है। आप इस बात से परिचित हैं, तो अगर कई साल पहले गणित वर्ग से वहाँ कुछ कहा जाता है जो आमतौर पर भाज्य समारोह, एक विस्मयादिबोधक बिंदु के रूप में चिह्नित है, जो सभी सकारात्मक integers से अधिक परिभाषित किया गया है। और वैसे भी कि n भाज्य गणना की जाती है आप सभी का गुणा किया जाता है की तुलना में संख्या कम या बराबर एन together-- को सभी पूर्णांकों से कम या एक साथ n करने के लिए बराबर है। 

तो 5 भाज्य 5 गुना है 4 गुना 3 गुना 2 बार 1। और 4 भाज्य 4 गुना है 3 गुना 2 बार 1 और इतने पर। तुम्हें नया तरीका मिल गया है। 

प्रोग्रामर के रूप में, हम नहीं करते एन, विस्मयादिबोधक बिंदु का उपयोग करें। इसलिए हम भाज्य परिभाषित करेंगे n के तथ्य के रूप में कार्य करते हैं। और हम बनाने के लिए भाज्य इस्तेमाल करेंगे एक समस्या के लिए एक पुनरावर्ती समाधान। और मैं तुम्हें मिल सकता है यह एक बहुत अधिक नेत्रहीन है कि चलने से अपील इस बात का संस्करण है, जो हम भी एक पल में पर एक नज़र ले जाऊँगा। 

तो यहाँ के एक जोड़े हैं facts-- श्लेष intended-- के बारे में factorial-- भाज्य समारोह। जैसा कि मैंने कहा एक के भाज्य, 1 है। 2 के भाज्य 2 बार 1 है। 3 से भाज्य 3 है 2 बार इतने पर बार 1, और। हम पहले से ही 4 और 5 के बारे में बात की थी। 

लेकिन इस पर विचार कर रही है, यह सच नहीं है? 2 के भाज्य नहीं है बस 2 बार 1 के भाज्य? मेरा मतलब है, एक के भाज्य 1 है। तो क्यों न हम सिर्फ इतना है कि यह नहीं कह सकते, 2 के भाज्य 2 बार 1 है के बाद से, यह वास्तव में सिर्फ 2 बार है 1 के भाज्य? 

और फिर, यह विचार है कि का विस्तार 3 से भाज्य नहीं है सिर्फ 3 बार 2 के भाज्य? और 4 के भाज्य 4 गुना है इतने पर 3, और के भाज्य? वास्तव में, भाज्य किसी भी नंबर की बस कर सकते हैं तरह अगर हम व्यक्त किया हमेशा के लिए इस बाहर ले। हम किस तरह का सामान्यीकरण कर सकते हैं भाज्य समस्या यह है के रूप में n बार n शून्य से 1 के भाज्य। इसके बारे में n बार उत्पाद है सभी नंबरों को मुझ से भी कम है। 

यह विचार है, इस समस्या का सामान्यीकरण, हमें बारी बारी से करने के लिए अनुमति देता है भाज्य समारोह को परिभाषित। आप एक समारोह को परिभाषित करते हैं बारी बारी से, वहाँ है इसे का एक हिस्सा होने की जरूरत है कि दो बातें। तुम कुछ कहा जाता है की जरूरत है आधार के मामले, जो है, आप इसे गति प्रदान करते हैं, पुनरावर्ती प्रक्रिया बंद हो जाएगा। 

अन्यथा, एक समारोह है कि कॉल itself-- आप imagine-- हो सकता है के रूप में हमेशा के लिए जा सकता है। समारोह समारोह कॉल समारोह कॉल समारोह समारोह कहता है। आप एक तरह से नहीं है, तो अपने कार्यक्रम इसे रोकने के लिए प्रभावी ढंग से अटक जाएगा एक अनंत लूप पर। यह अंत में दुर्घटना होगा यह स्मृति से बाहर चला जाएगा क्योंकि। लेकिन उस बिंदु के पास है। 

हम को रोकने के लिए कुछ अन्य तरीके से करने की जरूरत है हमारे दुर्घटनाग्रस्त कार्यक्रम के अलावा बातें, दुर्घटनाओं कि एक कार्यक्रम है क्योंकि शायद सुंदर या सुंदर नहीं। और इसलिए हम इस आधार के मामले कहते हैं। यह एक सरल उपाय है बंद हो जाता है, जो एक समस्या के लिए से होने वाली पुनरावर्ती प्रक्रिया। इसलिए इस बात का एक हिस्सा है एक पुनरावर्ती समारोह। 

दूसरे भाग पुनरावर्ती मामला है। और इस जहां प्रत्यावर्तन है वास्तव में जगह ले जाएगा। यह वह जगह है जहां समारोह में ही मुलाकात करेंगे। 

यह वास्तव में खुद के फोन नहीं होगा उसी तरह से यह कहा जाता था। यह एक मामूली बदलाव हो जाएगा यह बात है समस्या बनाता है एक नन्हा सा छोटी हल करने के लिए कोशिश कर रहा। लेकिन यह आम तौर पर हिरन गुजरता के समाधान के थोक सुलझाने रेखा के नीचे एक अलग कॉल करने के लिए। 

इन लग रहा है की कौन सा यहाँ आधार के मामले की तरह? जो की तरह इन लग रहा है की एक एक समस्या के लिए सबसे सरल हल क्या है? हम factorials का एक गुच्छा है, और हम जारी रख सकता है इतने पर on-- 6, 7, 8, 9, 10, और जा रहा है। 

लेकिन एक तरह इन लग रहा है की एक अच्छा मामले आधार के मामले होने के लिए। यह एक बहुत ही सरल उपाय है। हम विशेष कुछ भी करने की जरूरत नहीं है। 

1 के भाज्य सिर्फ एक है। हम कोई भी कार्य करने की जरूरत नहीं है गुणन सब पर। हम जा रहे हैं, तो ऐसा लगता है जैसे कोशिश करते हैं और इस समस्या को हल करने के लिए, और हम रोकने की जरूरत है कहीं प्रत्यावर्तन, हम शायद बंद करना चाहते हैं यह हम 1 करने के लिए मिलता है। हम उस से पहले बंद करने के लिए नहीं करना चाहती। 

हम परिभाषित कर रहे हैं तो अगर हमारे भाज्य समारोह, यहां एक कंकाल के लिए है हम ऐसा कैसे हो सकता है। हम उन दो बातें में प्लग की जरूरत है आधार के मामले और पुनरावर्ती मामला। आधार के मामले में क्या है? एन 1 के बराबर है, तो वापस कर 1-- है कि एक बहुत सरल समस्या को हल करने के लिए। 

1 के भाज्य 1 है। यह न एक बार कुछ भी नहीं है। यह सिर्फ एक है। यह एक बहुत ही आसान तथ्य है। और इतना है कि हमारे आधार मामला हो सकता है। हम इस में 1 पारित हो तो समारोह में, हम सिर्फ एक वापस कर देंगे। 

पुनरावर्ती क्या है मामला शायद की तरह लग रही हो? हर दूसरे नंबर के लिए 1 इसके अलावा, पैटर्न क्या है? खैर, हम ले जा रहे हैं n के भाज्य, यह n बार n के भाज्य शून्य से 1। 

हम 3 से भाज्य ले जा रहे हैं, यह 3 शून्य से 1 की 3 बार भाज्य है या 2। और हम नहीं कर रहे हैं यदि हां अन्यथा, 1 पर देख रहे हैं वापसी n बार n शून्य से 1 के भाज्य। यह बहुत स्पष्ट है। 

और थोड़ा होने के लिए क्लीनर और कोड अधिक सुंदर, पता है कि हम एकल लाइन छोरों है तो या एकल लाइन सशर्त शाखाओं, हम सभी से छुटकारा मिल सकता उन्हें चारों ओर सर्पाकार। इसलिए हम यह करने के लिए इस मजबूत कर सकते हैं। यह बिल्कुल वैसा ही है इस रूप में कार्यक्षमता। 

मैं सिर्फ घुंघराले दूर ले जा रहा हूँ केवल एक लाइन भी नहीं है, क्योंकि ब्रेसेस उन सशर्त शाखाओं के अंदर। इसलिए इन हूबहू व्यवहार करते हैं। एन 1 के बराबर है, तो एक वापसी। अन्यथा n बार लौटने n शून्य से 1 के भाज्य। इसलिए हम छोटी समस्या बना रहे हैं। N 5 के रूप में बाहर शुरू होता है, तो हम करने जा रहे हैं 4 से 5 बार भाज्य वापसी। और हम जब हम बात करते एक मिनट में देखेंगे एक अन्य वीडियो में कॉल stack-- के बारे में जहां हम के बारे में बात करते हैं हम सीखना होगा stack-- फोन वास्तव में इस प्रक्रिया काम करता है के बारे में क्यों। 

लेकिन 5 की, जबकि भाज्य का कहना है 5 बार भाज्य 4 की वापसी, और 4 खैर, ठीक है, कहने के लिए जा रहा है, वापसी 4 बार 3 के भाज्य। जैसा कि आप देख सकते हैं, हम कर रहे हैं एक तरह से एक के करीब पहुंच। हम करीब हो रही है और कि आधार के मामले के करीब। 

और हम आधार के मामले मारा एक बार, पिछले कार्यों के सभी वे देख रहे थे जवाब नहीं है। 2 के भाज्य वापसी कह रहा था 2 बार 1 के भाज्य। खैर, 1 रिटर्न 1 के भाज्य। भाज्य के लिए तो कॉल 2, 2 बार 1 लौट सकते हैं और के भाज्य के लिए है कि वापस दे कि परिणाम के लिए इंतजार कर रहा है, जो 3,। 

और फिर यह गणना कर सकते हैं इसका परिणाम, 3 बार 2, 6 और 4 के भाज्य के लिए वापस दे। और फिर, हम एक हैं कॉल स्टैक पर वीडियो यह एक छोटे से यह साफ है जहां मैं अभी क्या कह रहा हूँ से अधिक है। लेकिन यह बात है। यह अकेले का हल है एक नंबर के भाज्य की गणना। 

यह कोड के केवल चार लाइनें है। यह ठीक है, बहुत अच्छा है? यह सेक्सी की तरह है। 

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

वे दोनों n के भाज्य गणना। बाईं तरफ के संस्करण यह करने के लिए प्रत्यावर्तन का उपयोग करता है। सही संस्करण यह करने के लिए चलना उपयोग करता है। 

और नोटिस, हम घोषणा की है एक पूर्णांक उत्पाद एक चर। और फिर हम पाश। इतने लंबे समय n के रूप में हम, 0 से अधिक है n द्वारा कि उत्पाद गुणा रखना और जब तक एन decrementing हम उत्पाद की गणना। तो इन दो कार्यों, फिर से, वास्तव में ही बात करते हैं। लेकिन वे में यह मत करो ठीक उसी तरह। 

अब, यह संभव है एक से अधिक आधार है मामले या एक से अधिक पुनरावर्ती मामले, निर्भर करता है क्या अपने कार्य करने के लिए कोशिश कर रहा है। तुम जरूरी अभी तक सीमित नहीं हैं एक एकल आधार के मामले या एक भी पुनरावर्ती मामला। कुछ की तो एक उदाहरण कई आधार मामलों के साथ हो सकता है- फिबोनाची संख्या अनुक्रम। 

आप से याद कर सकते हैं प्राथमिक स्कूल के दिनों फिबोनाची अनुक्रम परिभाषित किया गया है कि है- जैसे पहला तत्व 0 है। दूसरा तत्व एक है। उन दोनों ने सिर्फ परिभाषा से कर रहे हैं। 

तो हर दूसरे तत्व परिभाषित किया गया है n शून्य से 1 और एन शून्य से 2 की राशि के रूप में। तीसरे तत्व तो 0 प्लस 1 1 होगा। और फिर चौथे तत्व दूसरा तत्व, 1 होगा, प्लस तीसरे तत्व, 1। और कहा कि 2 होगा। और आगे और आगे। 

तो इस मामले में, हम दो आधार मामलों है। एन 1 के बराबर है, तो 0 वापसी। 2 n के बराबर होता है, तो एक वापसी। अन्यथा, n के फिबोनाची लौटने शून्य से 1 प्लस n शून्य से 2 की फिबोनाची। 

तो यह है कि कई मामलों आधार है। क्या कई पुनरावर्ती मामलों के बारे में? खैर, कुछ भी नहीं है Collatz अनुमान बुलाया। मैं कहता हूँ, नहीं जा रहा हूँ आप जानते हैं यह क्या है, यह वास्तव में हमारे अंतिम है, क्योंकि इस विशेष वीडियो के लिए समस्या है। और यह हमारे व्यायाम है पर एक साथ काम करने के लिए। 

तो यहाँ है क्या Collatz अनुमान है- यह हर सकारात्मक पूर्णांक के लिए लागू होता है। और यह है कि यह अनुमान लगाया हमेशा संभव वापस पाने के लिए 1 करने के लिए आप इन कदमों का पालन करें। एन 1 है, तो बंद करो। : 1 है, तो हम एक करने के लिए वापस मिल गया है। 

अन्यथा, इस के माध्यम से जाना प्रक्रिया पर फिर से 2 n से विभाजित। आप 1 को वापस प्राप्त कर सकते हैं और देखते हैं। N विषम है यदि नहीं तो, के माध्यम से जाना फिर 3N प्लस 1 पर इस प्रक्रिया को, या 3 बार एन प्लस 1। तो यहाँ हम एक एकल आधार मामला है। एन 1 के बराबर है, तो बंद करो। हम किसी भी अधिक प्रत्यावर्तन नहीं कर रहे हैं। 

लेकिन हम दो पुनरावर्ती मामलों है। N भी है, तो हम एक पुनरावर्ती करना मामले, 2 n से विभाजित बुला रही है। N विषम है, तो हम एक अलग करना 3 बार n प्लस 1 पर पुनरावर्ती मामला। 

और हां इस वीडियो के लिए लक्ष्य है एक दूसरा ले वीडियो को थामने के लिए, और कोशिश करते हैं और यह लिखना पुनरावर्ती समारोह Collatz जहां आप एक मूल्य n में प्रवेश करते हैं और यह कितने कदम यह गणना आप एन से शुरू करता है, तो 1 को पाने के लिए ले जाता है और आप उन लोगों के ऊपर कदम का पालन करें। एन 1 है, तो यह 0 कदम उठा लेता है। अन्यथा, यह जा रहा है हालांकि एक कदम के साथ साथ ले लो यह या तो एन पर ले जाता है कई कदम 2 से विभाजित n भी है, या 3N प्लस 1 यदि एन अजीब है। 

अब, मैं यहाँ स्क्रीन पर डाल दिया है आप के लिए परीक्षण चीजों की एक जोड़ी, आप के लिए परीक्षण मामलों के एक जोड़े को देखने के लिए इन विभिन्न Collatz संख्या क्या कर रहे हैं, और यह भी एक उदाहरण कदम की है कि इसलिए आप कर सकते हैं के माध्यम से चले जाने की जरूरत है तरह की कार्रवाई में इस प्रक्रिया को देखते हैं। एन के बराबर है तो अगर 1, एन के Collatz 0 है। तुम सब करने की जरूरत नहीं है कुछ भी 1 को वापस पाने के लिए। आप पहले से ही वहाँ रहे हैं। 

2 n है, यह लेता है एक कदम और एक को पाने के लिए। तुम 2 के साथ शुरू करते हैं। खैर, 2 1 के बराबर नहीं है। तो यह एक कदम होने जा रहा है प्लस हालांकि कई कदम यह पर ले जाता है 2 n से विभाजित। 

2 से विभाजित 2 1 है। तो यह हालांकि एक कदम प्लस लेता है कई कदम यह 1 के लिए लेता है। 1 शून्य कदम उठा लेता है। 

आप देख सकते हैं 3 के लिए, वहाँ है काफी कुछ कदम शामिल किया गया। आप 3 से चले जाओ। और फिर आप के लिए जाना 10, 5, 16, 8, 4, 2, 1। यह एक करने के लिए वापस पाने के लिए सात कदम उठा लेता है। जैसा कि आप देख सकते हैं, वहाँ एक यहाँ कुछ अन्य मामलों का परीक्षण अपने कार्यक्रम के बाहर का परीक्षण करने के लिए। तो फिर, वीडियो थामने। और मैं अब वापस कूद जाऊँगा वास्तविक प्रक्रिया यहाँ क्या है, इस अनुमान है क्या। 

आप समझ सकते हैं देखें n के Collatz परिभाषित करने के लिए कैसे यह कितने की गणना करता है, ताकि यह 1 पर ले लेता कदम। तो उम्मीद है, आप वीडियो रोक दिया है और आप सिर्फ मेरे लिए इंतजार नहीं कर रहे यहाँ आप इस सवाल का जवाब देने के लिए। लेकिन आप कर रहे हैं, तो ठीक है, यहाँ का जवाब वैसे भी है। 

तो यहाँ एक संभव परिभाषा है Collatz समारोह का। N है, तो हमारा आधार case-- 1 के बराबर है, हम 0 वापसी। यह किसी भी नहीं ले करता है चरण 1 को वापस पाने के लिए। 

अन्यथा, हम दो पुनरावर्ती cases-- है यहां तक ​​कि संख्या के लिए एक और अजीब के लिए एक। मैं भी संख्या के लिए परीक्षण के रास्ते एन आधुनिक 2 0 के बराबर होती है, तो जाँच करने के लिए है। यह, फिर से, मूल रूप से है सवाल पूछ रही है, आप क्या आधुनिक है- याद करते हैं, तो मैं 2 से विभाजित n कोई शेष नहीं है? यही कारण है कि एक भी नंबर होगा। 

और इसलिए n आधुनिक 2 0 के बराबर होती है, तो परीक्षण इस एक भी नंबर है। यदि हां, तो मैं एक वापसी करना चाहते हैं, यह निश्चित रूप से है क्योंकि एक कदम प्लस के Collatz ले रही है जो भी नंबर मुझे का आधा है। अन्यथा, मैं एक वापसी करना चाहते हैं प्लस Collatz 3 बार एन प्लस 1। यही कारण है कि अन्य था पुनरावर्ती कदम है कि हम गणना करने के लिए ले सकता है चरणों की संख्या Collatz-- इसे वापस ले लेता है 1 करने के लिए एक नंबर दिया। तो उम्मीद है, इस उदाहरण आप एक छोटा सा दिया पुनरावर्ती प्रक्रियाओं की एक स्वाद की। उम्मीद है, आप कोड एक है लगता है छोटे से अधिक है, तो सुंदर कार्यान्वित एक सुंदर, पुनरावर्ती रास्ते में। भी नहीं लेकिन, अगर प्रत्यावर्तन है एक फिर भी बहुत शक्तिशाली उपकरण। और तो यह निश्चित रूप से कुछ है चारों ओर अपने सिर को पाने के लिए, आप पैदा करने में सक्षम हो जाएगा, क्योंकि प्रत्यावर्तन का उपयोग कर बहुत अच्छा कार्यक्रमों कि अन्यथा लिखने के लिए जटिल हो सकता है आप छोरों और चलना उपयोग कर रहे हैं। मैं डौग लॉयड हूँ। इस CS50 है।