编程题: 有n步台阶, 一次只能上 1步 或 2步, 共有多少种走法?
- 递归
- 循环迭代
递归:
package will01; import org.junit.Test; public class TestStep {
@Test
public void test(){
long start = System.currentTimeMillis();
System.out.println(f(30));
long end = System.currentTimeMillis();
System.out.println("time : "+ (end - start)); } //实现f(n):求 n步 台阶,一共有 几种 走法
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);
} }
循环迭代:
package will01; import org.junit.Test; public class TestStep2 { @Test
public void test(){
long start = System.currentTimeMillis();
System.out.println(loop(40));
long end = System.currentTimeMillis();
System.out.println("time : "+ (end - start)); // < 0ms } 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++){
//最后跨两步 + 最后跨一步 的走法
sum = two + one ;
two = one;
one = sum;
} return sum; } }
疑问: 递归的缺点: 递归浪费了空间,而且递归太深容易造成堆栈的溢出。不理解???
最大的不同: 迭代 花费的时间 比 递归 少很多。 所以迭代的效率会更高一点。
但是 迭代的代码的可读性 比 递归的 差。
参考视频: https://study.163.com/course/courseLearn.htm?courseId=1209482832#/learn/video?lessonId=1279646393&courseId=1209482832