记录斐波那契数列面试题

题目：1 1 2 3 5 8 13 21 34...请输入第30位的值。

分析：规律为arr[i] = arr[i-1] + arr[i-2]。

实现方式：

for循环方式

function fn(n, arr=[1,1]) {
  for (let i = 1; i < n-1; i++) {
    arr.push(arr[i]+arr[i-1])
  }
  return arr[n-1];
}
fn(30) //832040

递归方式

function fn(n, i = 1, arr=[1,1]) {
  if (n == 1 || n == 2) return 1 
  if(i <= n) {
    arr.push(arr[i]+arr[i-1])
  }
  i++;
  if(i>n){
    return arr[n-1]
  }
  return fn(n,i,arr)
}
fn(30) //832040

function fn(n) {
  if(n == 1 || n == 2) return 1
  return fn(n-1) + fn(n-2)
}
fn(30) //832040