[Javascript] 재귀와 스택

두 가지 사고방식

1. 반복적인 사고를 통한 방법: for 루프
2. 재귀적인 사고를 통한 방법: 작업을 단순화하고 자기 자신을 호출함

재귀 깊이

재귀 깊이(recursion depth): 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수

자바스크립트 엔진은 최대 재귀 깊이를 제한한다!

만개 정도까진 허용, 대다수의 엔진이 십만까지는 다루지 못 함

실행 컨텍스트와 스택

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

• 함수 1회 당 정확히 하나의 실행 컨텍스트가 생성

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

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

재귀와 반복문

실행 컨텍스트는 메모리를 차지한다.

→ 재귀를 사용하면 반복문을 사용한 코드보다 메모리 공간이 더 필요하다.
→ 반복문을 사용하면 필요한 메모리가 적고, 사용 메모리 공간이 고정된다.

 

그러나, 항상 재귀를 이용해 작성한 코드를 반복문을 사용한 코드로 다시 작성하는게 정답은 아니다!

재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에 이점이 있다.

 

우리는 모든 곳에서 메모리 최적화를 신경 써서 작성하지 않아도 된다. 우리가 작성해야 하는 코드는 좋은 코드이다. 메모리, 유지보수, 가독성 등 여러 방면에서 코드를 바라봐야 한다.

재귀적 순회

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

한 회사의 임직원을 나타내는 복잡한 객체가 있다.

• 부서에는 여러 명의 직원이 있는데, 이를 배열로 표현할 수 있습니다. sales 부서의 John과 Alice라는 2명의 직원을 배열 요소로 표현해 보았습니다.
• 부서는 하위 부서를 가질 수 있습니다. development 부서는 sites와 internals라는 두 개의 하위 부서를 갖습니다. 각 하위부서에도 직원이 있습니다.
• 하위 부서가 커지면 더 작은 단위의 하위 부서(또는 팀)로 쪼개질 가능성도 있습니다.

모든 임직원의 급여를 더한 값을 구해야 하는 요구사항이 들어왔을 때, 어떻게 코드를 구현하면 좋을까?

재귀 사용에 익숙치 않는 나 같은 경우 글에서 말하는 정말 지저분한, 덕지덕지 중첩 반복문이 붙은 코드를 짰을 것 같다.

---

재귀를 이용한 풀이법은 어떨까?

 

임직원 급여 합계를 두 가지 경우로 나누어 생각한다.

1. 임직원 배열을 가진 '단순한' 부서 - 간단한 반복문으로 급여 합계를 구할 수 있다.
2. N개의 하위 부서가 있는 객체 - 각 하위 부서에 속한 임직원의 급여 합계를 얻기 위해 N 번의 재귀 호출을 하게 되고, 최종적으로 모든 하위부서 임직원의 급여를 더한다.

// 급여 합계를 구해주는 함수
function sumSalaries(department) {
  if (Array.isArray(department)) { // 첫 번째 경우
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else { // 두 번째 경우
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
    }
    return sum;
  }
}

재귀적 구조

재귀적 구조: 자기 자신의 일부를 복제하는 형태의 자료 구조

웹 개발자에게 익숙한 HTML과 XML도 재귀적 자료 구조 형태이다.

HTML 태그는 아래와 같은 항목으로 구성되기 때문이다.

• 일반 텍스트
• HTML-주석
• 이 외의 HTML 태그

연결 리스트

배열 대신 빠르게 삽입 or 삭제를 해야할 때 사용할 수 있는 자료구조!

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

• value
• next : 다음 연결 리스트 요소를 참조하는 프로퍼티. 다음 요소가 없을 땐 null이 된다.

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

or

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;

 

참고 자료

• 재귀와 스택