斐波那契数列定义：From Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Fibonacci_number
In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence:[2][3]
or (often, in modern usage):
By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
or[4]
本例以后一种为例：
最简单的一种：两层递归
public static long fibonacci(int n){
if(n==0) return 0;
else if(n==1) return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}
问题是：随着n的数值逐渐增多，时间和空间耗费太大，读者可以自行实验。在我的机器上n=50时就不能忍受了。
考虑优化：一层递归
public static void main(String[] args) {
long tmp=0;
// TODO Auto-generated method stub
int n=10;
Long start=System.currentTimeMillis();
for(int i=0;i<n;i++){
System.out.print(fibonacci(i)+" ");
}
System.out.println("-------------------------");
System.out.println("耗时："+(System.currentTimeMillis()-start));
}
public static long fibonacci(int n) {
long result = 0;
if (n == 0) {
result = 0;
} else if (n == 1) {
result = 1;
tmp=result;
} else {
result = tmp+fibonacci(n - 2);
tmp=result;
}
return result;
}
递归时间减少了到不到50%
最好的方式，不使用递归的方式来做。
public static long fibonacci(int n){
long before=0,behind=0;
long result=0;
for(int i=0;i<n;i++){
if(i==0){
result=0;
before=0;
behind=0;
}
else if(i==1){
result=1;
before=0;
behind=result;
}else{
result=before+behind;
before=behind;
behind=result;
}
}
return result;
}