موضوع مقاله: بازگشت (علوم رایانه) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بازگشت (علوم رایانه) | مقدمه: بازگشت در علوم رایانه، روشی برای حل یک مسئله است که در آن راه‌حل مسئله به راه‌حل هایی در نمونه های کوچکتر از همان مساله وابسته می باشد. | ## بخش 1: بازگشت (علوم رایانه) | همچنین از آنجایی که ریشهٔ این کلمه در زبان انگلیسی فعل Recur به معنای "اتفاق افتادن مجدد" می‌باشد ترجمه‌های مناسب دیگر می توانند "توابع بازوقوع" و "توابع بازفراخوانی شونده" باشند، که همگی قطعا بهتر از ترجمهٔ مشهور و ضعیف آن(توابع بازگشتی) می‌باشند. به هر حال، نگرش خوداتکاء یا بازگشتی در علم کامپیوتر یک روش فکر کردن برای حل مسائل است. حل یک مسئله به روش خوداتکاء/بازگشتی بدین معناست که راه حل بستگی به مدل کوچکتری از صورت مسئله داشته باشد. "قدرت بازگشت قطعاً در این نهفته‌است که دسته‌ای نامتناهی از اشیا را بوسیلهٔ یک عبارت متناهی تعریف می‌کند. به معنای دیگر یک عدد نامتناهی در محاسبات می‌تواند بوسیلهٔ یک برنامهٔ متناهی بازگشتی تعریف شود حتی اگر این برنامه هیچ تکرار واضحی نداشته باشد ". اکثر زبان‌های برنامه نویسی سطح بالا عمل بازگشت را به این صورت تعریف می‌کنند که یک تابع خودش را فراخوانی کند. بعضی از زبان‌های تابعی هیچ ساختار حلقه‌ای تعریف نمی‌کنند اما بر خود بازگشت تکیه دارند که کد را به‌طور مکرر فراخوانی کند. نظریهٔ رایانش‌پذیری ثابت کرده‌است که این زبان‌های فقط بازگشتی از نظر ریاضی برابر زبان‌های دستوری هستند، یعنی اینکه مسائل را بدون نیاز به while و for حل می‌کنند. الگوریتم‌های بازگشتی در ریاضیات کاربردی و به خصوص کامپیوتر، مسائل فراوانی وجود دارد که حل آن‌ها را به سادگی می‌توان به صورت یک الگوریتم بازگشتی نشان داد. یک الگوریتم بازگشتی مانند یک تابع یا یک دنباله بازگشتی تعریف می‌شود فرمان‌های الگوریتم به‌طور مکرر و با پارامترهای مختلف اجرا می‌شوند تا به فرمان بنیادی الگوریتم برسیم. آنگاه تمام مقادیری را که محاسبهٔ آن‌ها انجام نشده‌است را به صورت بازگشتی محاسبه می‌نماییم تا فرمان مورد نظر اجرا شود. | ## بخش 2: بازگشت (علوم رایانه) | یک روش متداول برای آسان‌سازی مسائل این است که آن‌ها را به زیر مسائلی از همان نوع تقسیم بندی کنیم. تمام زبان‌های برنامه‌نویسی که امروز مورد استفاده‌اند تعریفی مستقیم از توابع بازگشتی در خود دارند. وقتی چنین تابعی فراخوانی می‌شود، کامپیوتر(برای اکثر زبان‌هایی که پشته دارند) یا خود کد زبان instanceهای مختلف تابع را (با فراخوانی پشته، هر چند روش‌های دیگر هم مورد استفاده قرار می‌گیرند). برعکس آن همهٔ توابع بازگشتی می‌توانند به کمک پشته به یک تابع غیر بازگشتی تبدیل شوند. اکثر توابع و روش‌هایی که می‌توانند بوسیلهٔ کامپیوتر ارزشیابی شوند بدون استفاده از غیر بازگشتی کردن قابل بازگشتی شدن هستند. برنامه‌نویسی بازگشتی بعضاً الگوریتم‌های بازگشتی را می‌توان به کمک زبان‌های برنامه‌نویسی پیاده‌سازی کرد که به این برنامه‌ها برنامه‌های بازگشتی گفته می‌شود. کاهنان معبد در تلاش بودند تا قرص‌های طلائی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است: در هر زمان فقط یک دیسک را می‌توان جابجا نمود. هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد. توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد. | ## بخش 3: بازگشت (علوم رایانه) | برای اینکه مسئله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مسئله اصلی (مسئله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر باشد. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین‌ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم: n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. n - ۱ دیسک را که هم‌اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. غالباً انتخاب یک ساختمان داده موجب ایجاد الگوریتم‌های متناسب با آن خواهد شد که این دو در کنار هم موجب افزایش سرعت انجام یک وظیفه یا کاهش مصرف حافظه برای پردازش داده می‌شود؛ سنگ بنای ساختمان‌های داده انواع داده و اشاره گرهای گوناگون است. که با توجه به چگونگی تعریف کاربرد آن‌ها در هر زبان برنامه نویسی پیاده‌سازی آن‌ها متفاوت خواهد بود. لیست پیوندی در زیر می‌توانید تعریف ساده‌ای از گرهٔ فهرستهای پیوندی را مشاهده کنید. در اینجا دو اشاره‌گر داریم، یکی به زیر درخت سمت چپ و دیگری به زیر درخت سمت راست. اما در هر حال هر کدام برتری‌ها و کاستی‌های نسبت به دیگری دارد و در موارد خاصی الگوریتم‌ها فقط با یکی از این روش قابل پیاده سازی‌اند. ترتیب فراخوانی توابع تابع ۱ ترتیب فراخوانی توابع تأثیر به سزایی در اجرای برنامه دارد. | ## جمع‌بندی | بازگشت غیرمستقیم زمانی است که به‌طور مثال تابع «الف» تابع «ب» و تابع «ب« تابع «ث« و تابع «ث» نیز دوباره تابع «الف» را فراخوانی کند.