در این مطلب میخواهیم درباره یکی از جذاب ترین و مهم ترین مباحث الگوریتم صحبت کنم؛ توابع بازگشتی. توابع بازگشتی در حل مسائل پیچیده الگوریتمی به ما کمک زیادی میکنند. مسائلی مثل جستجو و مرتب سازی و... در این مقاله با مفهوم تابع بازگشتی و کاربرد آن آشنا میشویم و مثال هایی از آن را بررسی میکنیم.
تابع بازگشتی به هر تابعی گفته میشود که خودش را صدا بزند. با یک مثال میتوانیم این تعریف را بهتر درک کنیم. فرض کنیم که میخواهیم یک تابع برای محاسبه فاکتوریل بنویسیم که عدد n را به عنوان ورودی دریافت میکند و فاکتوریل آن را حساب میکند.(تعریف فاکتوریل : حاصل ضرب اعداد یک تا n)
یکی از ساده ترین روش های پیاده سازی این تابع استفاده از تابع بازگشتی است، به این صورت که برای محاسبه فاکتوریل n کافیست عدد n را در فاکتوریل n-1 ضرب کنیم. به همین راحتی بدون هیچ الگوریتم نویسی پیچیده میتوانیم این تابع را پیاده سازی کنیم.
الگوریتم بازگشتی به الگوریتم هایی میگوییم که در پیاده سازی آنها از توابع بازگشتی استفاده میشود. در واقع در الگوریتم بازگشتی ما مسئله را به مسائل کوچک تر تقسیم میکنیم و برای آنها راه حل ارائه میدهیم.
چرا باید از الگوریتم بازگشتی استفاده کنیم؟ آیا الگوریتم بازگشتی باعث بهبود عملکرد نرم افزار میشود؟ جواب این است که خیر الگوریتم بازگشتی باعث بهبود عملکرد نمیشود بلکه حتی در اکثر موارد باعث میشود حافظه کامپیوتر بیش از حد درگیر شود. پس اصلا چرا باید از آن استفاده کنیم؟ توابع بازگشتی در زمان اجرا هیچ مزیت خاصی ندارد اما در زمان طراحی الگوریتم به ما کمک زیادی میکند. در واقع تنها دلیلی که ما از توابع بازگشتی استفاده میکنیم این است که حل بعضی مسائل از طریق الگوریتم بازگشتی راحت تر است.
اینکه از الگوریتم بازگشتی استفاده کنیم یا نه، بستگی به اولویت های ما دارد. آیا اینکه الگوریتم ما ساده تر باشد و بتوانیم به راحتی آن را بنویسیم مهم تر است یا اینکه بازدهی بهتر نرم افزار مهم تر است هرچند به قیمت پیچیده شدن الگوریتم باشد؟
به دلیل اینکه توابع بازگشتی خودشان را صدا میزنند، احتمال اینکه با پیاده سازی اشتباه، درگیر حلقه بی پایان شویم زیاد است. باید دقت کنیم که حتما یک حالت پایه یا همان شرط خروج برای تابع باز گشتی خودمان در نظر بگیریم، در غیر این صورت تابع بازگشتی دائما خودش را صدا میزند تا جایی که حافظه کامپیوتر پر شود و برنامه متوقف شود.
الگوریتم بازگشتی، کمک میکند تا بتوانیم مسائل پیچیده رو خرد کنیم و به مسائل ساده تر تبدیل کنیم، اما این خرد کردن نباید تا ابد ادامه پیدا کند، باید یک حالت پایه برای الگوریتم در نظر بگیریم که دیگر نیاز به خرد کردن آن وجود ندارد. برای مثال به الگوریتم بازگشتی فاکتوریل توجه کنید.
Factorial(n) => n * Factorial(n-1)
حالت پایه این الگوریتم میتواند عدد صفر باشد، یعنی هرگاه فاکتوریل صفر از ما خواسته شد، ما دیگر مرحله بازگشتی را تکرار نمیکنیم، بلکه از پیش میدانیم که Factorial(0) مساوی یک خواهد بود. کد این الگوریتم در زبان C# به صورت زیر خواهد بود
برای اینکه درک بهتری از ساده کردن الگوریتم ها با روش تابع بازگشتی داشته باشیم، بهتر است برویم سراغ الگوریتمی که کمی پیچیده تر باشد. در یکی از مقالات قبلی درباره الگوریتم های جستجو صحبت کردیم و فلوچارت آن را کشیدیم. حالا میخواهیم جستجوی دودویی را با استفاده از تابع بازگشتی پیاده سازی کنیم. کدنویسی با زبان C# انجام شده
زمانی که تابع بازگشتی استفاده میکنیم، کامپیوتر باید دیتای مربوط به هر مرحله را در حافظه خود ذخیره داشته باشد. وقتی توابع را درون هم صدا میزنیم، کامپیوتر باید بداند که بعد از پایان هر تابع، به کدام تابع بازگردد و دیتای مربوط به آن تابع را برگرداند. این مسائل به نظر پیچیده و کمی گیج کننده است. کامپیوتر چطور این مسائل را مدیریت میکند؟
برای پاسخ این سوال ابتدا باید با یک ساختار داده دیگر آشنا شویم؛ پشته یا همان Stack
پشته یک ساختار داده است برای نگه داری از مجموعه ای از داده ها. ساختار پشته به این صورت است که داده ها یکی یکی وارد آن میشوند و پشت یکدیگر قرار میگیرند، هر زمان که بخواهیم داده های stack را بخوانیم باید از آخرین داده شروع کنیم یکی بخوانیم، یعنی هر داده ای که زود تر در پشته، وارد شده باشد دیرتر خارج خواهد شد. مانند اینکه بخواهیم تعدادی کتاب را روی یکدیگر بچینیم. اولین کتابی قرار دهیم زیر همه کتاب های بعدی قرار خواهد گرفت در نتیجه برای بیرون کشیدن آن باید از بالا یکی یکی، کتاب ها را برداریم.
کامپیوتر برای مدیریت ترتیب تابع ها از یک stack درون خودش استفاده میکند. به این شکل که هر گاه وارد تابع جدیدی میشویم اطلاعات و متغیر های مربوط به آن تابع را در پشته ذخیره میکند، اطلاعات تابع جدید در پشته روی دیتای قبلی قرار میگیرد و هرگاه عملیات آن تابع تمام شود مجددا به تابع قبلی برمیگردم که در Call Stack قبل از تابع تمام شده قرار دارد. اگر این مفهوم کمی پیچیده است، نگران نباشید فعلا لازم نیست بیشتر از این، آشنا شویم اما اگر علاقه مند هستید میتوانید درباره نحوه عملکرد آن بیشتر مطالعه کنید.
الگوریتم های بازگشتی هرچند در بهبود سرعت و عملکرد نرم افزار کمکی به ما نمیکنند، اما کمک میکنند تا مسائل پیچیده را خرد کنیم و الگوریتم ساده تری برای آن بنویسیم. در واقع الگوریتم بازگشتی قرار است کار را برای برنامه نویس ساده تر کند نه کامپیوتر. نکته مهم دیگر این است که هنگام استفاده از توابع بازگشتی حتما باید دقت کنیم که شرط خروج درستی برای آن در نظر گرفته باشیم، وگرنه تابع ما، همینطور خودش را صدا میزند تا زمانی که حافظه کامپیوتر پر شود و نرم افزار متوقف شود.
خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.
منبع : سری مقالات الگوریتم و ساختمان داده از سایت خودم
