- 定义Fibonacci的第0项为0,第1项为1,使用C代码求出第n项
// 递归方法, 特点:容易实现,时间空间复杂度高
int fib(int n) {
// 入参合法判断
if (n < 0) {
return -1;
}
// 基线条件(base case)
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
// 循环, 特点:速度快,内存占用少
int fib(int n) {
// 入参合法判断
if (n < 0) {
return -1;
}
int f0 = 0, f1 = 1, f2;
int i;
if (n < 2) {
return n;
}
for(i = 1; i < n; i++) {
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f2;
}