【数据结构必备基本知识】递归与迭代的联系、区别与优缺点对比详解 |
您所在的位置:网站首页 › 简述求职信和简历的联系和区别 › 【数据结构必备基本知识】递归与迭代的联系、区别与优缺点对比详解 |
在后续的数据结构操作中,可能我们经常会用到递归或者是迭代,这会大大降低我们的代码量,并且能够解决一些其他方法很难解决的问题。以上一篇二叉树的遍历为例,通过递归算法,只用几行就可以遍历整个二叉树,递归的作用可想而知。 那么,什么是递归,什么是迭代,他们二者之间有什么联系,有什么区别,各自的优缺点是什么呢?接下来给大家详细讲解一下。 一、递归( recursion) 1、定义首先,递归是一种计算机算法,它是程序调用自身的编程技巧,在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。 2、必要条件1. 子问题须与原始问题为同样的事,且更为简单; 2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。 3、优点1.可以将大问题转化为小问题,减少代码量。 2.可以去掉不断重复的代码,使代码精简,提升可读性。 4、缺点递归调用浪费空间,递归太深还容易造成堆栈的溢出。 5、代码示例 //先序遍历 void PreOrderBiTree(BiTree BT) { if (BT) { VisitBiTree(BT); PreOrderBiTree(BT->lChild); PreOrderBiTree(BT->rChild); } }二、迭代(iteration) 1、定义 迭代是重复反馈过程的活动,其目的是为了逼近或求得所需目标或结果。 每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤,从前面的量依次求出后面的量的过程。 例如利用迭代法*求某一数学问题的解。对计算机特定程序中需要反复执行的子程序*(一组指令),进行一次重复,即重复执行程序中的循环,直到满足某条件为止,亦称为迭代。 2、必要条件1. 问题可以转化为一个解决方案的重复操作,某次操作的输出是下次操作的输入; 3、优点1.可以将重复问题转化为单一问题重复操作,减少代码量。 2.代码运行效率高,时间只因循环次数增加而增加,但是没有额外的空间开销; 4、缺点代码不如递归简洁。 5、代码示例 #include using namespace std; //求根号2的近似值 void main() { float i = 1; float j = 2; float avg = (j + i) / 2; while ((avg*avg - 2>0.000001)|| (2 - avg*avg>0.000001)) { if (avg*avg > 2) { j = avg; } else i = avg; avg = (j + i) / 2; } cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |