尾調用 (Tail Call)

recursive 的過程中可能會不斷堆疊記憶體，如果處理不當，就會造成 Stack Overflow，導致程式崩潰。一個新手常見的錯誤：只要是使用遞迴寫法，當遞回的次數夠多，就一定會造成 Stack Overflow。其實只要遞回符合 tail call 的規範，就可以避免使用過量記憶體的情況發生。

什麼是 tail call？簡單來說，當我們在目前的函式呼叫下一個函式時，只要不會再使用到目前函式的資源，這樣的呼叫方式就稱為 tail call。以下三個呼叫 g(x) 的方法，都不符合 tail call 規範，因為都還必須使用到當前函式的資源，因此當前函式並不會重記憶體堆疊中移除。

return g(x) + 1     -- must do the addition
return x or g(x)    -- must adjust to 1 result
return (g(x))       -- must adjust to 1 result

以下的函式也不符合 tail call，因為 g(x) 執行完還需要執行 return：

function f (x)
  g(x)
  return
end

在lua 中，只有 return g(...) 才符合 Tail Call 的定義，注意新手常犯的錯誤：沒有 return 是不符合的。符合 tail call 的遞回累加函式寫法：

local function tailed_sum(n, result)
  --collectgarbage()
  --print(collectgarbage("count"))
  if n == 1 then
    return result + 1
  end
  result = result + n
  return tailed_sum(n-1, result)
end

print(sum(10))
print(tailed_sum(10, 0))