问题一

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

递归解法

设f(n)=x，表示有n个台阶时，有x中走法

  • n=1，一步 f(1)=1
  • n=2，一步一步 或者 直接两步 f(2)=2
  • n=3，
    • 先到达f(1)，然后f(1)直接跨2步。
    • 先到达f(2)，然后f(2)跨1步。
    • 即 f(3) = f(1)+f(2)，表示，到f(1)的走法+到f(2)的走法
  • n=4，
    • 先到达f(2)，然后从f(2)直接跨2步
    • 先到达f(3)，然后f(3)跨1步
    • 即 f(4) = f(2)+f(3)，表示到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)，表示到f(x-2)的走法+到f(x-1)的走法 ```java public class Recursion { public static void main(String[] args) { final long start = System.currentTimeMillis(); System.out.println(“共有走法 “ + fun(40) + “ 种”); final long end = System.currentTimeMillis(); System.out.println(“总共耗时” + (end - start) + “ms”); }

      private static int fun(int n) { if (n < 1) {

      1.    throw new IllegalArgumentException(n + "不能小于1");

      } if (n == 1 || n == 2) {

      1.    return n;

      } return fun(n - 2) + fun(n - 1); } }

// 结果 当n=40时 共有走法 165580141 种 总共耗时303ms

  1. <a name="FWCQb"></a>
  2. ### 循环迭代解法
  3. 设f(n)=x，表示有n个台阶时，有x中走法<br />令 one保存最后走一步的方法，two保存最后走两步的方法
  5. - n=1，一步 f(1)=1
  6. - n=2，一步一步 或者 直接两步 f(2)=2
  7. - n=3，
  8.    - 先到达f(1)，然后f(1)直接跨2步。 
  9.    - 先到达f(2)，然后f(2)跨1步。 
  10.    - 即 f(3) = f(1)+f(2)，表示，到f(1)的走法+到f(2)的走法 two=f(1)，one=f(2)
  11. - n=4，
  12.    - 先到达f(2)，然后从f(2)直接跨2步 
  13.    - 先到达f(3)，然后f(3)跨1步 
  14.    - 即 f(4) = f(2)+f(3)，表示到f(2)的走法+到f(3)的走法two=f(2)；one=f(3)
  15. - ........
  16. - n=x
  17.    - 先到达f(x-2)，然后从f(x-2)直接跨2步 
  18.    - 先到达f(x-1)，然后f(x-1)直接跨1步 
  19.    - 即f(x)=f(x-2)+f(x-1)，表示到f(x-2)的走法+到f(x-1)的走法two=f(x-2)，one=f(x-1)
  20. ```java
  21. public class LoopIterate {
  23.     public static void main(String[] args) {
  24.         final long start = System.currentTimeMillis();
  25.         System.out.println("共有走法 " + loop(40) + " 种");
  26.         final long end = System.currentTimeMillis();
  27.         System.out.println("总共耗时" + (end - start) + "ms");
  28.     }
  30.     private static int loop(int n) {
  31.         if (n < 1) {
  32.             throw new IllegalArgumentException(n + "不能小于1");
  33.         }
  34.         if (n == 1 || n == 2) {
  35.             return n;
  36.         }
  37.         // 最后走一步的方法是f(2)，其有2种走法 即 初始化为走到第二级台阶的走法
  38.         int one = 2;
  39.         // 最后走两步的方法是f(1)，其有1种走法 即 初始化为走到第一级台阶的走法
  40.         int two = 1;
  41.         // 一共的走法
  42.         int sum = 0;
  45.         for (int i = 3; i <= n; i++) {
  46.             // 最后走1步 + 最后走2步的走法 ， 记录下到i个台阶时的总走法
  47.             sum = one + two;
  48.             // 到 i+1个台阶时，需要用到的还需要走两步的走法，就是i个台阶时的还需要走一步的走法
  49.             two = one;
  50.             // 到 i+1个台阶时，需要用到的还需要走一步的走法，就是i个台阶时的总走法
  51.             one = sum;
  52.         }
  53.         return sum;
  54.     }
  55. }
  57. 结果
  58. 共有走法 165580141 种
  59. 总共耗时0ms

总结

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