剑指Offer-循环和递归-(1)
知识点:递归
题目:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
如果我们需要重复地多次计算相同的问题,则通常可以选择用递归或者循环两种不同的方法;递归是在一个函数的内部调用这个函数本身;而循环则是通过设置计算的初始值以及终止条件,在一个范围内重复运算,比如1+2+。。+n,我们可以用递归或者循环两种方式求出结果
通常递归的代码会比较简洁,但是函数调用是有时间和空间消耗的:每一次函数调用,都需要在内存中分配空间以保存参数,返回地址及临时变量,而且往往栈的压入数据和弹出数据都需要时间。递归函数的效率不如循环;另外,递归中有可能有很多的计算是重复的,从而对性能带来很大的负面影响
**这是递归的写法**
public class Test0 {
public static void main(String[] args) {
System.out.println(add(100));
}
public static int add(int n) {
if(n>=0) {
int sum = add(n-1)+n;
return sum;
}
return 0;
}
}
这是循环的写法
public class Test0 {
public static void main(String[] args) {
System.out.println(add(100));
}
public static int add(int n) {
int sum=0;
for(int i=0;i<=n;i++) {
sum+=i;
}
return sum;
}
}
我们的目标:避免重复
直接用递归之所以慢,是因为重复的计算太多,我们可以把已经得到的数列中间项保存起来,在下次需要计算的时候我们先查一下,如果前面已经计算过了就不需要重复计算了。
更简单的方法就是从下往上计算,首先根据f(0)和f(1)计算f(2),再根据f(1)和f(2)计算f(3),这种方法的思路算法复杂度是O(n)。
public class Test0 {
public static void main(String[] args) {
System.out.println(Fibonacci(20));
}
public static int Fibonacci(int n){
int a=0;
int b=1;
int result = 0;
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
for(int i= 2;i<=n;i++){
result = a+b;
a=b;//记录前面的数字
b=result;//记录后边的数字
}
}
return result;
}
}