引出问题：
递归分析：
递归实现代码：
1 package 递归与迭代; 2 3 import org.junit.jupiter.api.Test; 4 5 /** 6 * @author zsh 7 * @company wlgzs 8 * @create 2019-03-27 15:58 9 * @Describe 递归实现 10 * 有n阶台阶，1次只能上一步或者2步，有多少种走法 11 * 递归 12 * 迭代 13 */ 14 public class TestStep { 15 @Test 16 public void test() { 17 long start = System.currentTimeMillis(); 18 System.out.println(f(40)); //165580141 19 long end = System.currentTimeMillis(); 20 System.out.println(end - start); //640ms 21 } 22 23 //递归实现f(n)：求n步台阶，一共有几种走法 24 public int f(int n) { 25 if (n < 1) { 26 throw new IllegalArgumentException(n + "不能小于1"); 27 } 28 if (n == 1 || n == 2) { 29 return n; 30 } 31 return f(n - 1) + f(n - 2); 32 } 33 34 }
运行结果：
迭代分析：
迭代代码：
1 package 递归与迭代; 2 3 import org.junit.jupiter.api.Test; 4 5 /** 6 * @author zsh 7 * @company wlgzs 8 * @create 2019-03-27 16:16 9 * @Describe 迭代实现 10 * 有n阶台阶，1次只能上一步或者2步，有多少种走法 11 * 递归 12 * 迭代 13 */ 14 public class TestStep2 { 15 16 @Test 17 public void test() { 18 long start = System.currentTimeMillis(); 19 System.out.println(loop(40)); //165580141 20 long end = System.currentTimeMillis(); 21 System.out.println(end - start); //<1ms 22 } 23 24 public int loop(int n) { 25 if (n < 1) { 26 throw new IllegalArgumentException(n + "不能小于1"); 27 } 28 if (n == 1 || n == 2) { 29 return n; 30 } 31 int one = 2; //走到第二级台阶的初始化值 32 int two = 1; //走到第一级台阶的初始化值 33 int sum = 0; 34 35 //最后跨两步+最后跨一步的走法 36 for (int i = 3; i <= n; i++) { 37 sum = two + one; 38 two = one; 39 one = sum; 40 } 41 return sum; 42 } 43 }
运行结果：
小结：
