تفاوت بین بازگشت و تکرار در برنامه نویسی چیست؟

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

بازگشت (Recursion)

بازگشت یک تکنیک برنامه نویسی است که در آن یک تابع خود را فراخوانی می‌کند تا نمونه‌های کوچکتری از یک مسئله را حل کرده تا زمانی که به یک حالت پایه (base case) برسد. این رویکرد خودخواندنی (self-calling)، مشکلات پیچیده را با تقسیم کردن آنها به مسائل فرعی قابل مدیریت ساده‌تر می‌کند.

بازگشت در دنیای واقعی

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

بازگشت چگونه کار می‌کند؟

در یک تابع بازگشتی، دو جزء اصلی وجود دارد:

• Base case: شرایطی که تابع از فراخوانی خود متوقف می‌شود و از بازگشت بی نهایت جلوگیری کرده و پاسخی مستقیم برای ساده‌ترین نمونه مشکل ارائه می‌دهد.
• Recursive case: بخشی از تابع که مشکل را به نمونه‌های کوچکتر کاهش می‌دهد و خود را با داده‌های کوچک فراخوانی می‌نماید.

تصویر زیر گردش کار یک تابع بازگشتی را نشان می دهد:

مزایای بازگشت

مزایای استفاده از Recursion به شرح زیر است:

• مشکلات پیچیده را ساده می‌کند: بازگشت می‌تواند راه حل مسائل پیچیده را با تجزیه آنها به زیرمسائل کوچکتر و قابل مدیریت ساده‌تر کند. این به ویژه برای مشکلاتی مفید است که به طور طبیعی در رویکرد  divide-and-conquerقرار می‌گیرند.
• تناسب طبیعی برای مشکلات با ساختار بازگشتی: بازگشت یک تناسب طبیعی برای مشکلات با ساختار بازگشتی ذاتی است، مانند پیمایش درخت، پیمایش نمودار، و برخی مشکلات ترکیبی.

معایب بازگشت

معایب استفاده از Recursion به شرح زیر است:

• استفاده بیشتر از حافظه به دلیل call stack: بازگشت شامل ایجاد یک فریم استک جدید برای هر call بازگشتی است که می‌تواند منجر به مصرف حافظه بالاتر در مقایسه با راه حل‌های تکرار شود. هر فراخوانی یک لایه به پشته call اضافه می‌کند، که می‌تواند به طور قابل توجهی برای بازگشت‌های عمیق رشد کند.
• خطر سرریز پشته: اگر عمق بازگشت خیلی زیاد باشد، می‌تواند از حداکثر اندازه پشته فراتر رفته و باعث خطای سرریز پشته (stack overflow) شود. این یک مشکل رایج است که به تعداد زیادی call بازگشتی نیاز دارد.
• ملاحظات عملکرد: راه‌حل‌های بازگشتی به دلیل سربار فراخوانی چند تابع و استفاده اضافی از حافظه، گاهی اوقات می‌توانند کارایی کمتری نسبت به نمونه‌های تکرار خود داشته باشند. این می تواند منجر به زمان اجرای کندتر شود، به ویژه برای مشکلاتی که می توان با روش های تکراری(iterative ) به طور موثرتر حل شوند.

تکرار (Iteration)

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

تکرار در دنیای واقعی

در باغبانی، آبیاری منظم گیاهان برای رشد و سلامت آنها ضروری است. از نظر تکرار، آبیاری منظم گیاهان شامل یک فرآیند تکراری با هدف تضمین رشد و سلامت آنها در طول زمان است.

تکرار چگونه کار می‌کند؟

در یک فرآیند تکرار شونده، مانند یک حلقه یا تابع تکرار شونده، اجزای اساسی وجود دارند که رفتار آن را دیکته می‌کنند:

• مقداردهی اولیه (Initialization): با مقداردهی اولیه متغیرها یا تنظیم شرایط اولیه مورد نیاز برای فرآیند تکراری شروع کنید.
• شرط (Condition): شرایطی را بررسی کنید که تعیین می‌کند تکرار باید ادامه یابد یا متوقف شود.
• بدنه (Body): مجموعه‌ای از دستورالعمل‌ها یا عملیاتی را اجرا می‌کند که منطق اصلی تکرار را نشان می‌دهد.
• به‌روزرسانی (Update): متغیرها یا حالت‌هایی را در تکرار تغییر دهید که به سمت برآوردن شرط یا تکمیل فرآیند پیشرفت می‌کنند.

شکل زیر گردش کار یک تابع تکراری را نشان می دهد:

ساختارهای حلقه:

 حلقه‌های For، while، Do-While

تکرار در برنامه نویسی شامل تکرار دستورالعمل‌ها تا زمانی است که یک شرط خاص برآورده شود. ساختارهای اولیه برای تکرار عبارتند از:

• حلقه For: زمانی استفاده می‌شود که تعداد تکرارها از قبل مشخص باشد.
• حلقه while: زمانی استفاده می‌شود که تعداد تکرارها ناشناخته باشد و تا زمانی که یک شرط درست باشد حلقه ادامه می‌یابد.
• حلقه Do-While: این شبیه به حلقه while است اما تضمین می‌کند که حلقه حداقل یک بار قبل از آزمایش شرط اجرا شود.

مزایای تکرار

مزایای استفاده از راه حل تکراری به شرح زیر است:

• به طور کلی حافظه کارآمدتر: تکرار (iteration) معمولا از حافظه کمتری نسبت به بازگشت استفاده می‌کند زیرا به فریم‌های پشته اضافی برای هر تکرار نیاز ندارد. در عوض، از یک متغیر کنترل حلقه استفاده می‌کند و در همان فریم فراخوانی تابع اجرا می‌شود.
• درک آسان‌تر برای مشکلات ساده: حلقه‌ها برای کارهای ساده و تکراری ساده‌تر و قابل درک هستند. آنها دنباله‌ای واضح از مقداردهی اولیه، بررسی شرایط، اجرای بدنه و به روز رسانی را دنبال می‌کنند که پیروی از منطق را آسان می‌کند.
• بدون خطر سرریز پشته: برخلاف بازگشت مجدد، تکرار شامل پشته‌های call عمیق نیست و خطر سرریز پشته را از بین می‌برد. این باعث می‌شود که تکرار برای مشکلاتی که به تکرارهای زیاد یا اندازه ورودی بزرگ نیاز دارند، انتخاب مطمئن‌تری باشد.

معایب تکرار

معایب استفاده از راه حل تکراری به شرح زیر است:

• می تواند برای مسائل با ماهیت بازگشتی کمتر بصری باشد: برای مسائلی که به طور طبیعی در یک چارچوب بازگشتی قرار می‌گیرند، مانند پیمایش درخت، پیمایش نمودار، یا مشکلات ترکیبی، راه حل‌های تکراری می‌توانند کمتر بصری باشند. رویکرد بازگشتی اغلب ساختار ذاتی مسئله را منعکس می‌کند و اجرای آن را منطقی‌تر و آسان‌تر می‌کند.
• گاهی اوقات منجر به کد پیچیده‌تر می‌شود: راه‌حل‌های تکراری گاهی اوقات می‌توانند به کد پیچیده‌تر و کمتر قابل خواندن منجر شوند، به خصوص برای مشکلاتی که به ذات بازگشتی هستند. مدیریت متغیرهای کنترل حلقه، حفظ ساختارهای داده اضافی (پشته‌ها یا صف‌ها) و اطمینان از منطق صحیح می‌تواند منجر به کد پیچیده در مقایسه با یک راه حل بازگشتی شود.

مقایسه بازگشت و تکرار

در زیر چند دستورالعمل برای انتخاب بین بازگشت و تکرار آمده است:

• ماهیت مشکل:

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

• پیچیدگی و خوانایی:

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

• ملاحظات عملکرد:

اگر ماهیت بازگشتی مشکل اجازه می‎دهد کد ظریف‌تر و قابل نگهداری‌تر و استفاده از پشته قابل مدیریت داشته باشید، از بازگشت استفاده کنید.
اگر استفاده از حافظه نگران کننده است و مشکل را می‌توان به طور موثر با حلقه‌ها حل کرد، از تکرار استفاده کنید.

انواع مشکلات مناسب برای بازگشت

• الگوریتم تقسیم و حل(D&C): مسائلی مانند ادغام مرتب سازی، مرتب سازی سریع و جستجوی باینری که در آن مشکل به زیرمسئله‌های کوچکتر تقسیم می‌شود که به صورت بازگشتی حل می‌شوند.
• مشکلات درخت و نمودار: پیمایش (مثل in-order، pre-order و post-order  برای درختان) و مسیریابی در نمودارهایی که به طور طبیعی با رویکرد بازگشتی مطابقت دارند.
• برنامه نویسی پویا: مسائلی مانند دنباله فیبوناچی، که در آن بازگشت با حافظه، راه حل را ساده می‌کند.
• مشکلات ترکیبی: ایجاد جایگشت و ترکیب و حل پازل‌هایی مانند برج هانوی.

انواع مشکلات مناسب برای تکرار

• حلقه‌های ساده: مسائلی مانند جمع کردن لیستی از اعداد، تکرار در میان آرایه‌ها یا لیست‌ها و مسائل ساده شمارش.
• مسائل خطی: راه حل‌های تکراری برای مسائلی که نیاز به اسکن خطی دارند، مانند یافتن مقدار حداکثر یا حداقل یک آرایه.
• کارهای تکراری: مشکلاتی که نیاز به تکرار یک کار چند بار مشخص دارند، مانند چاپ اعداد از 1 تا N یا تکرار از طریق ساختارهای داده مانند آرایه‌ها و لیست‌های پیوندی.

جمع‌بندی

هم بازگشت و هم تکرار مفاهیم اساسی در برنامه نویسی هستند که مزایا و معایب متفاوتی را ارائه می‌دهند. هر دو تکنیک توانایی حل مسئله شما را افزایش می‌دهند و درک شما از تفکر الگوریتمی را عمیق‌تر می‌کنند.