피보나치 수열, 자바스크립트 재귀로 함수 만들기(feat.메모이제이션)

메모이제이션을 사용한 피보나치 수열의 재귀 함수
피보나치(Fibonacci) 수는 이탈리아 수학자인 레오나르도 보나치(Leonardo Bonacci)에 의해 연구되어 알려진 것으로, 토끼가 새끼를 낳아 매달 증가하는 토끼의 수에 관해 계산하는 것으로 유명합니다.

0부터 시작하는 수를 순서대로 나열하면,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181…….와 같이 수가 증가하는데요.

바로 앞(n-1)의 수와 그 바로 앞(n-2)의 수를 더하면 현재의 수(n)가 됩니다.

다음 그림은 네모칸 채우기로 한 면의 길이가 피보나치 수와 같이 증가를 보이는 것을 알 수 있습니다.

출처:https://en.wikipedia.org/wiki/Fibonacci_number

사각형이 1/4씩 회전하며 그리는 나선형은 황금 비율(1.618)에 수렴하여 과학적이며 예술적인 비율을 만들어 낸다고 합니다.

https://en.wikipedia.org/wiki/Fibonacci_number

그럼 이 피보나치 수열을 재귀를 사용해 자바스크립트 함수로 만들어 보겠습니다.

const fibonacci = (n) => {

  if ( n <= 1 ) {
    return n;
  }
  
  return fibonacci(n-1) + fibonacci(n-2);
}

위 함수는 피보나치 수열을 재귀적으로 수행하지만 계산 양이 늘어날 때마다 시간 복잡도는 가파르게 증가합니다.

이는 계산의 중복 문제 때문인데요.

예를 들어 fibonacci(10)을 실행하면 fibonacci(9), fibonacci(8), fibonacci(7)……. 순서로 실행을 하게 되는데요.

fibonacci(9)는 다시 fibonacci(8), fibonacci(7), fibonacci(6)…. 을 실행하게 됩니다.

결국 이미 한 계산을 하고 또 하고 또 하고… 합니다.

하지만 이미 수행한 계산 결과를 배열로 저장해두고 거기서 값을 꺼내쓰면 계산의 중복은 발생하지 않으므로 효율적이고 아름다운 함수가 됩니다.

이를 메모이제이션(Memoization)이라고 하는데요.

메모이제이션을 사용하는 자바스크립트 코드는 다음과 같습니다.

const fibo = (num, memo) => {

      memo = memo || {}

      if(memo[num]){
          return memo[num]
      }

      if(num<=1){
          return num;
      }

      return fibo(num-1, memo) + fibo(num-2, memo);

}

간단하면서도 효율적으로 피보나치를 계산하는 자바스크립트 함수를 사용할 수 있습니다.