遞歸轉非遞歸：用棧模擬函數調用可行嗎？

問題

快速排序、歸併排序等分治算法遞歸深度過大可能導致棧溢出，且函數調用開銷影響性能。能否用 函數指針 + 顯式棧 替代遞歸？

可行性分析

• 原理：將每個遞歸子任務封裝為結構體（參數、局部狀態、返回地址），壓入手動管理的棧，循環彈出執行。
• 時間複雜度：與遞歸版本相同（O(n log n)），但消除了函數調用/返回開銷，常數因子略降。
• 空間複雜度：遞歸使用系統調用棧（受限於線程棧大小，通常 1~8MB）；顯式棧使用堆內存，可動態擴展，上限僅受進程地址空間限制，解決棧溢出風險。

實際意義

對於海量數據排序，手動棧能避免棧溢出，並便於實現尾調用優化、任務竊取並行化。但代碼複雜度顯著上升，調試困難。

參考資源

CodeProject 詳細教程：How to replace recursive functions using stack and function pointers。