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

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

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

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

[url]http://stcomputer.ir[/url]