(Javascript) 재귀(recursion)와 메모이제이션(Memoization) (1)

재귀

재귀란 함수가 자기 자신을 호출 하는 것을 의미합니다. 간단하게 팩토리얼(!) 을 알려주는 함수를 만들어보겠습니다.

var factorial = function(number){
var result =1 ; 
for(var i = 1 ; i <= number ; i++) {
		result *=i;
	}
	return result;
	
}; 
factorial(3); //6
factorial(4); //24

위에 코드도 맞는 코드지만 우아하지도 않고 확장가능성도 없습니다 . 재귀를 사용해서 코드를 만들어보겠습니다 .

var factorial = function(number){
	if(number>0){
		return number * factorial(number -1);

	} else {
	return 
	}
};

factorial (3) // 6
factorial(4) //24 

factorial 함수를 만들었는데 그 안에 factoral 함수를 또 호출합니다. 자기 자신을 호출하는 건데요 인자만 n 에서 n-1 로 바꿨습니다 factorial (3) 호출을 하면 내부적으로는 3*factorial(2) 가 호출됩니다.

factorial(2) 는 2factorial(1) 호출하고 factorial(1)은 1factorial(0) 을 호출합니다
factorial(0) ==1 이기 때문에 최종적으로 결과는 3 2 1 =6 이 됩니다 .

참고로 처음 코드처럼 한번에 풀지 않고 , 재귀적으로 푸는 것은 불할 정복 알고리즘 중의 하나입니다. 어떤 문제를 한 번에 풀기 힘들 때 , 작은 조각으로 쪼개어 푸는 것을 분할 정복 알고리즘 이라고 합니다.

이렇게 재귀를 사용하는 것은 컴퓨터에게는 많은 부담을 주지만 ,사람에게는 가독성을 높혀줍니다 .따라서 성능을 중시한다면 재귀를 쓰지 않는것이 좋습니다 하지만 재귀는 많은 곳에서 사용되기 때문에 꼭 알아두어야합니다.

메모이제이션

메모이제이션이란 프로그래밍을 할때 반복되는 결과를 메모리에 저장해서 다음에 같은 결과가 나올 때 빨리 실행하는 코딩 기법을 말합니다.

이전 코드에서 factorial(3) 을 호출한 후 factorial(4)를 할 때 뭔가 아쉽습니다.
factorial(4) 는 4*factorial(3) 인데요 . factorial(3) 은 아까 호출 했었죠. 하지만
factorial(4) 에서 예전의 결과값을 활용하지 못하고 다시 계산해버렸습니다 .

만약 factorial(3) 을 했던 결과값이 메모리에 남아있었다면 재사용할 수 있었겠죠 ?

다음과 같이 클로저를 사용해 계속 유지되는 저장 공간을 만든 후 코드를 바꿔봅시다.

var factorial = (function(){
	var save = {};
	var fact = function(number){
		if(number>0){
			var saved = save[number -1] || fact(number-1);
			var result = number*saved;
			save[number] = result
			console.log(saved,result);
 			return result;
           
	}	else {
		return 1;
	}
};
return fact
})();

factorial(7) // 1 1 , 1 2,2 6,6 24,24 120 ,120 720,720 5040

이렇게 클로저를 만든 후 factorial(7)을 두 번 연속 해봤습니다 . 처음 호출 때는 처음 계산 하는 것이기 때문에 계산이 여러번 실행 됩니다. console에 나오는 게 계산을 실행하는 과정입니다. 두 번째 호출 때는 한 번 만에 실행 결과가 나옵니다. 이전에 했던 계산이 메모리에 저장되어 있기 때문이죠 .

다른 예제로 피보나치 수열이 있습니다 . 피보나치 수열은 특이하게도 함수 안에서 두 번의 재귀 호출을 합니다 . 재귀가 빛을 발하는 순간이죠.

var fibonacci = function(number){
	if(number<2) {
		return number;
	} else {
		return fibonacci(number -1) + fibonacci(number -2 );
	}
}