(。・∀・)ノ゙嗨我可以实现你一个愿望~~
┗|`O′|┛ 嗷~~我想再来三个!
/_ \给爷爪巴……
神龙许愿的机制
在鸟山明《龙珠》的设定下,集齐七颗龙珠可以召唤一次神龙,神龙会帮你实现一个愿望。那如果我贪心地向神龙多要几个愿望呢?不知道龙珠里有没有这样的场景,不过结果大概率跟引言差不多,我猜。
基于一个设定,神龙要帮你 complete 一个愿望才会离开,假设我许了贪心的愿望,那么在确认第 n+1 代愿望已经被实现后,第 n 代的许愿才算达成(注意前文的 complete 设定)。那么假如我不断地贪心,愿望的 object 就会无限制增加,最终 out of memory。所以为了维护神龙系统的健壮性,许这种愿望的人是要被 ban 掉的!
那如果神龙系统是用尾递归实现的呢?
什么是尾递归?
function story() {
从前有座山,山上有座庙,庙里有个老和尚,
一天老和尚对小和尚讲故事:story()
// 尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。
}function story() {
从前有座山,山上有座庙,庙里有个老和尚,
一天老和尚对小和尚讲故事:story(),
小和尚听了,找了块豆腐撞死了
// 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境以供处理返回值。
}作者:匿名用户
链接:https://www.zhihu.com/question/20761771/answer/23254340
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
尾递归有什么好处?
节省内存空间,继续看知乎样例:
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)当调用recsum(5),Python调试器中发生如下状况:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
作者:匿名用户
链接:https://www.zhihu.com/question/20761771/answer/19996299
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
而当改成尾递归写法时,如下
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)理论上类似上面:
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15作者:匿名用户
链接:https://www.zhihu.com/question/20761771/answer/19996299
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
博客学习
Tail calls, @tailrec and trampolines
尾递归 in Scala
Scala 里面有个显式的注解 @tailrec
,一开始不是很理解:如果我不加这个注解,那我就不是尾递归了吗?这合理吗?
其实不是的。加上这个注解之后,编译器会进行特殊优化。而如果一个方法本身不是尾递归却也加了这个注解,那编译器会报错。
所以我觉得更大的用处是可以检验自己写的方法是不是一个真正的尾递归。嗯,very cool!