2016 - 2024

感恩一路有你

迭代和递归的实例 递归和迭代有什么区别?

浏览量:1231 时间:2021-03-13 17:08:01 作者:admin

递归和迭代有什么区别?

递归和迭代都是循环类型。简单地说,递归就是反复调用函数本身来实现循环。迭代是由函数中的某些代码实现的循环。迭代与普通循环的区别在于,循环代码中参与运算的变量也是保存结果的变量,当前保存的结果是下一次循环计算的初始值。在递归循环中,当满足终止条件时,循环将逐层返回。迭代使用计数器结束循环。当然,在许多情况下,各种循环是混合的,这取决于具体的需要。递归示例,例如,给定一个整数数组,使用半查询返回数组中指定值的索引,假设数组已排序。为了便于描述,假设所有的元素都是正数,数组的长度是2的整数倍。半查询是一种查询,它比遍历所有元素快得多。迭代的经典例子是实数的累加,例如计算从1到100的所有实数之和。

所有的递归程序或算法都能转化为迭代程序或算?

理论上是可以的,但是有些算法更简洁明了,有递归描述,虽然性能比迭代慢。目前,一些用递归转化为迭代的算法比较复杂,如典型的汉诺塔问题。虽然在线流程图例已通过迭代求解,但其正确性尚未得到研究者的证实。目前,递归仍然被广泛地用于实现它。

尾递归究竟是好是坏?

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

以n的阶乘为例:

正常递归:

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

尾部递归:

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

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

迭代和递归的实例 递归查询和迭代查询 递归算法经典实例

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