Data Structure TIL 01

2021년 7월 20일에 작성된 문서 1번 입니다.
자료 구조 배운 내용을 정리했습니다.

재귀 : 문제를 쪼개어 생각하는 방법

문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법

재귀의 과정을 arrSum에 적용하면, 다음과 같습니다.

1. 기존의 문제에서 출발하여 더 작은 경우를 생각한다.

   arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
   //arrSum에 적용할 문제를 더 작게 쪼갠다

2. 같은 방식으로, 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.

   arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
   arrSum([6, 2]) = 6 + arrSum([2]);
   arrSum([2]) = 2 + arrSum([]);
   //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;
   		//가장 작은 단위부터 arrSum을 적용하여 문제를 푼다.

   
   
   
   

다음과 같이, arrSum 을 보다 엄밀하게(formally) 정의할 수 있습니다.

/* 
 * 함수 arrSum의 엄밀한 정의
 * 1. arr이 빈 배열인 경우 = 0
 * 2. 그 외의 경우 = arr[0] + arrSum(arr2)
 *   (arr2는 arr의 첫 요소를 제외한 나머지 배열)
 */
arrSum(arr);

재귀 호출 : 함수 arrSum 을 JavaScript 코드로 구현할 경우 실행과정 중에 자기 자신을 호출한다.

재귀를 사용하는 경우

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

Written with StackEdit.