0 امتیاز
قبل در برنامه نویسی توسط (1.1هزار امتیاز)

در روش ها و الگوریتم های بازگشتی که در زبان های برنامه نویسی functional کاربرد زیادی دارد با مفهوم Tail recursion برخورد کرده ام، Tail recursion چیست و چه کاربردهایی دارد؟

2 پاسخ

+1 امتیاز
قبل توسط (1.1هزار امتیاز)
ویرایش شده قبل توسط
 
بهترین پاسخ

یک تابع یا متد 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 انجام نمی شود و تفاوتی بین دو پیاده سازی بالا وجود ندارد.

+1 امتیاز
قبل توسط (10 امتیاز)

در موارد زیادی از جمله مرتب سازی و الگوریتم های مربوط به درخت برنامه نویسان علاقه به استفاده از متد های بازگشتی دارند. درصورتی که متد باز گشتی تعداد دفعات زیادی فراخوانی شود باعث به وجود آمدن شرایط غیر قابل پیش بینی و stack overflow خواهد شد. برای جلوگیری از این اتفاق باید متد خود را با حلقه ها به صورت شبیه سازی کنیم که به جای stack از heap استفاده نماییم برای این کار روش های طراحی متفاوتی وجود دارد که یکی از روش های عمومی آن را می توانید در آدرس زیر ببینید:

http://www.jndanial.com/fa/90

سوالات مشابه

0 امتیاز
1 پاسخ 1.3هزار بازدید
0 امتیاز
0 پاسخ 903 بازدید
0 امتیاز
2 پاسخ 2.6هزار بازدید
0 امتیاز
0 پاسخ 609 بازدید
0 امتیاز
0 پاسخ 311 بازدید
0 امتیاز
0 پاسخ 284 بازدید
+1 امتیاز
1 پاسخ 752 بازدید
0 امتیاز
1 پاسخ 1.4هزار بازدید
...