TIL 2 (2021.10.06)

재귀

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

재귀적으로 사고하는 법

 

function arrSum(arr) {
// 1. 먼저 입력값과 출력값에 대해서 정의한다. => arr는 숫자로 구성된 배열이며, 이 함수를 통해서 
//    배열의 모든 값을 더해서 숫자로 리턴한다. arrSum: [number] => number

 // 2. 문제를 쪼개 본다. 먼저 파라미터로 받는 배열이 [1, 2, 3, 4] 일 경우,
 //    맨 마지막에 진행되어야 할 함수부분은. 1 + [2, 3, 4]
 //    가장 처음에 진행되어야 할 부분은 [4] 인데, 여기에서 또 자르게 되면 [] 만 남게 된다. 
 
 
 //3. [4] 부분에 대해서 더 자세하게 정의한다면, 빈배열은 더하기에 영향을 주면 안되기 떄문에 0을 
 //   리턴하도록 한다. => base case가 된다.그리고 이 부분은 재귀의 탈출(재귀의 호출이 멈춘다) 이 되는 
 //   부분으로, 재귀의 기초 (base case)라고 한다.
 
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초) - 재귀의 호출이 멈춘다. 
    -> 여기서부터 함수들이 계속해서 반복 실행된다.
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  
  // 4. 이후 복잡한 부분에 대해서 고민해본다.
  /*
  * Recursive Case : base case에 해당 하지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우 = [4]
  * head: 배열의 첫 요소 = 4
  * tail: 배열의 첫 요소만 제거된 배열 = [] => 0
  */
  return head + arrSum(tail); 4 + 0 이 된다. 이후 배열이 head가 3, 2, 1이 되며
  // 4 + 3 + 2 + 1 = 10 이 된다
}

 

잘게 쪼개어 사고하는 법

- 주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다. 일반적인 경우, 입력값으로 이 기준을 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것입니다.

 

재귀적 사고

- 문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다. 이후 단계별로 올라가면서 처리할 방법을 recursive case라고 합니다.

 

함수 자신의 재귀적 호출

- 함수 자신을 재귀적 호출 함으로써 base case까지 가고,  목표하는 지점까지 함수가 반복되며 원하는 값을 얻을 수 있습니다.

 

탈출 조건

- boolean 값으로 탈출할 경우, 충족하는 경우에는 바로 true를 리턴합니다. if 나 for 문 중간 중간에 false 리턴을 넣는 것이 확실해 보일 수는 있지만, 함수 중간에서 recursive case가 들어갈 경우에는 false의 리턴으로 인해서 남은 반복에 대해서 진행이 되지 않을 수 있어, 해당 경우에는 함수의 맨 마지막에 false를 넣어주는 것이 좋습니다.