[موسیقی] 

داگ لوید: شما احتمالا فکر می کنم که کد استفاده می شود فقط برای به انجام رساندن یک کار است. شما آن را بنویسید. آن چیزی. که تقریبا آن را. 

شما آن را کامپایل کنید. شما برنامه را اجرا کنید. شما خوب به آن بروید. 

اما باور کنید یا نه، اگر شما برای مدت زمان طولانی کد، شما در واقع ممکن برای دیدن کد عنوان چیزی است که زیبا. این یک مشکل را حل میکند در یک راه بسیار جالب، و یا فقط چیزی واقعا وجود دارد شسته و رفته در مورد راه به نظر می رسد. شما ممکن است خنده در من، اما این درست است. و بازگشت یک راه است به نوعی از این ایده از زیبا، ظریف، به دنبال کد. این مشکلات را حل میکند در راه است که جالب توجه است، آسان به تجسم هستند، و شگفت آور کوتاه است. 

آثار راه بازگشت است، یک تابع بازگشتی به عنوان یک تابع است که خواستار تعریف خود را به عنوان بخشی از اجرای آن است. که ممکن است به نظر می رسد کمی عجیب و غریب، و ما کمی را ببینید در مورد چگونگی این کار می کند در یک لحظه. اما باز هم، این روالهای بازگشتی هستند رفتن به خیلی ظریف چون آنها در حال رفتن برای حل این مشکل بدون داشتن تمام این توابع دیگر و یا این حلقه ها طولانی است. شما خواهید دید که این بازگشتی روش در حال رفتن به نگاه خیلی کوتاه است. و آنها واقعا در حال رفتن به کد خود را نگاه بسیاری زیبا تر است. 

من یک مثال بزنم این را ببینید که چگونه یک روش بازگشتی ممکن است تعریف شود. بنابراین اگر شما با این آشنا هستید از کلاس ریاضی سال ها پیش، وجود دارد چیزی به نام تابع فاکتوریل، که معمولا اشاره به یک علامت تعجب، که بیش از تمام اعداد صحیح مثبت تعریف شده است. و راهی که N فاکتوریل محاسبه شده است است همه شما را چند برابر اعداد کمتر از و یا برابر با N together-- تمام اعداد صحیح کمتر از و یا به n هم برابر است. 

بنابراین 5 فاکتوریل 5 بار است 4 بار 3 بار 2 بار 1. و 4 فاکتوریل 4 برابر است 3 بار 2 بار 1 و غیره. شما ایده را دریافت. 

به عنوان برنامه نویس، ما نمی استفاده از N، علامت تعجب. بنابراین ما فاکتوریل تعریف تابع به عنوان واقعیت N. و ما فاکتوریل به ایجاد استفاده یک راه حل بازگشتی برای یک مشکل. و من فکر می کنم شما ممکن است پیدا که مقدار زیادی است بیشتر بصری جذاب تر از تکرار شونده نسخه ای از این که ما همچنین می خواهیم نگاه در یک لحظه. 

بنابراین در اینجا یک زن و شوهر از جناس 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، و غیره؟ در واقع، فاکتوریل از هر تعداد فقط می توانید اگر ما بیان نوع این انجام برای همیشه. ما به نوعی می تواند تعمیم مشکل فاکتوریل آن را به عنوان N برابر فاکتوریل n منهای 1. را n بار محصول را تمام اعداد کمتر از من. 

این ایده، این تعمیم این مشکل، ما اجازه می دهد به صورت بازگشتی تعریف تابع فاکتوریل. هنگامی که شما یک تابع را تعریف به صورت بازگشتی، وجود دارد دو چیز است که نیاز به یک بخشی از آن را. شما نیاز به چیزی به نام مورد پایه، که، هنگامی که شما آن را آغاز کند، می روند بازگشتی را متوقف کند. 

در غیر این صورت، یک تابع است که خواستار itself-- به عنوان شما ممکن imagine-- می تواند بنویس. تابع فراخوانی تابع خواستار تماس تابع تابع تابع فراخوانی می کند. اگر شما یک راه ندارد برای متوقف کردن آن، برنامه های خود را خواهد شد به طور موثر گیر در یک حلقه بی نهایت. آن را در نهایت سقوط خواهد کرد، به دلیل آن را از حافظه اجرا. اما کنار نقطه است. 

ما نیاز به برخی از راه های دیگر برای متوقف کردن همه چیز علاوه بر توفنده برنامه های ما، چون یک برنامه که سقوط است احتمالا زیبا نیست و یا ظریف است. و بنابراین ما این مورد پایه است. این یک راه حل ساده است به یک مشکل متوقف می شود که روند بازگشتی از وقوع. به طوری که یک بخشی از تابع بازگشتی. 

در بخش دوم، صورت بازگشتی است. و این است که در آن بازگشت در واقع اتفاق می افتد. این جایی است که تابع خود تماس بگیرید. 

آن را به خود دقیقا در پاسخ نیست به همان شیوه آن نامیده می شد. آن خواهید بود یک تغییر جزئی که باعث می شود مشکل آن تلاش برای حل یک کمی ریزه کوچکتر است. اما به طور کلی می گذرد جفتک انداختن حل بخش عمده ای از راه حل به تماس های مختلف پایین خط. 

کدام یک از این به نظر می رسد مانند مورد پایه در اینجا؟ کدام یک از این نظر می رسد مانند ساده ترین راه حل برای یک مشکل؟ ما یک دسته از فاکتوریل، و ما می تواند ادامه رفتن شماها 6، 7، 8، 9، 10، و غیره. 

اما یکی از این به نظر می رسد مثل یک مورد خوب به مورد پایه. این یک راه حل بسیار ساده است. ما لازم نیست که به انجام هر کاری خاص است. 

فاکتوریل 1 فقط 1. ما لازم نیست که برای انجام هر گونه ضرب در همه. به نظر می رسد اگر ما قصد داریم را امتحان کنید و حل این مشکل، و ما باید برای جلوگیری از بازگشت جایی، ما احتمالا می خواهید برای جلوگیری آن زمانی که ما به 1 است. ما نمی خواهیم به قبل از آن را متوقف کند. 

بنابراین اگر ما در حال تعریف تابع فاکتوریل ما، در اینجا یک اسکلت برای این ما چگونه ممکن است انجام این کار. ما نیاز به برق وصل در آن دو چیز در مورد پایه و صورت بازگشتی. مورد پایه چیست؟ اگر n برابر با 1 است، بازگشت 1-- که یک مشکل واقعا ساده را حل کند. 

فاکتوریل 1 1 است. آن را نمی 1 بار هر چیزی است. این فقط 1. این یک واقعیت بسیار آسان است. و به این ترتیب است که می تواند مورد پایگاه ما. اگر ما به این گذشت 1 تابع، ما فقط بازگشت 1. 

بازگشتی چیست مورد احتمالا شبیه؟ برای هر عدد دیگر علاوه بر 1، چه الگوی نیست. خب، اگر ما در حال گرفتن فاکتوریل n، آن را n بار فاکتوریل n منهای 1. 

اگر ما در حال گرفتن فاکتوریل 3، آن را 3 بار فاکتوریل 3 منهای 1، و یا 2. و بنابراین اگر ما نیست به دنبال در 1، در غیر این صورت بازگشت N برابر فاکتوریل n منهای 1. این بسیار سر راست است. 

و به خاطر داشتن کمی تمیز کننده و کد های ظریف تر، می دانم که اگر ما حلقه تک خط و یا تک خط شاخه شرطی، ما می توانیم از همه از شر آکولاد در اطراف آنها. بنابراین ما می توانیم به این تحکیم. این دقیقا همان قابلیت به عنوان این. 

من فقط در نظر گرفتن دور در اشکال مختلف طبی، چرا که تنها یک خط وجود دارد در داخل از آن شاخه شرطی. بنابراین این رفتار یکسان. اگر n برابر با 1 است، بازگشت 1. در غیر این صورت بار N بازگشت فاکتوریل n منهای 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. و دوباره، ما یک ویدئو در پاسخ پشته که در آن نشان داده شده است کمی بیش از آنچه که من در حال حاضر گفت. اما این آن است. این به تنهایی است راه حلی برای محاسبه فاکتوریل یک عدد است. 

تنها چهار خط کد است. این خیلی جالبه، درست است؟ این نوع از سکسی است. 

بنابراین به طور کلی، اما نه همیشه، یک تابع بازگشتی می توانید یک حلقه در یک جایگزین تابع غیر بازگشتی. بنابراین در اینجا، در کنار هم، است که تکرار شونده نسخه از تابع فاکتوریل. هر دو از این محاسبه دقیقا همان چیزی که. 

آنها هر دو محاسبه فاکتوریل n. نسخه در سمت چپ با استفاده از بازگشت به انجام آن. نسخه در سمت راست با استفاده از تکرار به انجام آن. 

و توجه ما باید به اعلام یک متغیر یک محصول عدد صحیح است. و سپس ما حلقه. تا زمانی که n بزرگتر از 0 ما است، حفظ ضرب که محصول توسط n طرح ساده N تا ما محاسبه محصول می باشد. بنابراین این دو تابع، دوباره، دقیقا همان چیزی است. اما آنها آن را در نمی دقیقا به همان شیوه. 

در حال حاضر، ممکن است به بیش از یک پایگاه مورد یا بیش از یک صورت بازگشتی، بسته در چه عملکرد خود را در تلاش است تا انجام دهد. شما لزوما فقط محدود به یک مورد پایه و یا یک بازگشتی تنها مورد. بنابراین به عنوان مثال از چیزی با موارد چند پایه ممکن است this-- اعداد فیبوناچی. 

شما ممکن است از یاد روزهای مدرسه ابتدایی که دنباله فیبوناچی تعریف شده است مانند this-- عنصر اول 0 است. عنصر دوم 1 است. هر دو از این فقط با تعریف هستند. 

پس از آن هر عنصر دیگر تعریف شده است به عنوان مجموع N منهای 1 و n منهای 2. بنابراین عنصر سوم می شود 0 به علاوه 1 است 1. و پس از آن عنصر چهارم می شود عنصر دوم، 1، به علاوه عنصر سوم، 1. و خواهد بود که 2. و غیره و غیره. 

بنابراین در این مورد، ما باید دو مورد پایه. اگر n برابر با 1 است، بازگشت 0. اگر n برابر با 2 است، بازگشت 1. در غیر این صورت، بازگشت فیبوناچی از n منهای 1 به علاوه فیبوناچی از n منهای 2. 

به طوری که موارد پایه های متعدد است. چه در مورد موارد بازگشتی چند؟ خب، چیزی وجود دارد به نام حدس کولاتز. من قصد ندارم برای گفتن، شما می دانید چه چیزی است، دلیل آن در واقع نهایی ما مشکل برای این فیلم خاص. و آن را از ورزش ما به کار بر روی با هم. 

بنابراین در اینجا چیزی است که حدس کولاتز is-- آن را به هر عدد صحیح مثبت اعمال می شود. و آن را حدس می زند که آن را همیشه ممکن است برای گرفتن تماس تا 1 اگر شما این مراحل را دنبال کنید. اگر n 1 است، را متوقف کند. ما به 1 کردم اگر n 1 است. 

در غیر این صورت، از طریق این فرایند دوباره در N تقسیم بر 2. و ببینید اگر شما می توانید به 1 است. در غیر این صورت، اگر n فرد باشد، از طریق رفتن این فرایند دوباره در 3N به علاوه 1، یا 3 بار N به علاوه 1. بنابراین در اینجا ما یک مورد تک پایه است. اگر n برابر با 1 است، را متوقف کند. ما هر گونه بازگشت تر در حال انجام نیست. 

اما ما باید دو مورد بازگشتی. اگر n زوج باشد، ما را بازگشتی مورد، خواستار N 2 تقسیم شده است. اگر n فرد باشد، ما انجام مختلف صورت بازگشتی در 3 بار N به علاوه 1. 

و به این ترتیب هدف برای این فیلم است را به یک دوم، مکث ویدیو، و سعی کنید و نوشتن این تابع بازگشتی کولاتز که در آن شما در یک مقدار N عبور، و آن را محاسبه چگونه بسیاری از مراحل آن طول می کشد تا به 1 اگر شما از N شروع و شما آن مراحل پیگیری کنید. اگر n 1 است، آن را 0 مرحله طول می کشد. در غیر این صورت، آن را به یک گام به علاوه با این حال بسیاری از مراحل آن در هر دو N طول می کشد تقسیم بر 2 اگر n زوج باشد، و یا 3N به علاوه 1 اگر n فرد باشد. 

در حال حاضر، من قرار داده ام بر روی صفحه نمایش در اینجا چند چیز آزمون را برای شما، یک زن و شوهر از موارد آزمون برای شما، برای دیدن چه این اعداد مختلف کولاتز هستند، و همچنین یک تصویر از اقداماتی که نیاز به از طریق بنابراین شما می توانید رفته مرتب سازی بر اساس این فرآیند در عمل ببینید. بنابراین اگر N برابر است 1، کولاتز از n 0 است. شما لازم نیست که به انجام هر چیزی را به عقب بر گردیم به 1. شما در حال حاضر وجود دارد. 

اگر n 2، طول می کشد یک گام برای رسیدن به 1. شما با 2 شروع می شود. خب، 2 به 1 برابر نیست. طوری که آن را به یک قدم به علاوه با این حال بسیاری از مراحل آن طول می کشد در N 2 تقسیم شده است. 

2 تقسیم بر 2 1 است. بنابراین آن طول می کشد یک قدم به علاوه با این حال بسیاری از مراحل آن را برای 1 طول می کشد. 1 صفر مرحله طول می کشد. 

3، به عنوان شما می توانید ببینید، وجود دارد کاملا چند مراحل. شما از 3 است. و سپس شما را به رفتن 10، 5، 16، 8، 4، 2، 1. این هفت مرحله طول می کشد تا به 1. و به عنوان شما می توانید ببینید، آنجا یک زن و شوهر دیگر موارد آزمون در اینجا برای تست کردن برنامه خود را. پس دوباره، مکث ویدیو. و من پرش به حال چه روند واقعی است که در اینجا، چه این حدس است. 

ببینید اگر شما می توانید از شکل چگونه به تعریف کولاتز از n به طوری که آن را محاسبه چگونه بسیاری از مراحل آن طول می کشد برای رسیدن به 1. پس امیدوارم، به شما این ویدیو متوقف می و شما نه تنها انتظار برای من به شما پاسخ اینجا است. اما اگر شما هستند، خوب، اینجا به هر حال جواب این است. 

بنابراین در اینجا یک تعریف ممکن است از تابع کولاتز. پایگاه ما case-- اگر n برابر با 1، ما بازگشت 0. این کار هر گونه نیست مراحل دریافت برگشت به 1. 

در غیر این صورت، ما دو cases-- بازگشتی یکی برای اعداد زوج و یکی برای عجیب و غریب. راه من برای اعداد حتی تست برای بررسی اگر N مد 2 برابر با 0. این است که اساسا، دوباره، پرسیدن سوال، اگر شما به خاطر is-- چه MOD اگر من تقسیم N 2 هیچ باقی مانده وجود دارد؟ این امر می تواند حتی یک عدد است. 

و به همین ترتیب اگر n مد 2 برابر با 0 است تست این حتی یک عدد است. اگر چنین است، من می خواهم به بازگشت 1، دلیل این است که قطعا برداشتن یک قدم به علاوه کولاتز از هر چه تعداد نیمی از من است. در غیر این صورت، من می خواهم به بازگشت 1 به علاوه کولاتز 3 بار N به علاوه 1. که بود گام بازگشتی که ما می تواند به محاسبه Collatz-- تعداد مراحل طول می کشد تا تماس به 1 با توجه به تعداد. پس امیدوارم، این مثال کمی به شما از طعم و مزه از روش بازگشتی. امیدوارم، شما فکر می کنم کد است کوچک و زیبا در صورت اجرا بیشتر در زیبا، راه بازگشتی. اما حتی اگر نه، بازگشت است ابزار واقعا قدرتمند با این وجود. و پس از آن قطعا چیزی برای دریافت سر خود را در اطراف، چون شما قادر به ایجاد برنامه های بسیار سرد با استفاده از توابع بازگشتی که در غیر اینصورت پیچیده به ارسال شود اگر شما با استفاده از حلقه ها و تکرار. من داگ لوید هستم. این CS50 است.