[教程源码] [Lua]使用尾递归解决栈溢出问题

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

--[[
这个是一个正确的尾递归例子,
与上面递归的区别在于返回值不一样,
尾递归的返回值没有额外的计算,
尾递归返回值唯一写法就是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