얼마나 이해했나요? - 재귀

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.

재귀
구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법이다.
인자가 빈 배열이 아닌 경우, 함수는 자기 자신을 호출하기도 하는데 이것을 재귀 호출이라고 한다.

• 재귀를 언제 사용해야 하는지 알고 있다.

＊ 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
＊ 중첩된 반복이 많거나 중첩의 정도를 미리 알 수 없는 경우

• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.

① 재귀 함수의 입력값과 출력값 정의하기

입력값: array
출력값: number

② 문제를 쪼개고 경우의 수를 나누기 → 순서와 크기로 기준을 정하기

arr([])		- 빈 배열일 때
arr([arr1, arr2, ... , arr(n)])	- 빈 배열이 아닐 때

③ 단순한 문제부터 해결하기 (base case) → 결과가 하나 혹은 두개일 때
→ arr를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arr은 0이다.

arr([]) === 0
arr([arr1, arr2, ... , arr(n)])	- 빈 배열이 아닐 때

④ 남아있는 복잡한 문제 해결하기
→ arr의 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고,
나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더한다.

arr([]) === 0
arr([arr1, arr2, ... , arr(n)]) = arr1 + arr([arr2, ..., arr(n)])

⑤ 코드로 구현하기

function recursive(input1, input2, ...) {
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  그렇지 않은 경우
  // let head = arr[0]		→ 배열의 첫 요소
  // let tail = arr.slice(1);	→ 배열의 첫 요소만 제거된 배열
  return head + recursive(tail);
}

• 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
  - 실생활에 사용 되는 유용한 Tree 구조를 알고 있다.
  - 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.