[JAVASCRIPT.INFO] 6.1 재귀와 스택

6.1 재귀와 스택

함수가 자기자신을 호출할 수도 있는데, 이를 재귀라고 한다

실행 컨텍스트와 스택

실제 재귀 호출이 어떻게 동작하는가

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

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

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

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

• 현재 함수의 실행이 일시 중지됨
• 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택에 저장됨
• 중첩 호출 실행
• 중첩 호출 실행 완료 후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내오고, 중단한 함수의 실행을 재개함

재귀적 순회

예시는 재귀와 순회-재귀적순회 에서 참고

구조가 단순하지 않은 경우 반복문을 사용해서 구하기 쉽지 않다. 이런 경우 재귀를 이용한 풀이법을 사용하면 좋다.

• N개의 하위 부서가 있는 객체 - 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 N번의 재귀 호출을 실행

let company = {
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600}],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Aliex', salary: 1800}],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

function sumSalaries(department) {
  if(Array.isArray(department)){
    return department.reduce((prev, cur) => prev + cur.salary, 0);
  } else {
    let sum = 0;
    for(let subdep of Ojbect.values(department)){
      sum += sumSalaries(subdep);    // 재귀 호출로 각 하위 부서 임직원의 급여 총합
    }
    return sum;
  }
}

재귀적 구조

연결 리스트

배열은 요소 '삭제'와 '삽입'에 들어가는 비용이 많이 든다. arr.unshift(obj) 연산을 수행할 경우 새로운 obj를 위한 공간을 만들기 위해 ㅁ모든 요소의 번호를 다시 매겨야 한다. (arr.shift()도 마찬가지)

빠르게 삽입 혹은 삭제를 해야 할 때는 배열 대신 연결 리스트라 불리는 자료 구조를 사용할 수 있다.

연결 리스트의 요소는 객체와 프로퍼티들을 조합해 정의할 수 있다.

• value
• 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;