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と書いてあるけれど、具体的にどのようなコードになるのだろうか。