출처

재귀

= 함수가 자기 자신을 호출하는 것

• 대게 반복문으로 구현한 코드보다 코드의 길이가 더 짧다
• 재귀 깊이(recursion depth) : 첫 호출을 포함한 중첩 호출의 최대 개수
  • = 실행 컨텍스트 스택에 들어가는 실행 컨텍스트의 최댓값
  • JS엔진에서는 최대 재귀 깊이가 제한되어있다.
  • 하지만 대부분의 간단한 호출은(ex-몇만번) 문제되지 않는다

실행 컨텍스트

= execution context stack
= 함수 실행 절차에 대한 세부 정보를 저장하고 있는 내부 데이터 구조

• 제어 흐름의 현재 위치
• 변수의 현재 값
• this의 값

등이 저장된다
실행 컨텍스트는 함수 호출 1회당 1개씩 생성된다.

중첩 호출 시 실행되는 절차

1. 실행 중이던 함수 일시 정지
2. 중지된 함수의 실행 컨텍스트가 실행 컨텍스트 스택 (execution context stack)에 저장됨
3. 중첩 호출 실행
4. 중첩 호출 실행 완료 시, 실행 컨텍스트 스택에서 임시 저장한 컨텍스트를 다시 꺼내와서 이어서 실행

실행 컨텍스트는 메모리를 차지하기 때문에, 재귀가 많이 중첩될 수록 메모리를 많이 차지한다! 반면, 반복문은 전체 실행동안 실행 컨텍스트가 한 개 생성된다. 따라서 반복문이 메모리를 더 절약할 수 있는 방식이지만, 때에 따라 코드의 길이, 가독성, 유지보수 등을 모두 고려하여 더 적절한 구현법을 선택해야 한다.

• 재귀적 순회(recursive traversal) 구현 시 사용하기 좋다
  • 배열과 객체가 중첩되어있는 형태에서 모든 하위요소를 순회해야 할 때

재귀적 구조

• 재귀적으로 정의된 자료구조
• 자기 자신의 일부를 복제하는 형태의 자료 구조

연결 리스트

• 배열은 뒷쪽요소에 대한 삽입/삭제(push/pop)이 아닌, 앞쪽에 대한 삽입/삭제(shift, unshift)의 경우 연산 수행 시간이 많이 걸린다. (뒤의 요소를 모두 이동시켜줘야 하기 때문에)
• 이러한 배열의 한계점을 극복한 자료구조가 바로 연결리스트이다.
  • 앞이나 뒤나 동일하게 빠르게 요소를 삽입/삭제할 수 있다.

구성요소

• value

• next : 연결리스트에서 다음 요소를 참조하는 프로퍼티

  • 다음 요소가 없을 시 값은 null

• 연결 리스트의 첫 요소의 참조는 연결 리스트를 담는 변수명에 저장되어있다.

• value와 next 직관적으로 보여주는 예시

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;
// 기존 연결리스트의 세번째 요소를 null로 비워준다. 
list.next.next = null;

이 코드의 결과, list 연결리스트의 두번째 요소와 세번째 요소 간의 체인이 끊어지면서 하나의 연결리스트를 분리시킬 수 있다.

• 연결리스트 합치기

list.next.next = secondList;

위 코드에서 secondList 연결리스트의 첫 요소를 list연결리스트의 세번째 요소로 지정한다.
그 결과, list와 secondList 가 합쳐질 수 있게 된다.

• 연결리스트 중간 요소 제거

list.next = list.next.next;

이 코드에서는 list의 두번째 요소 자리에 list 의 세번째 요소를 집어넣어 준다.
즉, 기존의 list의 두번째 요소는 삭제되고 그 뒤의 나머지 리스트가 한칸 앞으로 당겨져 온 형태와 같아진다.

• 연결리스트의 단점
  index가 있는 배열에 비해 특정 요소에 쉽게 접근할 수가 없다.

// 배열 : arr
console.log(arr[5]);
// 연결리스트 : list
console.log(list.next.next.next.next);