关于java:还在用递归试试迭代吧

10次阅读

共计 2032 个字符，预计需要花费 6 分钟才能阅读完成。

递归（recursion）

递归常被用来形容以自类似办法反复事物的过程，在数学和计算机科学中，指的是在函数定义中应用函数本身的办法。（A 调用 A）

迭代（iteration）

反复反馈过程的流动，每一次迭代的后果会作为下一次迭代的初始值。（A 反复调用 B）

有 n 步台阶，一次只能上 1 步或 2 步，共有多少种走法？

n=1 -> 一步 ->f(1)=1
n=2 ->（1）一步一步走（2）间接走 2 步 ->f(2)=2
n=3 ->（1）先达到第一级台阶（f(1)），而后间接跨两步
```
（2）先达到第二级台阶（f(2)）->f(3) = f(1) + f(2)
```
n=4 ->（1）先达到 f(2)，而后间接跨两步
（2）先达到第二级台阶 f(3)，而后间接跨一步 ->f(4) = f(2) + f(3)
···
n=x（1）先达到 f(x-2)，而后间接跨两步
（2）先达到第二级台阶 f(x-1)，而后间接跨一步 ->f(x) = f(x-2) + f(x-1)

循环迭代思路
n=1 -> 一步 ->f(1)=1
n=2 ->（1）一步一步走（2）间接走 2 步 ->f(2)=2
n=3 ->（1）先达到第一级台阶（f(1)），而后间接跨两步
```
（2）先达到第二级台阶（f(2)）->f(3) = f(1) + f(2)
```
n=4 ->（1）先达到 f(2)，而后间接跨两步
（2）先达到第二级台阶 f(3)，而后间接跨一步 ->f(4) = f(2) + f(3)
···
n=x（1）先达到 f(x-2)，而后间接跨两步
（2）先达到第二级台阶 f(x-1)，而后间接跨一步 ->f(x) = f(x-2) + f(x-1)

从下面能看出不论有多少台阶，都要走到最初的 n - 1 或 n - 2 台阶的这两种状况，所以咱们能够用两个长期变量 one=（f(n)-1）、two=（f(n)-2）保留这两个状况！

递归

循环迭代

public class Recursion {public static void main(String[] args) {long start = System.currentTimeMillis();
      System.out.println(f(42));
      long end = System.currentTimeMillis();
      System.out.printf("耗时毫秒为：%d", end - start);
  }

  /**
   * 有 n 步台阶，一次只能上 1 步或 2 步，共有多少种走法的递归代码实现
   * 性能损耗比较严重，特地是数据量大的时候，还会有可能造成栈溢出
   *
   * @param n 待计算的值
   * @return 计算结果
   */
  public static int f(int n) {if (n == 1 || n == 2) {return n;}
      return f(n - 2) + f(n - 1);
  }
}

public class LoopIteration {public static void main(String[] args) {long start = System.currentTimeMillis();
        System.out.println(loopIteration(42));
        long end = System.currentTimeMillis();
        System.out.printf("耗时毫秒为：%d", end - start);
    }

    /**
     * 循环迭代解决 有 n 步台阶，一次只能上 1 步或 2 步，共有多少种走法问题
     *
     * @param n 待计算的值（台阶数）* @return 后果（多少种走法）*/
    public static int loopIteration(int n) {if (n < 1) {throw new IllegalArgumentException(n + "不能小于 1");
        }
        if (n == 1 || n == 2) {return n;}
        // 当 n =3，one=f(3-1)=f(2)=2,two=f(3-2)=f(1)=1
        int one = 2; // 初始化走到最初须要走一步的走法
        int two = 1; // 初始化走到最初须要走两步的走法
        // 总步数
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = one + two;
            // 当 i = 4 时，此时 two=f(4-2)=f(2)=2，所以就是上一次的 one
            two = one;
            // 当 i = 4 时，one=f(4-1)=f(3)=3，所以就是上一次的 sum
            one = sum;
        }
        return sum;
    }
  }