紫猫学院社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 933|回复: 2

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

[复制链接]

847

主题

2413

帖子

2433

积分

院长

Rank: 9Rank: 9Rank: 9

猫粮
4485
QQ
发表于 2018-9-28 22:25:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

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

回复

使用道具 举报

4

主题

9

帖子

9

积分

超级版主

Rank: 8Rank: 8

猫粮
47
发表于 2020-12-24 16:16:18 | 显示全部楼层
看不懂,哈哈∑(っ°Д°;)っ
回复

使用道具 举报

847

主题

2413

帖子

2433

积分

院长

Rank: 9Rank: 9Rank: 9

猫粮
4485
QQ
 楼主| 发表于 2020-12-24 20:36:00 | 显示全部楼层

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

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|紫猫编程学院  

GMT+8, 2021-1-21 20:25

Powered by Discuz! X3.4

Copyright © 2012-2020 紫猫编程学院

快速回复 返回顶部 返回列表