Lua中的尾调用与尾递归

尾调用

何为尾调用？

当一个函数是另一个函数的最后一个动作时，该调用就是一条尾调用！

e.g.

function testFuncA(arg)print(arg)
endfunction testFuncB()local str = "尾调用test"return testFuncA(str)  -- 函数testFuncB的最后一步操作是调用函数testFuncA，这就是一条尾调用
endtestFuncB()  -- 尾调用test

ps：

• 函数尾部有调用另一个函数，不一定是尾调用：

function testFuncA(arg)return arg
endfunction testFuncB(arg)return 1 + testFuncA(arg)  -- 不是尾调用，testFuncB的最后一步操作是执行算术运算符"+"
endprint(testFuncB(1))  -- 2function testFuncC(arg)return arg or testFuncA("test")  -- 不是尾调用，testFuncC的最后一步操作不一定是调用函数testFuncA
endprint(testFuncC(true))  -- true
print(testFuncC(false))  -- test

• 尾调用不一定出现在函数尾部，只要是最后一步操作即可：

function testFuncA(arg)print("testFuncA arg->", arg)
endfunction testFuncB(arg)print("testFuncB arg->", arg)
endfunction testFunc(arg)if arg > 0 thenreturn testFuncA(arg)  -- 是尾调用endreturn testFuncB(arg)  -- 也是尾调用
endtestFunc(0)  -- testFuncB arg->	0
testFunc(1)  -- testFuncA arg->	1

尾调用特性

lua 支持尾调用的特性"尾调用消除"：当在进行尾调用的时候不消耗任何栈空间，这种实现就称为尾调用消除。

函数调用会在内存形成一个"调用记录"，又称"调用帧"，保存调用位置和内部变量等信息。如果在函数 A 的内部调用函数 B，那么在 A 的调用记录上方，还会形成一个 B 的调用记录。等到 B 运行结束，将结果返回到 A，B 的调用记录才会消失。如果函数 B 内部还调用函数 C，那就还有一个 C 的调用记录栈，以此类推。所有的调用记录，就形成一个"调用栈"。

e.g.

function A()B()
endfunction B()C()
endfunction C()print(debug.traceback())print("this is func C")
endA()--[[
stack traceback:C:\Users\user\Desktop\transition\test.lua:25: in function 'C'C:\Users\user\Desktop\transition\test.lua:21: in function 'B'C:\Users\user\Desktop\transition\test.lua:17: in function 'A'C:\Users\user\Desktop\transition\test.lua:29: in main chunk[C]: ?
this is func C
]]

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项（只保留内层函数的调用记录），这将大大节省内存。

e.g.

function A()return B()
endfunction B()return C()
endfunction C()print(debug.traceback())print("this is func C")
endA()--[[
stack traceback:C:\Users\user\Desktop\transition\test.lua:10: in function (tail call): ?(tail call): ?C:\Users\user\Desktop\transition\test.lua:14: in main chunk[C]: ?
this is func C
]]

ps：

正是由于尾调用消除特性的存在，使得一个程序可以拥有无数嵌套的尾调用，而不会造成栈溢出。利用尾调用的特性，适合编写状态机！

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归e.g.

-- 递归阶乘运算
function factorial(n)if n == 1 thenprint(debug.traceback())return 1endreturn n * factorial(n - 1)
endprint(factorial(5))--[[
stack traceback:C:\Users\user\Desktop\transition\test.lua:4: in function 'factorial'C:\Users\user\Desktop\transition\test.lua:7: in function 'factorial'C:\Users\user\Desktop\transition\test.lua:7: in function 'factorial'C:\Users\user\Desktop\transition\test.lua:7: in function 'factorial'C:\Users\user\Desktop\transition\test.lua:7: in function 'factorial'C:\Users\user\Desktop\transition\test.lua:10: in main chunk[C]: ?
120
]]

递归非常耗费内存（空间复杂度O(n)），因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。

尾递归e.g.

-- 尾递归阶乘运算
function factorial(n, total)if n == 1 thenprint(debug.traceback())return totalendreturn factorial(n - 1, n * total)
endprint(factorial(5, 1))--[[
stack traceback:C:\Users\user\Desktop\transition\test.lua:4: in function (tail call): ?(tail call): ?(tail call): ?(tail call): ?C:\Users\user\Desktop\transition\test.lua:10: in main chunk[C]: ?
120
]]

尾递归由于只存在一个调用记录（空间复杂度O(1)），所以永远不会发生"栈溢出"错误。

ps：

在使用Lua进行开发的时候，能使用尾调用的时候尽量改写成尾调用，能使用尾递归的时候尽量改写成尾递归！能节省不少内存空间！

参考：

尾调用优化

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！