تفاوت تابع بازگشتی با غیر بازگشتی
#1
Note 
برای اينکه بازگشتی موفق باشد مسئله نياز است يک زيرساختار بازگشتی داشته باشد. راه حل بعضی از مسائل به طور ذاتی بازگشتی است چون احتياج به نگداری حالت قبلی دارند. الگوريتم پيمايش درخت(tree traversal)، تابع اکرمن(Ackermann) و الگوريتم های تقسيم و غلبه مانند مرتب سازی سريع(Quicksort) همگی به صورت بازگشتی هستند. همه اين الگوريتم ها می توانند به صورت غيربازگشتی با کمک پشته هم پياده شوند اما نياز به پشته مزيت راه حل غير بازگشتی را از بين می برد.

تابع غير بازگشتی احتمالا در عمل کمی سريعتر از نسخه بازگشتی آن اجرا می شود چون تابع غير بازگشتی سربار فراخوانی تابع (function-call) را به اندازه تابع بازگشتی ندارد و اين سربار در بعضی زبان ها نسبتا بالا است.

يک دليل ديگر برای ترجيح غيربازگشتی به بازگشتی اين است که فضای پشته قابل دسترس کمتر از فضای قابل دسترس در حافظه آزاد heap است. و الگوريتم های بازگشتی تمايل به فضای پشته بيشتری نسبت به غير بازگشتی دارند.
سرريزی پشته

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


پاسخ
ایجاد موضوع جدید   پاسخ به موضوع  

موضوعات مرتبط با این موضوع...
موضوع نویسنده پاسخ بازدید آخرین ارسال
Note تابع بازگشتی چیست؟ VBProgrammer 0 857 22-02-2013 ساعت 15:42
آخرین ارسال: VBProgrammer
Note غیر فعال کردن VS just in time debugger SOFTAFZAR 0 1,349 23-07-2012 ساعت 18:52
آخرین ارسال: SOFTAFZAR

کاربرانِ درحال بازدید از این موضوع:   1 مهمان