循环(loop), 递归(recursion), 遍历(traversal), 迭代(iterate)，及相同点、区别 作者：马育民 • 2024-12-30 09:48 • 阅读：10013 # 循环(loop) 在满足条件的情况下，重复执行同一段代码 ### 类比 - 很多人玩游戏，也是在一直重复，如：玩王者荣耀一直练一个英雄，同一个出装套路 - 普通人的一天，差不多都是在重复前一天的内容，也就是循环： 1. 吃饭 2. 工作/学习 3. 娱乐 4. 睡觉 # 迭代(iterate) 按照某种顺序访问 **线性结构** 中的每一项 线性结构：一般指集合，列表，数组等。 # 遍历(traversal) 按照某种规则访问 **非线性结构** 中的每一项 强调 **非线性结构**，如：树、图 # 递归(recursion) **递归**：指重复调用函数自身 如：在函数 `test` 内，又调用 `test` 自己 ``` void test(){ System.out.println(1); // 方法递归，自己调用自己 test(); } ``` ### 递归的分类 递归分为两种： - 直接递归：称为方法自身调用自己。 - 间接递归：方法之间调用，如：A方法调用B方法，B方法调用C方法，C方法调用A方法。 ### 递归求和 ``` int add( int i){ /* num为1时,方法返回1, 相当于是方法的出口,num总有是1的情况 */ if( i == 1){ return 1; } /* num不为1时,方法返回 num +(num-1)的累和 递归调用getSum方法 */ return i + add(i-1); } ``` ### 限制 递归有限制，受开发语言中，工作栈大小的限制，如：Java最多能执行1万多次 ### 注意事项 - 递归一定要有 **条件限制**，保证递归能够 **停止下来**，否则会发生栈内存溢出。 - 在递归中虽然有限定条件，但是递归次数不能太多。否则也会发生栈内存溢出。 ### 应用场景 一个大型复杂的问题，层层转化为一个 **与原问题相似，但规模较小 的问题** 来求解 **关键：**小问题须与原始问题为同样的操作，且更为简单。如：斐波那契数列等 如：**四层及以上的嵌套循环**，代码就变得非常难看，可读性很差，此时应该用递归 ### 与循环比较 ##### 循环的优点 运行效率高（不需要函数参数入栈和出栈）； 对存储空间占用比递归少，不需要系统维护工作栈； 便于调试。 ##### 循环的缺点 **三层嵌套循环** 的代码还能接受，**四层及以上的嵌套循环**，代码就变得非常难看，可读性很差。 而且有的问题非常适合用递归，用循环实现会非常困难。 ##### 递归的优点 多层嵌套时，代码清晰简洁，易于理解，可读性强。 ##### 递归的缺点 运行效率低（函数调用需要参数入 栈和出栈）； 对存储空间的占用比循环多，因此受到问题规模和线程空间大小的限制，如果栈溢出，将导致系统崩溃； 不便于调试。 # 相同点 大部分的递归、遍历、迭代、都是 **循环** # 区别 - 循环(loop) - 最基础的概念, 所有重复的行为 - 递归(recursion) - 在函数内调用自身, 将复杂情况逐步转化成基本情况 - 迭代(iterate) - 按顺序访问 **线性结构** 中的每一项 - 遍历(traversal) - 按规则访问 **非线性结构** 中的每一项 参考： https://blog.csdn.net/lvxiangan/article/details/78622553 https://www.cnblogs.com/feichengwulai/articles/3642107.html https://blog.csdn.net/uuuutaossienuuuu/article/details/50732185 原文出处：https://malaoshi.top/show_1GWJVFDa9uG.html