[algorithm] Fibonacci 수열 알고리즘 - 개선된 알고리즘

문제: 재귀함수를 이용하여 피보나치 수열을 만드는 알고리즘을 개선하기

기존 알고리즘

// 효율이 떨어지는, 재귀로 구현하는 피보나치수열
function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

/* 알고리즘의 문제점
fibonacci수열을 반복해서 계산하는 문제가 있다.
예를 fibonacci(5)를 구할 때,
fibonacci(5) = fibonacci(4) + fibonacci(3)
             = (fibonacci(2) + fibonacci(3)) + (fibonacci(1) + fibonacci(2))
             = (fibanacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)) + (fibonacci(1) + fibonacci(2))
이런 식으로 같은 피보나치수를 반복해서 구한다.
fibonacci(5) = fibonacci(4) + fibonacci(3)
             = fibonacci(2) + fibonacci(3) + fibonacci(3)
사실 겹치는 수 fibonacci(3)을 기억해두었다가 나중에 재사용하면 같은 계산을 반복하지 않을 수 있다.
메모리를 조금 더 사용하고 계산시간을 훨씬 줄일 수 있게 된다.
*/

// 개선된, 재귀함수를 이용한 피보나치 수열 알고리즘
function fibonacci(n) {
  const memo = [0, 1]; // fibonacci(0) = 0, fibonacci(1) = 1
  const recur = x => { 
      if (memo[x] !== undefined) { // 이미 계산된 값이라면
        return memo[x];             // 가져다쓴다
    } else {                     // 아직 계산되지 않은 값이라면
        return memo[x] = recur(x - 2) + recur(x - 1); // 계산해서 저장한 다음 리턴한다.
    }
  }
  return recur(n);
}