递归简单来说就是自己调用自己，
递归构造包括两个部分：
1.定义递归头：什么时候需要调用自身方法，如果没有头，将陷入死循环
2.递归体：调用自身方法干什么
递归是自己调用自己的方法，用条件来判断调用什么时候停止！
斐波那契数列数列的递归实现： F(n)=F(n-1)+F(n-2)
package test;
public class Test {
public static long fibonacci(int n) {
if(n==0||n==1) return 1;
else {
return fibonacci(n-1)+fibonacci(n-2);
}
}
public static void main(String[] args) {
for(int i=0;i<10;i++) {
long num = fibonacci(i);
System.out.print(num+" ");
}
}
}
斐波那契数列数列的非递归实现： F(n)=F(n-1)+F(n-2)
package test;
public class Test {
public static long fibonacci2(int n) {
long arr[] = new long[n+1];
arr[0]=0;
arr[1]=1; //n不能为0，因为n为0时，arr大小为1，arr[1]越界。
for(int i=2;i<=n;i++) {
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n];
}
public static void main(String[] args) {
for(int i=1;i<10;i++) {
long num = fibonacci2(i);
System.out.print(num+" ");
}
}
}