簡介
尾遞迴(tail recursion)是一種特殊的遞迴形式,其中遞迴調用是函數的最後一個動作。在尾遞迴中,遞迴調用的結果直接返回,而不會在每一層的遞迴中進行額外的計算。這使得編譯器或解釋器可以輕易地將遞迴實現為迴圈,從而減少調用堆疊的深度,避免堆疊溢出。
實際範例
這邊替大家找到一個清楚的範例你所不知道的 C 語言:遞迴呼叫篇,範例清楚地比較尾遞迴優化後組合語言的差異
尾遞迴優化前:使用callq函式呼叫,產生新的stack frame
尾遞迴優化後:使用jne跳轉到迴圈起始點,不產生新的Stack frame,完成尾遞迴優化
心得
在可以直接控制的情境下,特別是在像C這樣的命令式編程語言中,直接使用迴圈來替代尾遞迴的確是一個性能更可預測且通常更高效的選擇。這不僅可以避免依賴於編譯器進行特定的優化,還可以提供更清晰的性能特性和更好的可讀性(對於那些不太熟悉遞迴或函數式編程模式的開發者來說)。
總之,如果算法或計算可以自然地表示為迴圈,而且沒有特定的理由必須使用遞迴(如算法的語義、可讀性考量或語言特性),那麼使用迴圈通常是更好的選擇。这种方式直接利用了迴圈的性能優勢,而無需依賴於編譯器的尾遞迴優化。