코드 실행

• browser에서 parser가 코드를 한번 검사를 한다.

• 검사하면서 힙 메모리에 데이터가 저장된다.

• 인터프리터 형식으로 코드르 한 문장씩 실행한다.

• 실행하는 코드는 콜스택(callstack)에 들어왔다가 나가면서 순서대로 실행된다.

  	아직 깊게는 배울 수가 없었다. 현재까지 이해하고 기억난 바로는 이렇다.
  	추후에 엔진과 컴파일에 대해서 공부를 하게된다면 수정하려고 한다.

재귀함수

재귀의 사전적 정의는 본래의 것으로 돌아오는 것을 뜻한다.
그럼 재귀함수는 무엇일까?

재귀함수

• 재귀함수는 하나의 함수가 실행 될 때 자기 자신을 다시 호출하여 수행하는 함수를 뜻한다.

특징

• 변수를 여러 개를 선언할 필요가 없다.
  변수 선언이 아니라 하나의 함수를 재귀적으로 호출을 하면서 문제를 해결하기 때문에 변수의 수를 줄일 수 있다.

• for문이나 while문을 사용하지 않기 때문에 코드가 간결해진다.

예시1

// 1~5까지의 합
function recursion(number){
  	if (number == 1){
    	return 1
    }
 	return number + recursion(number-1)
}

기본적으로 재귀함수는 return하는 부분에서 자신을 호출하기 때문에 무한루프를 실행하게 된다. 따라서 if조건문을 사용하여 종료 조건을 설정해주고 실행시켜야한다. 따라서 1~5까지의 합으로 number가 1일때 재귀를 종료해줘야 함으로 1일때 1을 return하는 조건문을 사용한다.

예시2

//팩토리얼구하기 
function facto(number) {
  	if (number <= 1) {
      return 1
    }
  	return number * facto(number-1)
}
console.log(facto(5))
//결과 => 120

예시3

//피보나치 수열
function fib(number) {
	if(number <= 2 ) {
     	return 1 
    }else{
    	return fib(number-1) + fib(number-2)
    }
}
console.log(fib(10))
// 결과=> 55

유명한 피보나치 수열을 재귀함수로 구하는 예제이다.
전항과 전전항을 더해서 현재 항을 구하는 로직이기 때문에 재귀함수를 두번 호출하게 된다.

여기서 문제점이 발생하게 된다.
재귀호출에는 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해한다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되어 속도저하와 실행 중단이 일어날 수 있는 문제점이 있는데, 전항과 전전항 그리고 그 전항과 전전항 각각에서 전항과 전전항을 또 구하기 때문에 같은 fib(number)값을 또 연산하고 연산하게 된다.

그림을 보면 이미 fib(3)으르 분명히 구했는데 fib(4)에 재귀 호출에서 fib(3)을 또 연산하게 된다. fib(3)는 2번 fib(2)는 3번 fib(1)은 2번을 같은 계산이 실행되는걸 볼 수 있다. 이런 구조를 가지게 되기 때문에 간단한 연산이라도 실행 횟수가 많아지고 같은 데이터들을 많이 저장하기 때문에 속도저하와 연산중단이 일어날 수 있다.

실제로도 fib(50)만 실행해봐도 상당한 시간이 소요되는걸 몸소 체험할 수 있을 것이다.

메모이제이션 기법

위와 같은 문제를 해결하기 위해서 나온 기법으로 이미 계산한 함수 값을 저장해놓고 쓰일 일이 있으면 호출하여 사용하는 기법이다.

let memo = {}
function fibo(number) {
    if(n in memo){
        return memo[number]
    }else {
        if ( number <= 2 ) return 1
        memo[number] = fibo(number-1) + fibo(number-2)
        return memo[number]
    }
}

memo라는 전역 객체를 생성하고 ( 배열로해도 된다. ) number는 memo의 속성을, memo[number]는 fibo(number)의 값을 담당하는 역할을 수행한다.

1. 첫 if문에서 number in memo는 memo 속성 중에 number가 있는지 비교한다.

2. 첫 if문이 true라면 memo[number]를 반환하고 false라면 else문을 실행한다.

3. else문 안에 첫 if문에서 number가 2이하인지 비교한다.

4. true라면 1을 return하고 false라면 memo[number]에 fibo(number-1) + fibo(number-2)를 할당한다. 그리고 memo[number]를 반환한다.

메모이제이션 기법 을 검색하다보니 DP 동적 계획법이라는 것을 발견했다.
메모이제이션이 동적 계획법 중 하나인 것 같은데 점화식도 구상하고 아직 내게는 어려운 것 같아서 메모제이션이 무엇인지만 알고 넘어가자.