منو
 کاربر Online
640 کاربر online

تکنیک بازگشتی

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)


این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


تکنیک بازگشتی


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



لذا اگر قابل محاسبه باشد قابل محاسبه است.
این نوع محاسبه منوط به یک شرط است و آن این است که تعریف تابع به تسلسل منجر نشود و آن به این معنی است که حداقل یک ورودی تابع بصورت صریح ( غیر ضمنی ) تعریف شده باشد. مثلاً یک تعریف صریح است. لذا تعریف بازگشتی بصورت زیر کامل و بدون ابهام می شود:




برنامه فاکتوریل بصورت زیر پیاده می شود:








در راستای توسعه استفاده از روش بازگشتی توابع چند متغیره را در نظر بگیرید. در این نوع توابع هم می توان مفهوم بازگشتی را اعمال کرد. مثال تابع ترکیب را در نظر بگیرید:



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














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


پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0208.pdf




تعداد بازدید ها: 7632


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..