参考斐波纳契函数java实现的误区--谨慎使用递归
最近在研究算法,遇到了斐波纳契函数,即1,2,3,5,8,13,21,34,55,89,...,通用式为:f(n)=f(n-1)+f(n-2).
一般的程序员想了想,撸起袖子,开工.
public static int fib(int n){
if(n<=2){
return 1;
}else{
return fib(n-1)+fib(n-2);
}
}
高手的程序员想了又想,慎重的写下了:
public static int fibonacci(int n) {
if (n <= 2) {
return 1;
}
int result = 0;
int first = 0, second = 1;
for (int i = 1; i < n; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}
前者使用的是递归,后者使用的是简单的循环.