深究递归与迭代的区别、联系、优缺点与实例的对比
1 .概念辨析
递归的基本概念:程序调用自身的编程技巧称为递归,是函数调用自身。
一种函数在其定义中直接或间接调用自身的方法。 它通常可以通过将大的复杂问题转换为与原始问题相似的小规模问题来解决,大大减少代码量。 递归的能力在于用有限的语句定义对象的无限集合。
使用递归时需要注意的点是两点:
1 )递归是指在过程或函数中调用自己。
2 )使用递归时,需要明确的递归终止条件,称为递归出口。
递归可分为两个阶段:
1 )渐进:将复杂问题的解决推向比原问题简单一点的解决
2 )得到返回:的最简单情况后,逐步返回,依次得到复杂的解。
利用递归可以解决背包问题、汉诺威问题、……等很多问题。
斐波那契数列为:0、1、1、2、3、5 .
递归引起一系列函数调用,可能存在一系列重复计算,因此递归算法的执行效率相对较低。
迭代:利用变量的原始值估计变量的新值。如果递归是自己调用自己,迭代就是a不断调用b。
2 .辩证地看待递归和迭代
递归简单地说,就是APP应用程序本身调用自身,以查询和访问分层数据结构。 递归使用可以使代码更简洁、更清晰、更容易阅读。 但是,递归需要系统堆栈,即使初学者不一定如此,空间消耗也比非递归代码多得多。 此外,递归深度过大可能会导致系统资源不足。
容易认为如果不用递归就不用递归,递归可以用反复代替。
确实,理论上递归和迭代在时间复杂度方面是等效的(不考虑函数调用开销和函数调用堆栈开销),但实际上递归效率确实比迭代低。 这样,既然递归没有任何优点,就没有必要使用递归。 递归的存在有什么意义呢?
万物的存在需要时间的检验,递归没有埋藏在历史中,即有存在的理由。 理论上,所有递归函数都可以转换为迭代函数,反之亦然,但成本通常很高。 但是,从算法结构来说,递归声明的结构不一定总是能够转换成迭代结构。 之所以这么说,是因为结构的引申本身是递归的概念,用反复的方法在设计初期根本无法实现。 这和动态多态性的东西不一定总是能用静态多态性的方法实现是一样的。 因此,在结构设计中多采用递归方式而不是迭代方式。 典型的例子类似于链表,使用递归定义及其简单性,但对内存定义(数组方式)的定义和调用处理的描述很模糊,特别是出现循环链、图、网格等问题时,使用迭代方式从描述到实现都是不现实的因此,在实践中,所有的迭代都可以转换为递归,但是递归不一定可以转换为迭代。
使用递归算法的必要前提是只有在预期一个收敛时才能使用递归算法。 否则,不能使用递归算法。
递归对程序员来说很方便,对机器很难有帮助,但是递归可以通过数学公式很容易地转换为程序。 其优点是容易理解,容易编程。 但是递归是通过堆栈机制实现的,每次加深层次时都会占用堆栈数据空间。 一些具有较深嵌套层数的算法无法递归,导致空间内存崩溃。 递归还带来了大量的函数调用,这也有很多额外的时间开销。 所以深度大的话时空性就会变差。
虽然迭代效率高,但执行时间随循环数的增加而增加,没有额外的开销,也没有空间上的增加,但是存在难以理解,难以制作复杂的问题的缺点。
因此,“无递归、无递归、递归可以用迭代代替”的理解,还是要辩证看待,不能一击而死。
1、2部分摘自网络,稍加改动,向原作者致敬!
3 .个人总结
定义
好处
缺点
递归
程序调用自身的编程技巧称为递归
1 )大问题成为小问题,可以大幅减少代码量
2 )用有限的语句定义对象的无限集合。
3 )代码更简洁明了,阅读方便
1 )递归调用函数,浪费空间
2 )递归太深容易引起堆栈溢出
迭代次数
利用变量的原始值估计变量的新值,迭代是指a不断调用b。
1 )迭代效率高,随着周期数的增加,执行时间增加;
2 )无额外开销,空间无增长,
1 )难以理解
2 )代码不像递归那么简单
3 )制作复杂的问题很难。
两者的关系
1 )递归一定有迭代,但迭代不一定有递归,大部分可以相互变换。
2 )可以迭代的是不使用递归,递归调用函数,浪费空间。 另外,递归太深容易引起堆栈溢出。 /*相对地(/
以下是示例。
#包含
用户名称空间;
//迭代实现斐波那契数列
longfab_iteration(intindex ) )。
{
if (索引==1| |索引==2) () ) ) ) ) ) ) ) ) ) )。
{
返回1;
}
else
{
longf1=1L;
p>long f2 = 1L;
long f3 = 0;
for(int i = 0; i
{
f3 = f1 + f2; //利用变量的原值推算出变量的一个新值
f1 = f2;
f2 = f3;
}
return f3;
}
}
//递归实现斐波那契数列
long fab_recursion(int index)
{
if(index == 1 || index == 2)
{
return 1;
}
else
{
return fab_recursion(index-1)+fab_recursion(index-2); //递归求值
}
}
int main(int argc, char* argv[])
{
cout <
cout <
return 0;
}