第一季:5递归与迭代
题目
编程题:
有 n 步台阶,一次只能上 1 步或者 2 步,共有多少种走法?
1.递归
2.循环迭代
递归
斐波那契数列
package fbnq5;
import org.junit.Test;
public class TestStep {
@Test
public void test() {
long start=System.currentTimeMillis();
System.out.println(f(40));//165580141
long end=System.currentTimeMillis();
System.out.println(end-start);//335
}
//实现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 fbnq5;
import org.junit.Test;
public class TestStep {
@Test
public void test() {
long start=System.currentTimeMillis();
System.out.println(f(40));//165580141
long end=System.currentTimeMillis();
System.out.println(end-start);//335
}
//实现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);
}
}
小结
-
方法调用自身称为递归,利用变量的原值推出新值称为迭代。
-
递归
- 优点:大问题转为小问题,可以减少代码量,同时代码精简,可读性好;
- 缺点:递归调用浪费了空间,而且递归太深容易造成堆栈的溢出。
-
迭代
- 优点:代码运行效率好,因为时间复杂度为0(n),而且没有额外空间的开销;
- 缺点:代码不如递归简洁,可读性好