在数学上,费波那契数列是以递归的方法来定义:
F(0) = 0;
F(1) = 1;
F(n) = F(n-1) + F(n-2);
那么下面就来看看实现它的几种方式:
- 递归法
代码如下:
function fib(n)
{
if(n == 0)
{
return 0;
}
if(n == 1)
{
return 1;
}
else
{
return fib(n - 1) + fib(n - 2);
}
}
- 迭代法
代码如下:
function fib(n)
{
var f0 = 0;
var f1 = 1;
var currentFib;
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
for(i = 1;i < n;i++)
{
currentFib = f0 + f1;
f0 = f1;
f1 = currentFib;
}
return currentFib;
}
- 数组法
代码如下:
function fib(n)
{
var list = [];
list[0] = 0;
list[1] = 1;
for (var i = 1; i < n; i++) {
list[i + 1] = list[i] + list[i - 1];
}
return list[n];
}