記錄斐波那契數(shù)列面試題

題目：1 1 2 3 5 8 13 21 34...請輸入第30位的值。

分析：規(guī)律為arr[i] = arr[i-1] + arr[i-2]。

實現(xiàn)方式：

for循環(huán)方式

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