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

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

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

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

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

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

دعونا نلقي نظرة مضروب العملية الأكثر شيوعا في حسابات الاحتمال. مضروب n هو نتاج كل عدد صحيح موجب أقل من ويساوي ن. خمسة مضروب حتى 5 مرات 4 مرات 3 مرات 2 مرات 1 إلى منح 120. أربعة مضروب هو 4 مرات 3 مرات 2 مرات 1 إلى إعطاء 24. وتنطبق نفس القاعدة إلى أي عدد صحيح موجب. 

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

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

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

وحتى الآن يمكننا أن ننتقل إلى الكتابة التعليمات البرمجية للدالة. للقضية الأساس، سيكون لدينا حالة ن يساوي يساوي 1، حيث وسوف نعود 1. ثم الانتقال الى الدعوة متكررة، وسوف نعود مرة ن مضروب ن ناقص 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). ذلك لأي مضروب (ن)، انها المنتج ن و مضروب السابقة. وهذا مضروب السابقة يتم الحصول عليها عن طريق الدعوة مضروب ن ناقص 1. 

الآن، نرى ما اذا كان يمكن تنفيذ تعمل عودي نفسك. تحميل ما يصل محطة الخاص بك، أو run.cs50.net، وكتابة دالة مبلغ التي تأخذ عددا صحيحا n و إرجاع مجموع كل إيجابية متتالية أعداد صحيحة من ن إلى 1. لقد كتبت من المبالغ من بعض القيم لمساعدتك لدينا. أولا، معرفة حالة الحالة الأساسية. ثم، أن ننظر في مجموع (5). يمكنك التعبير عن ذلك من حيث من مبلغ آخر؟ الآن، ماذا عن مبلغ (4)؟ كيف يمكنك التعبير عن مبلغ (4) من حيث مبلغ آخر؟ 

مرة واحدة لديك مبلغ (5) ومبلغ (4) وأعرب من حيث المبالغ الأخرى، انظر إذا كان يمكنك تحديد نمط لمبلغ (ن). إن لم يكن، في محاولة أعداد قليلة أخرى وأعرب عن المبالغ الخاصة بهم في حيث أعداد أخرى. عن طريق تحديد أنماط منفصلة الأرقام، كنت جيدا على طريقك ل تحديد نمط لأي ن. 

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

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

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

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

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

شكرا لمشاهدة هذا قصيرة. على أقل تقدير، والآن يمكنك فهم النكات مثل هذا. اسمي Zamyla، وهذا هو CS50. 

تأخذ هذه الوظيفة، مرحبا، و وظيفة الفراغ الذي يأخذ عدد صحيح، ن، كإدخال. الحالة الأساسية يأتي أولا. إذا كان n أقل من 0، الطباعة "وداعا" والعودة.