재귀에 대해 파헤쳐보자

아오 재귀... 알다가도 모를 재귀..
알겠다고.. 알겠는데.. 너 어케쓰니?
하필 재귀 할때 컴터가 맛가서+이동중이라 수업에 참여할 수가 없었다ㅠㅠ
페어없이 혼자 진행해야 해서 너무너무 걱정이었는데,
생각보다 나 혼자서도 잘하네!? 근데 쓰면서도 왜되는건지 왜 안되는건지 모르겠다.

코어자바스크립트

https://ko.javascript.info/recursion

코어자바스크립트를 처음부터 끝까지 함 정독해보자 ㄱㄱ~🤪

1. base case

모든 절차가 간단해지는, 명확한 결과값을 도출하는 케이스

2. recursive case

목표 작업을 간단한 동작과 목표작업을 변형한 작업으로 분할한다.

function pow(x, n) {
  if (n == 1) { //base case
    return x;
  } else { //recursive case
    return x * pow(x, n - 1);
  }
}
//삼항연산자로 더 간결하게 만들 수도 있다.
function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수를 재귀 깊이라고 한다. pow의 재귀 깊이는 n이다. 자바스크립트 엔진은 최대 재귀 깊이를 제한한다. 엔진에 따라 다르지만 만개까지 허용한다고 보면 될 듯 하다!

실행 컨텍스트와 스택

실행중인 함수의 실행 절차에 대한 정보는 해당 함수의 실행 컨텍스트에 저장된다. 실행 컨텍스트는 제어흐름의 현재위치, 변수의 현재 값, this의 값 등의 상세 내부 정보가 저장되는 곳이다.
함수 호출이 될 때마다 하나의 실행 컨텍스트가 생성된다!
함수 내부에 중첩 호출이 있을 때, 현재 함수가 일시중지된다. 그리고 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택이라는 자료구조에 저장된다. 중첩 호출이 실행되고, 실행이 끝난 후엔 실행 컨텍스트 스택에서 일시중지 된 함수의 실행 컨텍스트를 꺼내와서 실행을 이어간다.
이때 중첩이 계속될 경우, 스택에 컨텍스트가 쌓이게 된다.
스택은 LIFO(Last In First Out)의 구조를 가지고 있다. 처음 들어온 자료는 아래에 쌓이고 최근 들어온 자료일수록 상단에 위치한다.
스택이 쌓이고, 결국엔 베이스케이스를 만나게 될 것이다. 베이스케이스에서는 명확한 값을 리턴할 것이고, 컨텍스트는 실행을 마쳤으니 삭제된다. 다음 컨텍스트가 실행되고, 베이스케이스에서 리턴된 값과 계산 후 결과를 리턴한다. 이렇게 맨 아래에 있는 컨텍스트까지 실행되면 최종 값이 출력된다.

메모리주의!

함수가 실행될 때마다 메모리를 차지하는 크기가 커진다. 재귀의 깊이가 깊을수록 큰 메모리가 필요하다.

반복문을 사용하면 메모리가 절약된다.

반복문을 사용한 함수는 컨텍스트를 하나만 사용한다.

반복문과 재귀가 큰 차이가 없는 경우도 있다.

1. 조건에 따라 함수가 다른 재귀 서브 호출을 하고, 그 결과를 합칠 때.
2. 분기문이 복잡하게 얽혀있을 때.

재귀적 순회를 구현할 때 사용하면 좋다.

즉, 필요한 데이터의 깊이가 일정하지 않을때.
하위 부서의 깊이와 상관없이 급여에 접근 할 수 있다.

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

배열을 사용하는 경우: base case
객체를 사용하는 경우: recursive case

function sumSalaries(department) {
  if (Array.isArray(department)) { // base case: 배열인경우
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else { // recursive case: 객체인 경우
    let sum = 0; //Object.values(): 프로퍼티의 값이 담긴 배열 반환
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); 
      // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
    }
    return sum;
  }
}

Object.values()

그냥 찍으면 객체로 반환되는데, Object.values()로 찍으면 배열로 반환된다!

Object.values(company.sales[0])
//(2) ['John', 1000]
company.sales[0]
//{name: 'John', salary: 1000}

재귀적 구조

재귀적 자료구조는 자기 자신의 일부를 복제하는 형태의 자료구조이다.
HTML, XML도 재귀적 자료구조 형태를 갖고 있다!

Linked list : 연결 리스트(연접 리스트)

연결 리스트는 스택과 같은 기본적인 자료구조 중 하나이다.

배열은 요소를 추가하거나 삭제할 때 비용이 많이 든다.

왜냐고? 배열은 연속된 메모리 공간을 차지한다. 예를 들어 보자.
let arr = ['시고르자브종', '진돗개', '시바견', '말티즈', '포메라니안', '시츄', ..., '푸들']
여기 arr라는 배열이 있다. 시고르자브종은 공식명이 아니니(?) 지우기로 했다. 마침 0변 인덱스에 있으니 arr.shift() 하면 끝일까? 놉.
진돗개를 arr[0]으로 옮기고, 시바견도 arr[1]로 옮기고... 이짓을 해야한다... 어휴. 중간에 견종을 추가하려고 해도 마찬가지. arr[5]에 '꼬똥 드 툴레아'를 추가하려면 arr[5] 부터 arr[arr.length -1]까지 한칸 뒤로 밀어줘야한다!

연결 리스트는 뭐가 다른가 하면,

배열처럼 연속된 메모리 공간을 차지해야 할 필요가 없다! 꼬리에 다음에 올 데이터의 주소를 갖고 있어서, 그 주소로 찾아가면 되는 것.
정처기 짬밥좀 털어봤다ㅋㅋㅋㅋ 여턴간에... 이 연결리스트를 어떻게 활용하면 된다구?

연결 리스트의 요소: value, next

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null //다음 데이터가 없으면 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;

체인의 시작 객체는 변수 list에 저장되어있다. 연결 리스트를 사용하면 전체 리스트를 여러 부분으로 나누기도 쉽고, 다시 합치는 것도 가능하다.

//나누기
let secondList = list.next.next;
list.next.next = null;
//합치기
list.next.next = secondList;

연결 리스트는 인덱스로 접근할 수가 없다는 단점이 있다...! 두둥 너무나도 큰 단점이군