파트 1 - 5) 함수 심화학습 - 1) 재귀와 스택

재귀와 스택 https://ko.javascript.info/recursion

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

pow (2, 4)를 계산하려면 아래와 같은 재귀 단계가 차례대로 이어진다.

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

실행 컨텍스트와 스택

실행 중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트(execution context) 에 저장된다.

실행 컨텍스트는 함수 실행에 대한 세부 정보를 담고 있는 내부 데이터 구조로 제어 흐름의 현재 위치, 변수의 현재 값, this의 값 등 상세 내부 정보가 실행 컨텍스트에 저장된다.

함수 호출 일 회당 정확히 하나의 실행 컨텍스트가 생성된다.

함수 내부에 중첩 호출이 있을 때는 아래와 같은 절차가 수행된다.

1. 현재 함수의 실행이 일시 중지
2. 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택(execution context stack) 이라는 특별한 자료 구조에 저장
3. 중첩 호출 실행
4. 중첩 호출 실행이 끝난 이후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내오고, 중단한 함수의 실행을 다시 이어감.

연결리스트

하지만 배열은 요소 '삭제’와 '삽입’에 들어가는 비용이 많이 든다.
빠르게 삽입 혹은 삭제를 해야 할 때는 배열 대신 연결 리스트(linked list)라 불리는 자료 구조를 사용할 수 있다.
연결 리스트 요소는 value, next 프로퍼티를 사용하여 정의할 수 있다.
next는 다음 연결 리스트 요소를 참조하는 프로퍼티로 다음 요소가 없을 땐 null이 된다.

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};
// 아래처럼 작성할 수도 있다.

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

연결 리스트를 사용하면 전체 리스트를 여러 부분으로 쉽게 나눌 수 있고, 다시 합치는 것도 가능하다. 요소를 쉽게 추가하거나 삭제할 수도 있다.

//나누기
let secondList = list.next.next;
list.next.next = null; // list는 1->2->null, secondList는 3->4->null

//합치기
list.next.next = secondList;

//list에 새로운 value 추가
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

list = { value: "new item", next: list };
//list에 'new item'이 들어가고 next는 기존 list값인 1이 된다.

//중간 요소 제거하려면 이전 요소의 next를 변경해주면 된다.
list.next = list.next.next; //list(='new item')의 next(=1)에 next의 next(=2)를 넣음

위 예시의 마지막 예문에서 변경된 next인 1은 체인에서 제외되어 다른 곳에 따로 저장되지 않으면 메모리에서 제거된다.

1. 이전 요소를 참조하는 프로퍼티 prev를 추가해 이전 요소로 쉽게 이동하게 할 수 있다.
2. 리스트의 마지막 요소를 참조하는 변수 tail를 추가할 수 있습니다. 다만 이때 주의할 점은 리스트 마지막에 요소를 추가하거나 삭제할 때 tail도 갱신해 줘야 한다.
   이 외에도 요구사항에 따라 구조를 변경할 수 있다.