재귀적 사고

Achievement Goal

• 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
• 재귀를 언제 사용해야 하는지 알고 있다.
• 재귀적 사고 연습을 통해 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.
• 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
• 실생활에 사용되는 유용한 Tree 구조를 알고 있다.
• 깊이를 알 수 없는 Tree 구조에 재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

재귀적 사고

• 잘게 쪼개어 사고하는 법
• 함수 자신의 재귀적 호출
• 탈출 조건

재귀적 사고를 하면 좋은 점

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있을 때 코드를 이해하기 편하다
• 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우에 유용하다

재귀적으로 사고하기

1. 문제를 가장 단순하게 정의하기
2. 문제를 쪼개고 경우의 수를 나누기 : 기준은 1. 입력값 기준 2. 문제의 순서/크기에 따라
3. 단순한 문제 해결하기 : 가장 해결하기 쉬운 문제부터 해결한다
   특히 재귀의 기초(base case), recursive case 템플릿을 활용하면 좋다.

   function recursive(input1, input2, ...) {
    // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
    if (문제를 더 이상 쪼갤 수 없을 경우) {
      return 단순한 문제의 해답;
    }
    // recursive Case
    // 그렇지 않은 경우
    return 더 작은 문제로 새롭게 정의된 문제
    // 예1. someValue + recursive(input1Changed, input2Changed, ...)
    // 예2. someValue * recursive(input1Changed, input2Changed, ...)
   }

재귀적 사고 패턴

• 배열인 경우 head와 tail을 통해 재귀적 과정을 거친다는 것을 이해하자

const head = arr[0], tail = arr.slice(1)
return head + newFunction(tail)

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}