피보나치 수

코드

let mem = new Array(100000).fill(0)

function fib(n) {
  if (n <= 2) {
    return 1
  }
  
  // 메모이제이션 
  // mem배열에 이미 값이 할당되어 있는 경우 바로 그 인덱스의 값을 뱉는다.
  if (mem[n] !== 0) {
    return mem[n] 
  } else {
    mem[n] = (fib(n - 1) + fib(n - 2)) % 1234567
  }
  return mem[n]
}

fib(5)
console.log("fib(5): ", fib(5))

💪 도움됐던 재귀유튜브

재귀함수가 두개있을때, 어느 순서대로 처리되는지 궁금해서 찾아본 결과,

1. fib(n-1)함수가 1이하일때까지 호출됨(memory에 쌓임)
   fib(5), fib(4), ... fib(1)

2. fib(1)에서 함수가 종료되고 1을 뱉으면 memory에서 제거되고 fib(2)는 남아있던 fib(n-2)함수를 부른다(memory에 쌓임) 그러면 fib(1)이 쌓이고 1뱉고 , fib(0)도 1뱉는다. 그리고 fib(2)는 그 합인 1을 뱉으면서 memory에서 제거되다.

3. 반복...

❌ 하지만 ,,, 메모이제이션 + 재귀 방법으로 했을 경우, 오답 + 런타임 오류 발생

왜 ?????

1. 문제에서 1234567을 나눈 값을 할당하라고 했는데, 이는 100,000의 경우 소화할 수 있는 자료형을 초과해버려 엉뚱한 값이 나오기 때문에 매변 1234567값을 나눈값을 넣어줘야 엉뚱한 값이 들어가는 것을 방지할 수 있다.

2. 런타임 오류
   JS 엔진의 재귀함수 최대 깊이는 10,000이라고 한다. 따라사 문제에 주어진 최대값을 넣게 되면 10,000을 초과해버린다.

---

반복문과 배열로만 피보나치 수를 구한 코드

function fib(n) {
  let ans = [0, 1]

  if (n <= 1) return ans[n]

  for (let i = 2; i < n + 1; i++) {
    ans.push((ans[i - 2] + ans[i - 1]) % 1234567)
  }
  return ans[n]
}

function solution(n) {
  var answer = 0

  answer = fib(n)

  return answer
}