재귀적 사고 연습 (9-20)

재귀란?

• 문제를 해결할 때 구조가 동일하다면 더 작은 경우를 해결함으로 문제를 해결하는 방법을 말한다.

function arrSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

0. 위 예시 함수를 쪼개서 생각해보자.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
arrSum([]) = 0;

1. 원래 문제에서 출발 -> 더 작은 경우를 생각한다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

2. 더는 작아지지 않을때까지 더 작은 경우를 생각해보자.

um([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

3. 문제가 간단해져서 바로 풀 수 있게 되는 순간에 문제를 차근차근 해결한다.

arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

4. arrSum을 더 엄밀하게 정의할 수 있다.

arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(첫 요소를 제외한 나머지 배열)

5. 재귀는 언제 사용할까?

• 주어진 문제가 구조가 비슷하고, 더 작은 문제로 나뉘어질 수 있는 경우
• 중첩된 루프가 많거나, 중첩의 정도를 미리 알 수 없는 경우

재귀적 사고 연습하기

1. 재귀 함수의 입력값과 출력값 정의해보기!

• 문제를 가장 추상적 or 가장 단순하게 정리해보자
• arrSum의 경우 넘버타입을 요소로 갖는 배열을 입력받아서 넘버를 리턴한다를 간편하게 아래와 같이 표기해보자!

arrSum: [number] => number

2. 문제를 쪼개고, 경우의 수를 나누기

• 순서와 크기를 생각하면서 순서를 명확하게 정할 수 있는지, 크기를 기준으로 나눌 수 있는지 생각해본다.

2.1 arrSum은 배열의 크기에 따라 구분 가능!
arrSum([1, 2, 3, 4])과 arrSum([2, 3, 4])을 구하는 방법은 동일하니까 이 구분은 적절하다고 판단된다.
2.2 경우의 수로 나눈다!
빈배열인 경우, 그렇지 않은 경우로 나눌 수 있다.

arrSum: [number] => number
arrSum([ ])
arrSum([el, e2, ... , en])

3. 단순한 문제 해결하기

2번처럼 문제를 순서나 크기로 쪼개면서 가장 쉬운 문제를 먼저 해결한다. 이를 재귀으 기초(base case)라고 부른다. 그리고 재귀의 기초는 재귀함수구현 시 재귀의 탈출조건(재귀 호출이 멈추는 조건)을 구성하게 된다.

• arrSum를 더이상 쪼갤 수 없는 경우는 입력값이 빈배열인 경우이고, 이 때 arrSum은 0이다.

  arrSum: [number] => number
  arrSum([ ])
  arrSum([el, e2, ... , en])

4. 복잡한 문제 해결하기

• 남아있는 복잡한 문제 해결한다.
  4.1 arrSum이 길이가 1이상일때를 구하고(head라고 말하자) 나머지 요소를 구하는 것에 head를 더한다.

arrSum: [number] => number
arrSum([ ]) = 0
//위에는 입출력 단순히 표시하고
//빈배열일때 다음으로 이제 본격적으로 재귀 시작!(아래)
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

배열이 있을때(head)와 나머지 부분(tail)로 구분하자. 그럼 arrSum을 해결할 수 있다.

5. 코드 구현하기

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

추가적으로 일반적인 재귀함수의 템플릿(재귀함수연습에 활용해보자!)

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. 어떤값 + 본인함수(x,y,z, ...)
  // 예2. 어떤값 * 본인함수(x,y,z, ...)
}