Lua は末尾再帰最適化を行う。ってマニュアルに書いてあるんだけど、ホントカヨーって思って調べてみた。

function pow(x, n)
	if n == 1 then return x end

	return x * pow(x, n-1)
end

function pow_tail(x, n)
	local function pow_f (c, r)
		if c == 0 then
			return r
		else
			return pow_f(c - 1, x * r)
		end
	end

	return pow_f(n, 1)
end

-- print(     pow(2, 1000000000))
-- print(pow_tail(2, 1000000000))

pow は普通の再帰で pow_tail が末尾再帰ばーじょん
pow のほうを実行すると

lua: math1.lua:7: stack overflow
stack traceback:
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        ...
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:22: in main chunk
        [C]: ?

でエラー

pow_tail を実行中に途中で C-c で止めると

^Clua: interrupted!
stack traceback:
        math1.lua:15: in function <math1.lua:11>
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        ...
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        math1.lua:23: in main chunk
        [C]: ?

と tail call でスタック情報が消えて ? になってることがわかる。