JavaScript #16

재귀

어떤 문제는 동일한 구조의 더 작은 문제로 나뉠 수 있고
그 작은 문제를 해결한다면 전체 문제도 마찬가지로 해결된다

---

더 작은 문제로 만드는 연습

문제를 작게작게 만들다보면 바로 풀 수 있게 된다

1. 입력값과 출력값 정의
2. 입력값 혹은 문제의 순서와 크기를 확인
   크기를 구분하거나 순서가 명확히 정해진다면 OK
3. 크기가 더 이상 작아지지 않거나 순서의 마지막일 경우가 가장 작아진 문제

작은 문제를 해결하면?
문제를 작아지게 만든 방법대로 전체 문제를 해결

코드 예시)

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

---

Factorial

5!
= 5 × 4 × 3 × 2 × 1
= 5 × (4 × 3 × 2 × 1) = 5 × 4!
= 5 × 4 × 3! = ...

function fac(n) {
  if (n === 1) return 1  // 가장 작은 경우
  return n * fac(n-1) // 문제를 작게 만들기

fac(4)의 동작 방식

---

그림 출처 : codestates