07.斐波那契数列

2021-03-03
swordoffer

题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… , 这个数列从第3项开始，每一项都等于前两项之和。

JS实现

//递归实现
const Fibonacci = (n) => {
  if (n <= 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2);
};

//迭代实现
const Fibonacci = (n) => {
  if (n <= 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }

  let a = 0,
    b = 1,
    sum = 0;
  for (let i = 2; i <= n; i++) {
    sum = a + b;
    a = b;
    b = sum;
  }
  return sum;
};