فهرست مندرجات

طراحی بازگشتی الگوریتم

مقدمه

1- تعریف

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

2- انواع تابع بازگشتی

1- تابع بازگشتی مستقیم

به تابع بازگشتی گفته می شود که در داخل بدنه تابع، همان تابع با پارامتر های متفاوتی صدا زده می‌شود.

2- تابع بازگشتی غیر مستقیم

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

3- مزایا و معایب الگوریتم های بازگشتی

مزیت‌های الگوریتم‌های بازگشتی را می‌توان به صورت خلاصه بدین صورت بیان کرد،سازگاری با طبیعت مسأله (برخی مسأله‌ها ذاتا بازگشتی هستند)، خوانایی زیاد، سادگی، کوتاهی کد الگوریتم از نظر تعداد دستورات و …
اما مهمترین عیب الگوریتم های بازگشتی، فراخوانی تابع به تعداد دفعات زیاد است که از نظر حافظه و زمان سربار قابل توجهی ایجاد می‌کند.

پیاده سازی بازگشتی

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

کاربرد‌ها

با توجه به سادگی پیاده‌سازی این الگوریتم‌ها، الگوریتم‌های بازگشتی کاربرد بسیار زیادی دارند.
دقت کنید تمامی الگوریتم‌هایی که به صورت بازگشتی قابل پیاده‌سازی هستند، به صورت غیر بازگشتی هم می‌توانند پیاده‌سازی شوند ولی معمولا پیاده‌سازی غیر بازگشتی بسیار مشکل‌تر از پیاده‌سازی بازگشتی ‌است. از جمله الگوریتم‌هایی که به صورت بازگشتی قابل پیاده‌سازی هستند عبارت‌اند از : مسأله برج هانوی، محاسبه‌ی توان، بزرگترین مقسوم علیه مشترک، اعداد فیبوناچی و …