Luaは末尾再帰の最適化を行う
Luaは末尾再帰の最適化を行うらしい。プログラムを書いて確かめてみる。
function add(n) if n == 0 then return 0 else return 1 + add(n-1) end end function addTCO(n, acc) if n == 0 then return acc else return addTCO(n-1, acc+1) end end function main() local n = 1000000 print(addTCO(n, 0)) print(add(n)) end main()
実行結果です。
1000000 lua: a.lua:5: stack overflow stack traceback: a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' ... a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:5: in function 'add' a.lua:20: in function 'main' a.lua:23: in main chunk [C]: in ?
確かに、末尾再帰の方はスタックオーバーフローしていない。
『Programming in Lua』には、相互再帰の末尾呼び出しのサンプルが示されている(room1, room2, room3関数のサンプル)。相互末尾再帰の最適化方法が全くイメージ出来ない。記事には関数へのgotoと書いてあるけれど、具体的にどのようなコードになるのだろうか。