یک تابع یا متد tail-recursive تابعی است که قابلیت بهینه سازی در زمان کامپایل را دارد بصورتی که تابع tail-recursive با اینکه بازگشتی است ولی از حافظه استک استفاده نمی کند.
فرض کنید می خواهیم یک متد داشته باشیم که با گرفتن x که یک عدد است، حاصل جمع 1 تا x را محاسبه کند.
پیاده سازی بازگشتی به زبان جاوا:
public int sumTo(int x) {
if (x == 1) {
return x;
} else {
return x + sumTo(x - 1);
}
}
نحوه محاسبه مقدار حاصل جمع در کد بالا بصورت زیر است:
sumTo(5)
5 + sumTo(4)
5 + (4 + sumTo(3))
5 + (4 + (3 + sumTo(2)))
5 + (4 + (3 + (2 + sumTo(1))))
5 + (4 + (3 + (2 + 1)))
15
همانطور که ملاحظه می کنید در این متد بدلیل اینکه فراخوانی بازگشتی آخرین عملیات متد نیست برای محاسبه حاصل جمع نیاز به نتیجه فراخوانی قبلی وجود دارد (استفاده از استک) این روش استفاده از متدهای بازگشتی tail-recursive نیست و حتما نیاز به استفاده از حافظه استک دارد و در صورتی که مقدار x زیاد باشد به خطای stack overflow برخورد می کند.
پیاده سازی tail-recursive با زبان جاوا:
public int tailRecSumTo(int x, int total) {
if (x == 0) {
return total;
} else {
return tailRecSumTo(x - 1, total + x);
}
}
نحوه محاسبه مقدار حاصل جمع در کد بالا بصورت زیر است:
tailRecSumTo(5, 0)
tailRecSumTo(4, 5)
tailRecSumTo(3, 9)
tailRecSumTo(2, 12)
tailRecSumTo(1, 14)
tailRecSumTo(0, 15)
15
در پیاده سازی با روش tail-recursive ابتدا عملیات و محاسبات لازم انجام شده و در نهایت فراخوانی بازگشتی انجام شده است، این روش پیاده سازی باعث می شود که نیازی به نگهداری وضعیت فراخوانی تابع قبلی در استک نباشد و در نتیجه حتی اگر x خیلی بزرگ باشد هم به خطای stack overflow برخورد نمی شود.
نکته: حتی اگر شما تابع خود را به روش tail-recursive پیاده سازی کنید ولی کامپایلر زبان شما هیچ بهینه سازی برروی آن انجام ندهد باز هم مشکل خطای stack overflow را خواهید داشت. کامپایلر های زبان های Scala، Lisp و Erlang این بهینه سازی را انجام می دهند و برای مثال در زبان پایتون هیچ بهینه سازی برای توابع tail-recursive انجام نمی شود و تفاوتی بین دو پیاده سازی بالا وجود ندارد.
