递归法：
long int fibonacci(int input)
{
long int result;
if (input >= 2) {
result = fibonacci(input-1) + fibonacci(input-2);
} else {
switch (input) {
case 0:
result = 0;
break;
case 1:
result = 1;
break;
}
}
return result;
}
循环法：
long long int fibonacci(int input)
{
long long int f0 = 0;
long long int f1 = 1;
long long int f2;
int i;
switch (input) {
case 0:
return f0;
case 1:
return f1;
}
for (i = 2; i <= input; i++)
{
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f1;
}
| 方法 | 时间复杂度 |
|---|---|
| 递归法 | O(2^n) |
| 循环法 | O(n) |
