Lua 正确的尾调用（proper tail call）

Lua支持“尾调用消除（tail-call elimination）”。
尾调用（tail call）：当一个函数调用是另一个函数的最后一个动作时，该调用才算是一条“尾调用”。例如，下面的代码就是一条“尾调用”：

function f (x) return g(x) end

也就是说，当f调用完g之后就再无其他事情可做了。因此在这种情况下，程序就不需要返回那个“尾调用”所在的函数了。所以在“尾调用”之后，程序也不需要保存任何关于该函数的栈（stack）信息了。当g返回时，执行控制权可以直接返回到调用f的那个点上。有一些语言实现（例如Lua解释器）可以得益于这个特点，使得在进行“尾调用”时不好非任何栈空间。将这种实现称为支持“尾调用消除”。
由于“尾调用”不会耗费栈空间，所以一个程序可以拥有无数嵌套的“尾调用”。例如，在第哦用以下函数时，传入任何数字作为参数都不会造成栈溢出：

function foo (n)
    if n > 0 then return foo(n-1) end
end

判断当前的调用是一条“尾调用”的准则：一个函数在调用完另一个函数之后，是否就无其他事情需要做了。
例如，下面的代码就不是一条“尾调用”：

function f (x) g(x) end

这个示例的问题在于，当调用完g后，f并不能立即返回，它还需要丢弃g返回的临时结果。类似的，以下所有调用也都不符合上述准则：

return g(x) + 1        -- 必须做一次加法
return x or g(x)    -- 必须调整为一个返回值
return (g(x))        -- 必须调整为一个返回值

在Lua中，只有“return <func>(<args>)”这样的调用形式才算是一条“尾调用”。Lua会在调用前对<func>及其参数求值，所以它们可以是任意复杂的表达式。举例来说，下买的呢调用就是一条“尾调用”：

return x[i].foo(x[j] + a*b , i + j)

[“尾调用” 迷宫游戏示例]
“尾调用”类似一条goto语句。在Lua中“尾调用”的已答应永久是编写“状态机（state machine）”。这种程序通常以一个函数来表示一个状态，改变状态就是goto（或调用）到另一个特定的函数。举一个简单的迷宫游戏的例子来说明这个问题。例如，一个迷宫有几间房间，每间房间中最多有东南西北4扇门。用户在每一步移动中都需要输入一个移动的方向。如果在某个方向上有门，那么用乎可以进入相应的房间；不然，程序就打印一条警告。游戏目标就是让用户从最初的房间走到最终的房间。
这个游戏就是一种典型的状态机，其中当前房间就是一个状态。可以将迷宫中的没见房间实现为一个函数，并使用“尾调用”来实现从一件房间移动到另一间房间。在以下代码中，实现一个具有4间房间的迷宫：

function room1 ()
    local move = io.read()
    if move == "sourth" then return room3()
    elseif move == "east" then return room2()
    else
        print("invalid move")
        return room1()  -- stay in the same room
    end
end

function room2()
    local move = io.read()
    if move == "sourth" then return room4()
    elseif move == "west" then return room1()
    else
        print("invalid move")
        return room2()
    end
end

function room3()
    local move = io.read()
    if move == "north" then return room1()
    elseif move == "east" then return room4()
    else
        print("invalid move")
        return room3()
    end
end

function room4()
    print("congratulations!")
end

通过调用出世房间来开始这个游戏：

room1()

若没有“尾调用消除”的话，每次用户的移动都会创建一个新的栈层（stack level），移动若干步之后就有可能会导致栈溢出。而“尾调用消除”则对用户已动的次数没有限制。这是因为每次移动实际上都只是完成一条goto语句到另一个函数，而非传统的函数调用。
对于这个简单的游戏而言，或许会觉得将程序设计为数据驱动的会更好玩一点，其中将房间和移动记录在一些table中。不过，如果游戏中的没见房间都有个字特殊的情况的话，采用这种状态机的设计会更为合适。