[عزف الموسيقى] 

DOUG لويد: ربما كنت تعتقد أن ويستخدم رمز فقط لإنجاز المهمة. تكتب بها. وهو يفعل شيئا. هذا الى حد كبير ذلك. 

يمكنك ترجمة عليه. تشغيل البرنامج. كنت جيدة للذهاب. 

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

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

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

حتى 5 مضروب هو 5 مرات 4 مرات 3 مرات 2 مرات 1. و4 مضروب هو 4 مرات 3 مرات 2 مرات (1) وهلم جرا. تحصل على هذه الفكرة. 

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

حتى هنا بضع التورية facts-- intended-- حول factorial-- لل وظيفة عاملية. مضروب 1، كما قلت، هو 1. مضروب 2 هو 2 مرات 1. مضروب 3 هو 3 مرات 2 مرات 1، وهلم جرا. تحدثنا عن 4 و 5 بالفعل. 

ولكن بالنظر إلى هذا، أليس هذا صحيحا؟ لا مضروب 2 فقط 2 مرات مضروب 1؟ أعني، مضروب 1 هو 1. فلماذا لا نستطيع فقط أن أقول، منذ مضروب 2 هو 2 مرات 1، انها حقا فقط 2 مرات مضروب 1؟ 

ومن ثم توسيع هذه الفكرة، ليس مضروب 3 فقط 3 مرات مضروب 2؟ ومضروب 4 هو 4 مرات مضروب 3، وهلم جرا؟ في الواقع، مضروب أي عدد يمكن فقط يمكن التعبير عنها إذا كنا النوع من تنفيذ ذلك إلى الأبد. يمكننا نوع من التعميم مشكلة عاملية كما انها مرات ن مضروب ن ناقص 1. انها ن مرات نتاج جميع الأرقام أقل من لي. 

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

خلاف ذلك، وهي وظيفة أن يدعو itself-- كما قد imagine-- يمكن أن تستمر إلى الأبد. وظيفة باستدعاء الدالة يدعو المكالمات وظيفة وتدعو وظيفة وظيفة. إذا لم يكن لديك وسيلة لوقفه، البرنامج سوف يكون عالقا على نحو فعال في حلقة لا نهائية. أنه سوف تعطل في نهاية المطاف، لأنه سوف ينفد من الذاكرة. ولكن هذا خارج عن الموضوع. 

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

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

انها لن تسمي نفسها بالضبط وبنفس الطريقة كان يسمى. أنه سوف يكون اختلاف طفيف أن يجعل المشكلة انها محاولة حل أصغر قليلا تيني. ولكنه يمر عموما باك حل الجزء الأكبر من الحل لدعوة مختلف أسفل الخط. 

أي من هذه النظرات مثل حالة الأساس هنا؟ أي واحد من هذه تبدو مثل أبسط حل للمشكلة؟ لدينا مجموعة من factorials، ونحن يمكن أن يستمر الذهاب on-- 6، 7، 8، 9، 10، وهلم جرا. 

ولكن واحدة من هذه تبدو وكأنها حالة جيدة لتكون الحالة الأساسية. انها الحل بسيط جدا. ليس لدينا لفعل أي شيء خاص. 

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

حتى إذا نحن تعريف لدينا وظيفة عاملية، وهنا هيكل عظمي ل كيف يمكننا أن نفعل ذلك. نحن بحاجة إلى سد العجز في هذين things-- حالة القاعدة وحالة متكررة. ما هي الحالة الأساسية؟ إذا كان n يساوي 1، والعودة 1-- هذا مشكلة بسيطة حقا لحلها. 

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

ما هي العودية حالة ربما تبدو؟ لكل رقم آخر إلى جانب 1، ما هو نمط؟ حسنا، إذا كنا تتناولين مضروب ن، انها ن مرات مضروب ن ناقص 1. 

إذا نحن اتخاذ مضروب 3، انها 3 مرات مضروب 3 ناقص 1، أو 2. وحتى إذا نحن لسنا أبحث في 1، وإلا مرات العائد ن مضروب ن ناقص 1. انها واضحة جدا. 

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

أنا مجرد اخذ مجعد تستعد، لأنه لا يوجد خط واحد فقط داخل هذه الفروع المشروطة. لذلك فان هذه تتصرف مماثل. إذا كان n يساوي 1، والعودة 1. خلاف ذلك العودة مرة ن مضروب ن ناقص 1. لذلك نحن جعل المشكلة أصغر. إذا كان n يبدأ على النحو 5، ونحن في طريقنا ل العودة 5 مرات مضروب 4. وسنرى في دقيقة واحدة عندما نتحدث حول stack-- الدعوة في آخر الفيديو حيث نتحدث عن استدعاء stack-- سوف نتعلم لماذا تعمل بالضبط هذه العملية. 

ولكن في حين مضروب من 5 يقول العودة 5 مرات مضروب 4، و 4 وأريد أن أقول، حسنا، حسنا، وعودة 4 مرات مضروب 3. وكما ترون، نحن نوع من الاقتراب 1. نحن نقترب و أقرب إلى هذه الحالة قاعدة. 

وبمجرد أن تصل إلى الحالة الأساسية، كل الوظائف السابقة يكون الجواب أنهم كانوا يبحثون عنه. مضروب 2 كان يقول العودة 2 مرات مضروب 1. حسنا، مضروب 1 عوائد 1. وبالتالي فإن الدعوة إلى مضروب من 2 يمكن العودة 2 مرات 1، ويعطي أن يعود إلى مضروب 3، والتي ينتظر أن النتيجة. 

وبعد ذلك يمكن حساب في النتيجة، 3 مرات 2 هي 6، ويعيدها إلى مضروب 4. ومرة أخرى، لدينا الفيديو على مكدس الاستدعاءات حيث يتضح هذا قليلا أكثر من ما أقوله الآن. ولكن هذا هو عليه. هذا وحده هو الحل ل حساب مضروب العدد. 

انها فقط أربعة أسطر من التعليمات البرمجية. هذا رائع، أليس كذلك؟ انها نوع من مثير. 

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

كلاهما حساب مضروب ن. الإصدار على اليسار يستخدم العودية للقيام بذلك. الإصدار الموجود على اليمين يستخدم التكرار للقيام بذلك. 

والإشعار، علينا أن نعلن متغير منتج صحيح. وبعد ذلك حلقة. طالما ن أكبر من 0، ونحن الحفاظ على ضرب هذا المنتج من قبل ن وdecrementing ن حتى نحسب المنتج. لذا هاتين الوظيفتين، مرة أخرى، تفعل بالضبط نفس الشيء. لكنها لا تفعل ذلك في بالضبط بنفس الطريقة. 

الآن، فمن الممكن ل لدينا قاعدة أكثر من حالة أو أكثر من واحد حالة متكررة، اعتمادا على ما وظيفة الخاص بك هو يحاول القيام به. أنت ليست بالضرورة تقتصر فقط على حالة قاعدة واحدة أو متكررة واحدة حالة. لذلك مثالا على شيء مع حالات قاعدة متعددة قد يكون this-- لل فيبوناتشي تسلسل الرقم. 

ولعلكم تذكرون من أيام المدرسة الابتدائية ان متتالية فيبوناتشي يعرف مثل this-- العنصر الأول هو 0. العنصر الثاني هو 1. كل من هؤلاء هم فقط من حيث التعريف. 

ثم يتم تعريف كل عنصر آخر كمجموع ن ​​ناقص 1 و ن ناقص 2. وبالتالي فإن العنصر الثالث سيكون 0 زائد 1 هو 1. ثم العنصر الرابع سيكون العنصر الثاني، 1، بالإضافة إلى العنصر الثالث، 1. والتي من شأنها أن تكون 2. وهلم جرا وهلم جرا. 

حتى في هذه الحالة، لدينا حالتين القاعدة. إذا كان n يساوي 1، والعودة 0. إذا كان n يساوي 2، والعودة 1. خلاف ذلك، والعودة فيبوناتشي ن ناقص 1 بالإضافة إلى فيبوناتشي ن ناقص 2. 

ذلك أن حالات قاعدة متعددة. ماذا عن حالات متكررة متعددة؟ حسنا، هناك شيء دعا التخمين Collatz. أنا لا أريد أن أقول، أنت تعرف ما هي، لأنه في الواقع هدفنا النهائي المشكلة لهذا الفيديو خاص. وانها ممارستنا للعمل على معا. 

حتى هنا ما حدسية كولاتز is-- الأمر ينطبق على كل عدد صحيح موجب. ويخمن أنه من الممكن دائما أن نعود ل1 إذا كنت اتبع الخطوات التالية. إذا كان n هو 1، ووقف. لقد حصلت على العودة إلى 1 إذا كان n هو 1. 

خلاف ذلك، انتقل من خلال هذا العملية مرة أخرى على ن مقسوما على 2. ومعرفة ما إذا كان يمكن أن نعود إلى 1. خلاف ذلك، إذا كان n هو الغريب، من خلال الذهاب هذه العملية مرة أخرى على 3N زائد 1، أو 3 مرات ن زائد 1. حتى هنا لدينا حالة قاعدة واحدة. إذا كان n يساوي 1، ووقف. نحن لا نفعل أي مزيد من العودية. 

ولكن لدينا حالتين متكررة. إذا كان n هو حتى، ونحن نفعل العودية واحد حالة، الاتصال ن مقسوما على 2. إذا كان n هو الغريب، ونحن نفعل مختلفة حالة متكررة على 3 مرات ن زائد 1. 

وبالتالي فإن الهدف لهذا الفيديو هو لتأخذ ثانية، وقفة الفيديو، ومحاولة لكتابة هذا وظيفة العودية Collatz حيث يمكنك تمرير في قيمة ن، و يحسب كم عدد الخطوات التي يلزم للحصول على 1 إذا كنت تبدأ من ن وعليك اتباع تلك الخطوات حتى أعلاه. إذا كان n هو 1، فإنه يأخذ 0 الخطوات. خلاف ذلك، فإنه سيكون ل اتخاذ خطوة واحدة زائد ولكن العديد من الخطوات التي تتخذها على أي ن مقسوما على 2 إذا كان n حتى، أو 3N زائد 1 إذا كان n هو الغريب. 

الآن، لقد وضعت على الشاشة هنا بضعة أشياء الاختبار بالنسبة لك، بضع حالات الاختبارات بالنسبة لك، لنرى ما هي هذه الأرقام Collatz المختلفة، وأيضا التوضيح من الخطوات التي تحتاج إلى مرت حتى تتمكن من نوع من رؤية هذه العملية في العمل. حتى إذا كان n يساوي 1، Collatz ن هو 0. لم يكن لديك للقيام أي شيء للحصول على العودة إلى 1. كنت بالفعل هناك. 

إذا كان n هو 2، فإنه يأخذ خطوة واحدة للوصول إلى 1. عليك أن تبدأ مع 2. حسنا، 2 لا يساوي 1. لذلك سيكون خطوة واحدة بالإضافة إلى ذلك لكن العديد من الخطوات يأخذ على تقسيم ن ب 2. 

2 مقسومة على 2 هو 1. لذلك يأخذ خطوة واحدة زائد ولكن العديد من الخطوات التي تتخذها ل1. 1 يأخذ الصفر الخطوات. 

ل3، كما ترون، هناك تماما على بعد خطوات قليلة المعنية. تذهب من 3. ثم تذهب إلى 10، 5، 16، 8، 4، 2، 1. يستغرق سبع خطوات للحصول على العودة إلى 1. وكما ترون، هناك زوجين حالات الاختبار غيرها من هنا لاختبار البرنامج. ذلك مرة أخرى، وقفة الفيديو. وسأذهب الآن إلى القفز مرة أخرى ما هي العملية الفعلية هنا، ما هو هذا التخمين. 

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

حتى هنا تعريف ممكن وظيفة Collatz. قاعدتنا case-- إذا كان n هو يساوي 1، نعود 0. لأنها لا تأخذ أي خطوات للحصول على العودة إلى 1. 

على خلاف ذلك، لدينا اثنين cases-- العودية واحد للأرقام حتى واحد لالغريب. الطريقة يمكنني اختبار للأرقام الزوجية هو للتحقق مما إذا ن وزارة الدفاع 2 يساوي 0. وهذا هو الأساس، ومرة ​​أخرى، طرح السؤال، اذا كنت أذكر is-- ما إذا كنت زارة الدفاع الفجوة ن بنسبة 2 ليس هناك ما تبقى؟ من شأنه أن يكون عدد زوجي. 

وحتى إذا كان n وزارة الدفاع 2 يساوي 0 غير الاختبار هو هذا العدد حتى. إذا كان الأمر كذلك، أريد أن أعود 1، لأن هذا هو بالتأكيد اتخاذ خطوة واحدة بالإضافة إلى Collatz من أيا كان عدد هو نصف مني. خلاف ذلك، أريد أن أعود 1 بالإضافة إلى Collatz من 3 مرات ن زائد 1. كان ذلك الآخر الخطوة العودية أننا قد يستغرق لحساب Collatz-- عدد من الخطوات ما يلزم للحصول الظهر ل1 يعطى الرقم. لذلك نأمل، هذا المثال أعطاك قليلا من طعم إجراءات متكررة. نأمل، كنت أعتقد code عبارة عن قليلا أكثر جمالا إذا ما نفذت في، طريقة عودي أنيقة. ولكن حتى لو لم يكن كذلك، العودية هي أداة قوية حقا مع ذلك. وذلك بالتأكيد شيء للحصول على رأسك حولها، لأنك سوف تكون قادرة على خلق برامج باردة جدا باستخدام العودية قد يكون الأمر خلاف ذلك معقدة للكتابة إذا كنت تستخدم الحلقات والتكرار. أنا دوغ ويد. هذا هو CS50.