2016 - 2024

感恩一路有你

为什么禁止尾递归 尾递归究竟是好是坏?

浏览量:2415 时间:2021-03-10 19:14:03 作者:admin

尾递归究竟是好是坏?

如果递归级别太多,则会出现堆栈溢出异常,因为每次调用都会生成一个新的堆栈帧,并使用此堆栈帧保留当前函数的状态值。如果不需要保存状态值,则可以重用堆栈帧而不会导致堆栈溢出。

以n的阶乘为例:

正常递归:

如果n=3,则每一步都需要保留n值和下一个函数的返回值,因此每次调用都需要创建一个新的堆栈帧

尾部递归:

如果n=3,则每次调用都可以重用堆栈帧,因为不需要保存状态值。

因此,当递归在当前堆栈帧执行后完成时,它不需要保留当前堆栈帧,但根据当前堆栈帧的结果,它可以在进入下一个堆栈帧时优化为尾部递归。通常,尾部递归需要满足递归调用是函数体中最后执行的语句。例如,在factorial示例中,要执行的最后一条语句是直接调用factorial(n-1,n*result),而不是表达式n*factorial(n-1)。如果是表达式,则需要堆栈帧来保留N和阶乘(N-1)的结果。

编译器的任务是什么尾递归优化?

当编译器检测到函数调用是尾部递归时,它将覆盖当前活动记录,而不是在堆栈中创建新的活动记录。编译器可以这样做,因为递归调用是当前活动周期中要执行的最后一条语句,因此当调用返回时,堆栈帧中没有其他操作,因此不需要保存堆栈帧。通过覆盖当前堆栈帧而不是在其上添加新的堆栈帧,大大减少了使用的堆栈空间,从而提高了实际操作效率。虽然编译器可以优化尾部递归引起的堆栈溢出,但是在编程中我们应该尽量避免尾部递归,因为所有尾部递归都可以被简单的goto循环所代替。

如何在Python中实现尾递归优化?

Python不会优化尾部递归。默认情况下,递归的最大深度约为1000。当然,可以修改底层的默认最大深度。但是我们可以使用Python内置的yield将尾部递归函数转换为生成器。我只需要连续执行它的下一个方法。从本质上讲,递归和循环是一样的,但递归是一种函数调用,与循环相比,它有很多开销:参数堆栈压缩;当前指令执行指针PC跳转导致CPU指令缓存失败等。这些因素导致递归比循环慢。C语言不支持尾部递归优化。对于支持尾部递归优化的语言,根据尾部递归的编写方法(对递归函数的调用是函数的最后一行),该语言将递归优化为循环指令,因此两者没有区别。

为什么禁止尾递归 js尾递归优化 python

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。