还在用递归，试试迭代吧 java

递归&迭代递归（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; } }

小结