>> ZAMYLA: به منظور درک بازگشت، شما باید
اولین بازگشت را درک کنید.
پس از بازگشت در برنامه به معنای طراحی که شما خود ارجاعی
تعاریف.
ساختمان داده بازگشتی، به عنوان مثال، ساختمان های داده که
شامل خود را در تعاریف خود را.
اما امروز، ما قصد داریم به تمرکز در توابع بازگشتی.
>> به یاد بیاورید که توابع ورودی، استدلال، و بازگشت به ارزش به خود
خروجی ارائه شده توسط این دیاگرام در اینجا.
ما از جعبه به عنوان بدن از فکر می کنم تابع، شامل مجموعه ای از
دستورالعمل ها است که تفسیر ورودی و ارائه یک خروجی.
با توجه به بررسی دقیق تر در داخل بدن تابع می تواند تماس را نشان می دهد
توابع دیگر نیز هست.
از این تابع ساده، تولی، که طول می کشد یک رشته واحد به عنوان ورودی و
چگونه نامه های بسیاری از چاپ که رشته است.
strlen تابع، طول رشته، نامیده می شود، که خروجی است
مورد نیاز برای فراخوانی چون printf.
>> در حال حاضر، چه چیزی باعث می شود یک تابع بازگشتی ویژه ای است که آن را به خود فرا می خواند.
ما می توانیم این بازگشتی نشان دهنده تماس با این رنگ نارنجی فلش
حلقه برگشت به خود را.
اما دوباره اجرای خود را تنها را یکی دیگر از تماس بازگشتی، و
دیگر و دیگر.
اما توابع بازگشتی نمی توان بی نهایت.
آنها برای پایان دادن به نحوی، یا خود را برنامه برای همیشه اجرا خواهد شد.
>> بنابراین ما نیاز به پیدا کردن یک راه برای شکستن از تماس های بازگشتی.
به این مورد پایه.
هنگامی که شرایط مورد پایه داشته است تابع بدون گرداند
یکی دیگر از تماس بازگشتی.
نگاهی به این تابع، سلام، تابعی از درجه اعتبار ساقط است که یک نفر بین المللی به عنوان ورودی می باشد.
مورد پایه می آید برای اولین بار.
اگر نفر کمتر از صفر، خداحافظ چاپ و است بازگشت به تمام موارد دیگر،
تابع چاپ سلام و اجرا تماس بازگشتی.
تماس دیگر به سلام تابع با یک مقدار ورودی decremented.
>> در حال حاضر، حتی اگر ما چاپ سلام، تابع نمی خاتمه تا زمانی که ما
بازگشت نوع بازگشت آن، در این مورد از درجه اعتبار ساقط.
بنابراین برای هر نفر به غیر از مورد پایه، این تابع سلام باز خواهد گشت سلام
از n منهای 1.
از آنجا که این تابع از درجه اعتبار ساقط است هر چند، ما نه به صراحت در اینجا بازگشت تایپ کنید.
ما فقط اجرای تابع.
بنابراین خواستار سلام (3) خواهد شد و چاپ سلام اجرا سلام (2) است که اجرا سلام (1) یک
است که اجرا سلام (0)، که در آن شرایط مورد پایه داشته است.
پس سلام (0) چاپ خداحافظی و برمی گردد.
>> OK.
بنابراین در حال حاضر که ما درک اصول اولیه توابع بازگشتی، که آنها نیاز به
حداقل یک مورد پایه و همچنین به عنوان یک تماس بازگشتی، اجازه دهید تا به حرکت
به عنوان مثال معنی دار تر.
یکی می کند که نه تنها بازگشت از درجه اعتبار ساقط بدون توجه به آنچه.
>> اجازه دهید نگاهی به فاکتوریل عملیات اغلب در مورد استفاده
محاسبات احتمال.
n فاکتوریل n محصول هر است عدد صحیح مثبت کمتر از
و به 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.
>> هیچ مثبت وجود دارد اعداد صحیح باقی مانده است.
بنابراین ما باید الگوی برای تماس بازگشتی است.
N فاکتوریل به بار N برابر است با n فاکتوریل n منهای 1.
و مورد پایگاه ما؟
که فقط تعریف ما باشد از 1 فاکتوریل.
>> بنابراین در حال حاضر ما می توانیم به نوشتن حرکت کد برای تابع.
برای مورد پایه، ما باید شرایط N برابر است با برابر 1، که در آن
ما 1 را بازگشت.
سپس حرکت بر روی تماس بازگشتی، ما بار نفر را بازگشت
n فاکتوریل 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 و
فاکتوریل قبلی.
و این عاملی قبلی است با تماس دست آمده
n فاکتوریل n منهای 1.
>> در حال حاضر، اگر شما می توانید پیاده سازی یک بازگشتی خود را عمل می کنند.
بار کردن ترمینال خود را، و یا run.cs50.net، و ارسال مبلغ تابع
است که یک نفر صحیح و برمی گرداند مجموع همه متوالی مثبت
اعداد صحیح از N به 1.
من نوشته ام از این مبالغ به برخی از ارزش ها به شما کمک کند ما.
اول، شکل از شرایط مورد پایه.
سپس، در مجموع نگاه (5).
آیا می توانید آن را بیان در شرایط از مجموع دیگر؟
در حال حاضر، آنچه در مورد مبلغ (4)؟
چگونه می تواند به شما ابراز مجموع (4) از نظر جمع دیگر؟
>> هنگامی که شما جمع (5) و مجموع (4) بیان شده در شرایط دیگر مبالغ، نگاه کنید به
اگر شما می توانید شناسایی الگوی برای مجموع (n) است.
اگر نه، سعی کنید چند شماره های دیگر و بیان مبالغ خود را در
از لحاظ تعداد دیگری.
با شناسایی الگوهای برای گسسته اعداد، شما را به خوبی در راه خود را به هستی
شناسایی الگوی برای هر نفر.
>> بازگشت به یک ابزار واقعا قدرتمند است، پس از دوره آن را نه محدود به
توابع ریاضی.
بازگشت می تواند مورد استفاده قرار گیرد بسیار موثر در هنگام برخورد با درختان به عنوان مثال.
اتمام کوتاه در درختان برای تر بررسی دقیق، اما در حال حاضر
به یاد آورید که درخت جستجوی دودویی، در خاص، هستند تا از گره ها ساخته شده، هر
با ارزش و دو اشاره گر به گره.
معمولا، این است که نشان داده شده است گره پدر داشتن یک خط اشاره
به گره فرزند چپ و یک به گره فرزند سمت راست.
ساختار یک جستجوی دودویی درخت خود را به خوبی آشنایی
به یک جستجو بازگشتی.
تماس بازگشتی یا در عبور چپ یا گره سمت راست، اما بیشتر
که در کوتاه درخت.
>> می گویند شما می خواهید برای انجام یک عمل جراحی در هر گره در درخت جستجوی دودویی.
چگونه ممکن است به شما در مورد آن برود؟
خوب، شما می توانید از بازگشتی ارسال تابع است که انجام عملیات
در گره پدر است و باعث می شود یک بازگشتی تماس بگیرید به همان تابع،
عبور از در سمت چپ و گره فرزند سمت راست.
به عنوان مثال، این تابع، تولی، که تغییر ارزش یک گره داده شده و
همه فرزندان خود را به 1.
مورد پایه از علل گره تهی تابع به بازگشت، نشان می دهد
که هر گره وجود دارد در سمت چپ که زیر درخت.
>> اجازه دهید از طریق آن راه رفتن.
برای اولین بار پدر و مادر 13 است.
ما ارزش را تغییر دهید تا 1، و سپس تماس بگیرید عملکرد ما در سمت چپ و همچنین
به سمت راست.
تابع، تولی، در سمت چپ نام زیر درخت اول، تا گره سمت چپ
خواهد شد به 1 و تولی منصوب خواهد شد بر روی کودکان که گره نامیده می شود،
اولین سمت چپ و سپس سمت راست، و غیره و غیره.
و به آنها بگویید که شاخه لازم نیست کودکان هر بیشتر از همان پروسه
برای کودکان مناسب ادامه خواهد داد تا گره های درخت کل هستند
دوباره به 1.
>> همانطور که می بینید، شما محدود نشده است به تنها با یک تماس بازگشتی.
فقط به عنوان بسیاری را دریافت خواهید کار انجام می شود.
چه می شود اگر شما یک درخت به حال که در آن هر گره سه فرزند بود،
چپ، وسط و راست؟
چگونه تولی شما را ویرایش کنم؟
خب، ساده است.
فقط یک تماس بازگشتی اضافه کردن و پاس در اشاره گر به گره وسط.
>> بازگشت بسیار قدرتمند است و به است اشاره ظریف، اما می توان آن را
مفهوم دشوار در ابتدا، پس بیمار و وقت خود را.
شروع با مورد پایه.
معمولا ساده ترین راه برای شناسایی، و سپس شما می توانید کار
به عقب وجود دارد.
شما می دانید شما نیاز به رسیدن به خود را مورد پایه، به طوری که ممکن است
شما چند نکات می دهد.
سعی کنید برای بیان یک مورد خاص در از لحاظ موارد دیگر، و یا در زیر مجموعه.
>> برای تماشای این کوتاه است.
در دست کم، در حال حاضر شما می توانید درک جوک شبیه به این.
نام من Zamyla است، و این cs50 است.
>> نگاهی به این تابع، سلام، تابع از درجه اعتبار ساقط است که طول می کشد
یک int، n، به عنوان ورودی می باشد.
مورد پایه می آید برای اولین بار.
اگر نفر کمتر از 0، چاپ است "خداحافظ" و بازگشت.