5.1 题目

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

5.2 递归

  • n = 1
    • 一步
    • f(1) = 1
  • n = 2
    • 一步一步
    • 直接 2 步
    • f(2) = 2
  • n = 3
    • 先到达 f(1)，然后从 f(1) 直接跨 2 步
    • 先到达 f(2)，然后从 f(2) 跨 1 步
    • f(3) = f(1) + f(2)
  • n = 4
    • 先到达 f(2)，然后从 f(2) 直接跨 2 步
    • 先到达 f(3)，然后从 f(3) 跨 1 步
    • f(4) = f(2) + f(3)
  • ……
  • n = x
    • 先到达 f(x-2)，然后从 f(x-2) 直接跨 2 步
    • 先到达 f(x-1)，然后从 f(x-1) 跨 1 步
    • f(x) = f(x-2) + f(x-1) ```java package s01.e05;

public class TestStep {

  1. public int f(int n) {
  2.     if (n < 1) {
  3.         throw new IllegalArgumentException(n + "不能小于 1");
  4.     }
  5.     if (n == 1 || n == 2) {
  6.         return n;
  7.     }
  8.     return f(n - 2) + f(n - 1);
  9. }

}

  1. <a name="WDwIW"></a>
  2. # 5.3 循环迭代
  4. - n = 1
  5.    - 一步
  6.    - f(1) = 1
  7. - n = 2
  8.    - 一步一步
  9.    - 直接 2 步
  10.    - f(2) = 2
  11. - n = 3
  12.    - 先到达 f(1)，然后从 f(1) 直接跨 2 步
  13.    - 先到达 f(2)，然后从 f(2) 跨 1 步
  14.    - one 保存最后走一步
  15.    - two 保存最后走两步
  16.    - f(3) = two + one
  17.    - f(3) = f(1) + f(2)
  18.    - two = f(1)
  19.    - one = f(2)
  20. - n = 4
  21.    - 先到达 f(2)，然后从 f(2) 直接跨 2 步
  22.    - 先到达 f(3)，然后从 f(3) 跨 1 步
  23.    - f(4) = two + one
  24.    - f(4) = f(2) + f(3)
  25.    - two = f(2)
  26.    - one = f(3)
  27. - ......
  28. - n = x
  29.    - 先到达 f(x-2)，然后从 f(x-2) 直接跨 2 步
  30.    - 先到达 f(x-1)，然后从 f(x-1) 跨 1 步
  31.    - f(x) = two + one
  32.    - f(x) = f(x-2) + f(x-1)
  33.    - two = f(x-2)
  34.    - one = f(x-1)
  35. ```java
  36. package s01.e05;
  38. public class TestStep2 {
  40.     public int loop(int n) {
  41.         if (n < 1) {
  42.             throw new IllegalArgumentException(n + "不能小于 1");
  43.         }
  44.         if (n == 1 || n == 2) {
  45.             return n;
  46.         }
  48.         int one = 2; // 初始化为走到第二级台阶的走法
  49.         int two = 1; // 初始化为走到第一级台阶的走法
  50.         int sum = 0;
  52.         for (int i = 3; i < n; i++) {
  53.             // 最后跨 2 步 + 最后跨 1 步的走法
  54.             sum = two + one;
  55.             two = one;
  56.             one = sum;
  57.         }
  59.         return sum;
  60.     }
  61. }

5.4 小结

  • 方法调用自身称为递归，利用变量的原值推出新值称为迭代。
  • 递归
    • 优点：大问题转化为小问题，可以减少代码量，同时代码精简，可读性好
    • 缺点：递归调用浪费了空间，而且递归太深容易造成堆栈的溢出
  • 迭代
    • 优点：代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销
    • 缺点：代码不如递归简洁，可读性好