[Lua]尾调用消除（tail-callelimination）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

《Lua程序设计（第2版）》 6.3 正确的尾调用（proper tail call）

　　Lua是支持尾调用消除（tail-call elimination）的，如下面对函数g的调用就是尾调用。

1 function f(x) return g(x) end

　　尾调用之后，程序不需要保存任何关于函数f的栈(stack)信息，即不耗费任何栈空间。

　　尾调用方法可用于编写状态机（state machine），类似于goto到另一个函数，如果没有尾调用消除，每次调用都会创建一个新的栈层(stack level)，若干步之后有可能导致栈溢出。

　　注意，以下几种情况均不是尾调用：

1 function f(x)
2     g(x)
3 end
4 
5 return g(x) + 1
6 return x or g(x)
7 return (g(x))

　　举例，书中有个迷宫的例子，代码如下：

入口

room1

room2

room3

出口

room4

 1 function room1 ()
 2     local direction = io.read()
 3     if direction == "east" then
 4         room2()
 5     elseif direction == "south" then
 6         room3()
 7     else
 8         print("invalid direction!")
 9         room1()
10     end
11 end
12 
13 function room2 ()
14     local direction = io.read()
15     if direction == "west" then
16         return room1()
17     elseif direction == "south" then
18         return room4()
19     else
20         print("invalid direction!")
21         return room2()
22     end
23 end
24 
25 function room3 ()
26     local direction = io.read()
27     if direction == "north" then
28         return room1()
29     elseif direction == "east" then
30         return room4()
31     else
32         print("invalid direction!")
33         return room3()
34     end
35 
36 end
37 
38 function room4 ()
39     print("congratulations!")
40 end
41 
42 room1()

运行结果：

south
west
invalid direction!
east
congratulations!

我们写一个尾调用的简单循环：

 1 function room1()
 2     return room2()
 3 end
 4 
 5 function room2()
 6     print(111)
 7     return room1()
 8 end
 9 
10 room1()

运行结果：

111
111 -- 一直循环不会报错

不使用尾调用：

 1 function room1()
 2     room2()
 3 end
 4 
 5 function room2()
 6     print(111)
 7     room1()
 8 end
 9 
10 room1()

运行结果：

111
111 -- 循环几秒之后出现以下报错：

lua: stack overflow
stack traceback:
        [C]: in function 'print'
        6_propertailcall.lua:47: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        ...
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:48: in function 'room2'
        6_propertailcall.lua:43: in function 'room1'
        6_propertailcall.lua:51: in main chunk
        [C]: ?