재귀함수 이용

function fibonacci(n) {
  if(n===0){
    return 0
  }if(n===1){
    return 1
  }
  return fibonacci(n-1)+fibonacci(n-2)
}

중복호출이 많아 런타임이 길어진다.

+memoization

중복호출을 개선하기 위해 전에 구한 항을 기록하여 꺼내쓰는 방식

function fibonacci(n) {
  const fibArr=[0,1]
  function fibo(n) {
    //base
    if(fibArr[n]!==undefined){//항이 이미 존재 할 경우
      return fibArr[n] //그대로 리턴
    }
    fibArr[n]=fibo(n-1)+fibo(n-2) //재귀
    return fibArr[n]
  }
  return fibo(n)
}

for문 이용

function fibonacci(n) {
  const fibo=[0,1]//0번째 1번째 항
  for(let i=2 ; i<=n ;i++){//2번째 항부터
    fibo.push(fibo[i-1]+fibo[i-2]) //fibo[i]를 만들어준다.
  }
  return fibo[n]
}