[Javascript] Implementing in memoization(fibonacci, recursion)

오늘은 피보나치 수열을 재귀함수를 통해 2가지 방법으로 구현을 해보겠습니다.

1. 메모화(memoization)을 하지 않았을 때

2. 메모화(memoization)을 했을 때

우선 피보나치 수열의 정의와 메모화(memoization)에 대해서 알아보겠습니다.

피보나치 수열(Fibonacci sequence)

f(1) = 1

f(2) = 1

f(3) = f(2) + f(1) = 2

f(4) = f(3) + f(2) = 3

f(5) = f(4) + f(3) = 5 ···   

메모화(Memoization)

메모화란 프로그래밍을 할 때 반복되는 결과를 저장해서 이후 동일한 결과값이 나올 경우, 저장된 결과를 가져와 빨리 실행하는 기법을 의미합니다.

우선 메모화를 하지 않고 피보나치 수열을 구현해보겠습니다.

var fibo = function (n) {
if (n === 0 || n === 1) {
return n;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}

fibo(10);  // 55  

그렇다면 fibo(10)을 계산하는 동안 재귀함수를 몇 번 호출하는지 알아보겠습니다.

var count = 0;

var fibo = function (n) {
count++;
if (n === 0 || n === 1) {
return n;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}
fibo(10);  // 55  
console.log(count); // 177

fibo(10)을 계산하면서 177번의 반복을 하게됩니다. 인자의 수가 커진다면 엄청날 것입니다.

fibo(30)을 계산하면 83만번 이상의 반복을 하게됩니다.

여기서 필요한 것이 메모화입니다. 메모화는 반복되는 결과를 저장해서 이후 활용을 한다고 했습니다.

그럼 반복되는 결과를 저장하기 위해 객체를 선언해서 함수가 호출될 때마다 객체에 저장을 해보겠습니다.

var count = 0;
var memo = {};

var fibo = function (n) {
count++;
if (memo.hasOwnProperty(n)) {
return memo[n];
}
if (n === 0 || n === 1) {
return n;
} else {
memo[n] = fibo(n - 1) + fibo(n - 2);
return fibo(n - 1) + fibo(n - 2);
}
}

fibo(10);  // 55
console.log(count); // 37

반복되는 결과를 memo 객체에 저장을 해놓고 hasOwnProperty 메소드를 사용해 코드를 구현해봤습니다.

fibo(10)의 카운팅은 37번 밖에 되지않습니다. 심지어 fibo(1000)을 해도 카운팅이 4000을 넘지 않습니다.

---

recursion을 사용할 때는 무작정 쓰는 것이 아니라 메모화(Memoization)을 활용한다면 시간을 많이 단축할 수 있습니다.