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

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

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

اکثر کامپایلرها برای فراخوانی و برگشت از زیربرنامه call stack  را پیاده سازی می کنند. Call stack یا run-time stack یک پشته است که اطلاعاتی درباره زیربرنامه فعال یک برنامه را نگهداری می کند. زیربرنامه فعال زیربرنامه ای است که فراخوانی شده است اما هنوز اجرایش تمام نشده است. در زبان های سطح بالا call stack معمولا از برنامه نویس مخفی است. درمقابل در زبان اسمبلی نیاز است خود برنامه نویس با پشته درگیر شود.

وقتی زیربرنامه ای فراخوانی می شود، قبل از اینکه کنترل اجرای برنامه به آدرس زیربرنامه پرش کند آدرس دستورالعمل بعدی (دستورالعملی که درحافظه بعد از دستور فراخوانی قرار دارد) درجائی باید ذخیره شود که هنگام برگشت از زیربرنامه از آن استفاده می شود. این آدرس را آدرس برگشتی (return addresses) می نامند. معماری که بر اساس پشته  است آدرس برگشتی را به عنوان نقطه برگشت در پشته اضافه می شود. هر بار که زیربرنامه ای فراخوانی می شود آدرس برگشتی در پشته push می شود. هنگام برگشت از زیربرنامه آدرس برگشتی از پشته pop شده و کنترل برنامه به آن آدرس پرش می کند و اجرای برنامه از بعد از دستور فراخوانی  ادامه پیدا می کند. اکثر زبان‌های برنامه نویسی سطح بالاعمل بازگشت را به این صورت تعریف می‌کنند که یک تابع خودش را فراخوانی کند. زبان‌های imperative ساختارهای حلقه‌ای مثل while و یا for را برای انجام کارهای تکراری به کار می‌گیرند. بعضی از زبان‌های functional هیچ ساختار حلقه‌ای تعریف نمی‌کنند اما بر خود بازگشت تکیه دارند که کد را به طور مکرر فراخوانی کند. تئوری شماره پذیری ثابت کرده‌است که این زبان‌های فقط بازگشتی از نظر ریاضی برابر زبان‌های imperative هستند، یعنی اینکه مسائل را بدون نیاز به while و for حل می‌کنند.

الگوریتم‌های بازگشتی:

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

فیبوناتچی:

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

بازگشتی در مقابل غیر بازگشتی:

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

بازگشت مستقیم و غیرمستقیم:

بازگشت مستقیم زمانی است که تابع خود را فراخوانی کند. بازگشت غیرمستقیم زمانی است که به طور مثال تابع الف تابع ب و تابع ب تابع ث و تابع ث نیز دوباره تابع الف را فراخوانی کند.

برای درک بهتر این موضوع میتوانید به لینک زیر مراجعه کنید:

http://en.wikipedia.org/wiki/Return_statement

http://www.hpkclasses.ir/Courses/DataStructure/ds0900.html