[Lua]使用尾递归解决栈溢出问题

紫猫

在使用递归函数的时候, 很容易会遇到栈溢出情况, 所以需要使用尾递归来代替, 下面举两个例子说明两者区别.

[Lua] 纯文本查看 复制代码

--[[
这个是很常见的递归计算阶乘函数,
如果数字过大, 非常容易出现栈溢出,
因为函数的返回值中有n*这个计算,
导致每一次递归展开的时候,
都要保留上一次调用结果,
直到所有递归展开结束后,
才回收到初次调用返回结果.
如果保留的太多了, 就会栈溢出.
--]]
function foo(n)
    if n == 1 then return 1 end
    return n * foo(n - 1)
end

[Lua] 纯文本查看 复制代码

--[[
这个是一个正确的尾递归例子,
与上面递归的区别在于返回值不一样,
尾递归的返回值没有额外的计算,
尾递归返回值唯一写法就是return 函数名(参数列表),
注意, 不能做除了调用函数外的任何运算,
这样处理的好处是每次调用不需要保存上一次结果,
因为上次结果已经被保存到参数r里面了.
那么Lua在处理的时候, 就会直接消除上一次的栈空间,
这个函数永远不会发生栈溢出问题.
--]]
function foo(n, r)
    r = r or 1
    if n == 1 then return r end
    return foo(n-1, n * r)
end

FishBOSS

看不懂，哈哈∑(っ°Д°;)っ

紫猫

FishBOSS 发表于 2020-12-24 16:16
看不懂，哈哈

简单的说，栈溢出是因为代码消耗完了内存，导致内存不够使用了。

递归的时候，未被执行的代码会被保存到内存中，而深层递归需要保存更多未被执行的代码，所以需要更多的内存，而如果程序内存不足，就会出现栈溢出的问题。就像上面代码中的 n* 这部分内容，每次执行递归展开都要保存一次变量n的值和乘法运算，直到最后一次执行后，才慢慢收回。

但是尾递归就不存在这个问题，因为执行尾递归的时候，不存在未被执行的代码，那么就不需要多余的内存来保存这些代码，所以永远不会出现栈溢出问题。尾递归最后一句就是直接return调用函数，不存在什么n*之类需要保存的东西。