بازگشتی بودن فرآیندی است که در آن یک تابع به طور مکرر خودش را فراخوانی می‌کند تا آنکه به شرط خاصی برسد. استفاده از این روش جهت انجام محاسبات تکراری که در آن منطقی وجود دارد مناسب است. از نظر ریاضی، یک تابع بازگشتی یا خودگردی تابعی است که برحسب خودش تعریف می‌شود. به عنوان مثال فاکتوریل عدد صحیح و مثبت m، که آن را با m! نمایش می‌دهند، به شکل متداول به صورت زیر تعریف می‌گردد.
m! = m(m-1)(m-2) …. ۳٫ ۲٫ ۱
در ضمن فاکتوریل صفر برابر ۱ است.
راه دیگر برای تعریف فاکتوریل که روش بازگشتی است این است که اگر ۱ m =، خروج؛ در غیر این‌صورت m(m-1)!.
ملاحظه می‌کنید که در روش دوم، در صورتی که m بزرگ‌تر از یک باشد، فاکتوریل آن به طور مستقیم محاسبه نمی‌شود، بلکه برحسب فاکتوریل عدد (m-1) تعریف می‌شود. مثلاً فاکتوریل عدد ۴ به صورت ۴! = ۴ * ۳! تعریف می‌شود؛ یعنی تابع دوباره برحسب خودش تعریف می‌شود. به عبارت دیگر تعریف تابع روی خود تابع برمی‌گردد. بنابراین فاکتوریل ۴ دوباره به صورت ۴! = ۴ * ۳! تعریف می‌شود. این روش ادامه پیدا می‌کند تا اینکه آرگومان تابع به ۱ برسد که در این حالت پاسخ آن برابر ۱ خواهد بود. در اینجاً باید به عقب برگشت و مقادیر ایجاد شده را در یکدیگر ضرب کرد تا در پایان فاکتوریل عدد ۴ به دست آید.
از نظر برنامه‌نویسی، در صورتی تابع را بازگشتی نامند که به طور مستقیم یا غیرمستقیم تابع خود را فراخوانی کند. در بعضی زبانهای برنامه‌سازی مانند بیسیک و فورترن، روش تعریف تابع به صورت بازگشتی پیش‌بینی نشده است؛ یعنی امکان خودفراخوانی تابع وجود ندارد. در بعضی از زبانها این امکان پیش‌بینی شده، ولی هنگام تعریف تابع، باید به طور صریح مشخص گردد که تابع به صورت بازگشتی تعریف می‌گردد تا کامپایلر تابع مزبور را تابع بازگشتی بشناسد. زبان برنامه‌نویسی PL/I از این گروه است. در زبان پاسکال هم استفاده از توابع بازگشتی امکان پذیر است. در زبان C، همه توابع می‌توانند به صورت بازگشتی به کار برده شوند و نیاز نیست که‌این عمل به طور صریح بیان گردد؛ یعنی تعریف یا اعلان خاصی نیاز نیست. ایده تابع بازگشتی در شکل اولیه‌اش ساده است.
مثال به‌این برنامه توجه کنید.
main()
{
printf(“\n HELLO “) ;
main()
}
ملاحظه می‌کنید که این برنامه پایان‌ناپذیر است و بی‌‌نهایت بار اجرا می‌شود؛ یعنی تابع اصلی مرتب خودش را فراخوانی می‌کند و در هر فراخوانی عبارت ” HELLO ” چاپ می‌گردد. واضح است که‌این نوع خودفراخوانی توابع مطلوب نیست؛ یعنی باید تعداد دفعات خودفراخوانی متناهی باشد تا مانند مثال بالا با حلقه بدون پایان مواجه نشویم.
مثال تابع زیر مجموع اعداد طبیعی ۱ تا n را به شکل بازگشتی محاسبه می‌کند.
int sum (int n)
{
if (n<=1)
return (n) ;
else
return (n+sum (n-1)) ;
}
نحوه عملکرد این تابع در بعضی مقادیر n در جدول زیر تجزیه، تحلیل و نمایش داده شده است.
مثال برنامه زیر، با استفاده از تابع بازگشتی، فاکتوریل اعداد صفر تا ۱۰ را محاسبه می‌کند و در خروجی نشان می‌دهد.
