تابع بازگشتی در برنامه نویسی C

تابع بازگشتی چیست ؟

توابع بازگشتی (Recursive Functions) در برنامه‌نویسی به توابعی گفته می‌شود که در تعریف خود، دوباره خودشان را فراخوانی می‌کنند. این تکنیک یکی از ابزارهای مهم و قدرتمند در حل مسائل پیچیده و تقسیم آنها به زیرمسائل کوچکتر است. در یک تابع بازگشتی، مسئله اصلی به مسائل کوچکتر تقسیم می‌شود و سپس هر کدام از این زیرمسائل به صورت بازگشتی حل می‌شوند تا زمانی که به یک حالت پایه (Base Case) برسند که بدون نیاز به بازگشت می‌توان آن را مستقیماً حل کرد.

یک نمونه کلاسیک از استفاده توابع بازگشتی، محاسبه فاکتوریل یک عدد است. تابع فاکتوریل $𝑛!$ به صورت بازگشتی به شکل زیر تعریف می‌شود:

در این مثال، حالت پایه $\text{factorial}(0)=1$ است و برای مقادیر بزرگتر از صفر، تابع بازگشتی با فراخوانی خود و کاهش مقدار $𝑛$ به حل مسئله ادامه می‌دهد.

توابع بازگشتی در بسیاری از الگوریتم‌ها و مسائل مانند جستجوی دودویی، پیمایش درخت‌ها، و حل مسائل تقسیم و غلبه (Divide and Conquer) مانند مرتب‌سازی سریع (Quick Sort) و مرتب‌سازی ادغامی (Merge Sort) استفاده می‌شوند. اگرچه توابع بازگشتی می‌توانند کد را ساده‌تر و خواناتر کنند، اما نیاز به دقت زیادی دارند زیرا استفاده نادرست از آنها می‌تواند منجر به مشکلاتی مانند بازگشت بی‌نهایت و در نتیجه خطای کمبود حافظه شود.

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

به تابعی که خود را فراخوانی می کند، تابع بازگشتی می گویند و این روش به عنوان بازگشت شناخته می شود.

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

void recurse()

{

… .. …

recurse(); // فراخوانی تابع داخل خود تابع

… .. …

}

int main()

{

… .. …

recurse();

… .. …

}

بازگشت زمانی متوقف می شود که یک شرط (ها) برقرار شودف به این شرط، شرط توقف می گویند.

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

مثال: مجموع اعداد طبیعی با استفاده از تابع بازگشتی

#include

int sum(int n);

int main() {

int number, result;

printf(“Enter a positive integer: “);

scanf(“%d”, &number);

result = sum(number);

printf(“sum = %d”, result);

return 0;

}

int sum(int n) {

if (n != 0)

// خود را فراخوانی می کند sum() تابع

return n + sum(n-1);

else

return n;

}

خروجی

Enter a positive integer:3

sum = 6

ابتدا تابع ()sum درون تابع ()main با ارسال آرگومانnumber  فراخوانی می شود.

فرض کنید کاربر عدد ۳ را وارد می کند و این مقدار در اولین فراخوانی در پارامتر n تابع ()sum قرار می گیرد. با فراخوانی بعدی تابع درون خود تابع، n-1 یعنی عدد ۲ به تابع ()sum ارسال می شود. این روند ادامه می یابد تا n برابر با ۰ شود.

وقتی n برابر با ۰ شد، شرط if برقرار نیست و قسمت else اجرا می شود. در نهایت مجموع اعداد صحیح به تابع ()main برگردانده می شود.

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

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

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