بازگشت (Recursion)
بازگشت یعنی تابع خودش را صدا بزند. «بازگشت (Recursion)» روش حل مسئله بزرگ با شکستن به مسئله های کوچک است. «تابع (Function)» قطعه کدی با نام مشخص است. با تمرین، درک آن ساده تر می شود.
ایده اصلی بازگشت
تابع تا وقتی «شرط پایان» برقرار نشده، دوباره خودش را صدا می زند. سپس برمی گردد و پاسخ ها را جمع می کند.
نکته: «شرط پایان (Base Case)» یعنی جایی که دیگر صدا نزنیم.
مثال: جمع 1 تا 10 با بازگشت
با شکستن جمع بزرگ، به جمع های کوچک می رسیم.
int sum(int k);
int main() {
int result = sum(10);
printf("%d", result);
return 0;
}
int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
توضیح کوتاه: هر بار k کم می شود تا به صفر برسد. سپس نتایج برمی گردند.
مثال: شمارش معکوس بازگشتی
تا رسیدن به صفر، خود تابع با n-1 ادامه می دهد.
void countdown(int n);
int main() {
countdown(5);
return 0;
}
void countdown(int n) {
if (n > 0) {
printf("%d ", n);
countdown(n - 1);
}
}
مثال: فاکتوریل بازگشتی
فاکتوریل n برابر n×(n-1)×...×1 است. فاکتوریل 0 برابر 1 است.
int factorial(int n);
int main() {
printf("Factorial of 5 is %d", factorial(5));
return 0;
}
int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}
گام های عملی
- مسئله بزرگ را کوچک کن.
- شرط پایان دقیق بنویس.
- فراخوانیِ دوباره با ورودی کوچک تر انجام بده.
- کد را اجرا و مسیر بازگشت را بررسی کن.
هشدار: شرط پایان مبهم، حلقه بی پایان می سازد و حافظه را می بلعد.
برای مرور «بازگشت» دوباره برگرد. همچنین فصل توابع inline را ببین.
جمع بندی سریع
- بازگشت یعنی صدا زدنِ دوباره همان تابع.
- همیشه شرط پایان دقیق بنویس.
- برای مسائل تقسیم پذیر عالی است.
- حواست به مصرف حافظه باشد.