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

递归

循环迭代

核心代码

• 递归
  • TestStep.java

    public class TestStep {
    /**
     * 实现f(n):求n步台阶，一共有几种走法
     *
     * @param n
     * @return
     */
    public int f(int n) {
      if (n < 1) {
        throw new IllegalArgumentException(n + "不能小于1");
      }
      if (n == 1 || n == 2) {
        return n;
      }
      return f(n - 2) + f(n - 1);
    }
  }
  

  • TestStepTest.java

  public class TestStepTest {
      @Test
      public void test() {
          System.out.println(new TestStep().f(1));
          System.out.println(new TestStep().f(2));
          System.out.println(new TestStep().f(3));
          System.out.println(new TestStep().f(4));
          System.out.println(new TestStep().f(5));
      }
  
      @Test
      public void testCostTime() {
          long start = System.currentTimeMillis();
          System.out.println(new TestStep().f(40));//165580141
          long end = System.currentTimeMillis();
          System.out.println(end - start);//642 ms
      }
  
  }
  

• 迭代
  • TestStep2.java

  public class TestStep2 {
      /**
       * 实现f(n):求n步台阶，一共有几种走法
       *
       * @param n
       * @return
       */
      public int loop(int n) {
          if (n < 1) {
              throw new IllegalArgumentException(n + "不能小于1");
          }
          if (n == 1 || n == 2) {
              return n;
          }
  
          int one = 2;//初始化为走到第二级台阶的走法
          int two = 1;//初始化为走到第一级台阶的走法
          int sum = 0;
          for (int i = 3; i <= n; i++) {
              //最后跨2步+最后跨1步的走法
              sum = two + one;
              two = one;
              one = sum;
  
          }
          return sum;
      }
  }
  

  • TestStep2Test.java

  public class TestStep2Test {
      @Test
      public void test() {
          System.out.println(new TestStep2().loop(1));
          System.out.println(new TestStep2().loop(2));
          System.out.println(new TestStep2().loop(3));
          System.out.println(new TestStep2().loop(4));
          System.out.println(new TestStep2().loop(5));
  
      }
  
      @Test
      public void testCostTime() {
          long start = System.currentTimeMillis();
          System.out.println(new TestStep2().loop(40));//165580141
          long end = System.currentTimeMillis();
          System.out.println(end - start);//2 ms
      }
  
  }
  

小结

方法调用自身称为递归，利用变量的原值推出新值称为迭代。

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

源码地址

• 递归
• 迭代

彩蛋

• 1.通过debug观察递归的堆栈信息