循环(loop), 递归(recursion), 遍历(traversal), 迭代(iterate)，及相同点、区别

作者：马育民 • • 阅读：10060

循环(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

吉ICP备15003043号