02. 재귀의 활용

---

• 일반적인 재귀함수의 템플릿

function recursive(input1, input2, ...) {
 //base case : 문제를 더 이상 쪼갤 수 없는 경우
 if (문제를 더 이상 쪼갤 수 없는 경우) {
   return 단순한 문제의 해답;
  }

//recursive case : 그렇지 않은 경우
 return 더 작은 문제로 새롭게 정의된 문제

🔨 Guide. 재귀적으로 사고하기

🔧 1. 재귀 함수의 입력값과 출력 값 정의하기

• 함수 arrSum의 경우 number타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다.

arrSum: [number] => number ← 입출력값 정의

🔧 2. 문제를 쪼개고 경우의 수를 나뉘기

• 입력값이나 문제의 순서와 크기가 중요하다.
• 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 푸는데 도움이 된다.
• 경우의 수는 일반적으로 문제를 더 이상 쪼갤 수 없는 경우 / 그렇지 않은 경우로 나눈다.
• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다.

//1. 입출력 값 정의
arrSum: [number] => number 
//2. 경우의 수 나누기
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결(탈출)
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

🔧 3. 단순한 문제 해결하기

• 가장 해결하기 쉬운 문제부터 해결하는 것을 ‘재귀의 기초(base case)’라고 한다.
• 재귀의 기초는 재귀 함수를 구현할 때 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
• 만약 탈출 조건이 없다면 ? → 재귀함수는 끝없이 자기 자신을 호출하게 된다.

🔧 4. 복잡한 문제 해결하기

• 마지막으로 남아있는 복잡한 경우를 해결한다.

- 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있습니다.

🔧 5. 코드로 구현하기

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

🔨 2. 실습 예제

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 `fac` 을 작성하세요.
  예1) fac(5)  ===  5 * 4 * 3 * 2 * 1  ===  120
  예2) fac(3)  ===  3 * 2 * 1  ===  6

function fac(n) {
 if(n === 1) {
   return 1
  }
 return n * fac(n-1);
 }