بازگشت (علوم رایانه)
From Wikipedia, the free encyclopedia
بازگشت (به انگلیسی: Recursion) در علوم رایانه، روشی برای حل یک مسئله است که در آن راهحل مسئله به راهحل هایی در نمونه های کوچکتر از همان مساله وابسته می باشد[1].
به نظر میرسد ترجمه «بازگشت» بیشتر مناسب کلمه انگلیسی Return باشد تا کلمه Recursion ؛ به همین دلیل بعضی از اساتید عبارت «توابع خوداتکاء» را برای نامیدن اینگونه توابع به کار میبرند. همچنین از آنجایی که ریشهٔ این کلمه در زبان انگلیسی فعل Recur به معنای "اتفاق افتادن مجدد" میباشد ترجمههای مناسب دیگر می توانند "توابع بازوقوع" و "توابع بازفراخوانی شونده" باشند، که همگی قطعا بهتر از ترجمهٔ مشهور و ضعیف آن(توابع بازگشتی) میباشند. به هر حال، نگرش خوداتکاء یا بازگشتی در علم کامپیوتر یک روش فکر کردن برای حل مسائل است. در واقع خوداتکایی یا بازگشت یکی از ایدههای اصلی علم کامپیوتر است.[2] حل یک مسئله به روش خوداتکاء/بازگشتی بدین معناست که راه حل بستگی به مدل کوچکتری از صورت مسئله داشته باشد.[3]
"قدرت بازگشت قطعاً در این نهفتهاست که دستهای نامتناهی از اشیا را بوسیلهٔ یک عبارت متناهی تعریف میکند. به معنای دیگر یک عدد نامتناهی در محاسبات میتواند بوسیلهٔ یک برنامهٔ متناهی بازگشتی تعریف شود حتی اگر این برنامه هیچ تکرار واضحی نداشته باشد ".[4]
اکثر زبانهای برنامه نویسی سطح بالا عمل بازگشت را به این صورت تعریف میکنند که یک تابع خودش را فراخوانی کند. زبانهای دستوری ساختارهای حلقهای مثل while
یا for
را برای انجام کارهای تکراری به کار میگیرند. بعضی از زبانهای تابعی هیچ ساختار حلقهای تعریف نمیکنند اما بر خود بازگشت تکیه دارند که کد را بهطور مکرر فراخوانی کند. نظریهٔ رایانشپذیری ثابت کردهاست که این زبانهای فقط بازگشتی از نظر ریاضی برابر زبانهای دستوری هستند، یعنی اینکه مسائل را بدون نیاز به while
و for
حل میکنند.