如何將遞迴函數改成迭代函數?
遞迴(Recursive)函數是在執行的過程又會直接或間接地呼叫自己本身的函數。通常透過遞迴函數可以快速地驗證我們的演算法,用簡短的程式碼處理複雜的問題,但是函數在呼叫時需要建立新的堆疊框(Stack Frame),除了會需要額外的開支(Overhead)之外,如果在函數中呼叫函數,而這函數又會呼叫函數,持續下去,很容易就會造成堆疊溢出(Stack Overflow)。雖然有些程式語言的編譯器會做尾端呼叫消除(Tail Call Elimination, TCE)的優化(Tail Call Optimization, TCO),可以讓我們將遞迴函數設計成尾端遞迴(Tail Recursive)來避免分配額外的堆疊空間建立新的堆疊框,但編譯器其實並不能保證一定會去進行尾端呼叫消除。所以到頭來,我們應該還是儘量使用迭代函數會比較好。那麼大問題就來了:要如何將遞迴函數改成迭代函數呢?