適當的尾端遞迴
 |
||
|
適當的尾端遞迴 |
|
function f(args)
...
return g(args2)
end
遞迴函數有時可以改寫成尾端遞迴的版本。例如，階乘函數的傳統定義會帶領我們到
function fact(n) if (n==0) then return 1 else return n*fact(n-1) end end
這不是尾端遞迴，因為最後要進行的運算，是將 n和fact(n-1)相乘。但以下程式碼就是
function factt(n) return fact_(n, 1) end function fact_(n, ans) if (n==0) then return ans else return fact_(n-1, n*ans) end end
對於相同的引數，兩個定義的結果絕對相同。
> = fact(5) 120 > = factt(5) 120但在幕後的情境有所不同。如果我們以不符設計方式使用函數，就可以突顯這個差異。上面的基本實作僅適用於正整數。如果給予負數或分數結果，預計會偏離成無限遞迴。
如果我們執行 fact(-1)，就會收到堆疊溢出的訊息
> = fact(-1)
stdin:1: stack overflow
stack traceback:
stdin:1: in function `fact'
stdin:1: in function `fact'
...
stdin:1: in function `fact'
(tail call): ?
[C]: ?
另一方面，如果我們呼叫 factt(-1)，它永遠不會回傳 (此為比較類似函數主體的數學分析)。適當的尾端遞迴在於節省，這對於 Lua 所要應用於的應用程式類型非常重要。當作優化時，除錯會更為困難，因為無法重建呼叫追蹤。
每次語言規格說明已實作適當的尾端遞迴時，就表示在尾函數呼叫的特殊案例中，堆疊不會被浪費。這是語言設計者提供給使用者品質合約。在電腦科學世界中相當常見：Scheme、Perl、Forth 這些語言也這麼做。如果你的最愛程式語言沒有這麼做，那就大聲抱怨吧。
這是一個入門文字。它是要說明 Lua 功能中適當尾端遞迴這個功能，並可能在函數呼叫教學課程中提到。