Python和Node.js支持尾递归吗?

什么是尾部递归?简单地说,返回的最后一件事是在不保存冗余局部变量的情况下调用函数。

[En]

What is tail recursion? To put it simply, the last thing that is returned is a call to a function without saving redundant local variables.

看一个简单的计算阶乘的例子(Lua代码):

改成尾递归的方式就是:

因为在使用尾递归时不需要保存局部变量,所以某些语言中的解析器会优化尾递归以减少堆栈空间。由于需要保存局部变量,普通的递归方法会占用越来越多的堆栈空间,最终导致堆栈溢出。

[En]

Because there is no need to save local variables when using tail recursion, parsers in some languages optimize tail recursion to reduce stack space. Due to the need to save local variables, the ordinary recursive method takes up more and more stack space, which eventually leads to stack overflow.

Lua是支持尾递归的,所以上面的尾递归的代码,是可以很好的工作的。

Python本身是不支持尾递归的(via),并且对递归次数有限制的,当递归次数超过1000次的时候,就会抛出”RuntimeError: maximum recursion depth exceeded”异常。
有人对此为Python的尾递归写了一个优化版本,让Python突破递归调用1000次的限制:Tail Call Optimization Decorator (Python recipe) ,或者你可以看看以下两篇文章:

以上的Python尾递归优化可以突破1000次的递归限制,但是却对于尾递归应有的优化完全没有。以下为我的测试代码:

测试环境是 Python2.7.1,计算100000的阶乘。执行recursion.py的时候,内存占用约为 100M,执行tail_recursion.py的时候,内存占用占到 1G的时候,还是没有执行完,我只好杀掉进程。

不过我确实想不明白为什么Python这里写成尾递归的方式会比会比普通方式占用多那么多内存呢?

我知道JavaScript是不支持尾递归的。ES4的时候曾经提过要加入尾递归的支持,不过后来被去掉了(via)。
周爱民的《Javascript语言精髓与编程实践》其中也提到:

  • “然而不幸的是。目前已知的javascript 的解释环境中并不支持这种特性(尾递归)。因此,我们在这里讨论函数室式时,可以说”能够通过函数递归来消灭循环语句”,但在不支持尾递归(及其优化技术)的javascript中,这种实现将以大量栈和内存消耗为代价”

Node.js是基于Google V8的,所以在Chrome的控制台测试了一下:

从结果看来,基本没戏了。但是还是在node.js写了代码验证一下。

以下为计算13000的阶乘时内存占用情况:

从结果来看,尾递归的方式占用的内存还要多。

下面再来看看计算13000的阶乘,循环1000次,然后计算平均每次的执行时间:

以下为执行结果:

阿门,在内存使用和执行效率方面,尾递归方式都比正常方式差。

[En]

Amen, both in terms of memory usage and execution efficiency, the way of tail recursion is worse than the normal way.

看来V8是对于尾递归的方式完全没有做优化了,对于Node.js异步调用到处是的情况下,没有对尾调用做优化的话,栈空间浪费很严重啊!不知道我这样认为对不对?忘记一点是”异步”的,异步回调栈是清空的了,不存在该问题。

Enjoy!

Original: https://www.cnblogs.com/QLeelulu/archive/2011/07/31/2122379.html
Author: Q.Lee.lulu
Title: Python和Node.js支持尾递归吗?

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/9813/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部