[Algorithm] 재귀의 이해

 

 

 

 

 

 

재귀

어떤 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법

재귀를 사용한 코드는 대부분 더욱 간결하고, 이해하기 쉬움

 

• 재귀적으로 사고하는 법
  • 잘게 쪼개어 사고하는 법
  • 재귀적 사고
  • 함수 자신의 재귀적 호출
  • 탈출 조건
• 재귀 함수의 활용 (트리 구조)
  • 트리 구조에 재귀 함수를 활용
  • JSON 구조에 재귀 함수를 활용
  • DOM 구조에 재귀 함수를 활용

 

 

 

 

---

 

재귀의 이해 - 다르게 생각하기

문제. 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 `arrSum` 을 작성

답

자연수로 이루어진 리스트(배열)의 합을 구하는 알고리즘

1. 보조 변수 sum을 0으로 초기화한다.
2. 순차적으로 리스트(배열)의 구성요소에 접근하면서 sum에 더한다.

//자연수로 이루어진 리스트(배열)의 합을 구하는 arrSum
function arrSum(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i]; } return sum; }

• 재귀적으로 구성한 알고리즘

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;

 

 

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

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

 // arrSum에 적용할 문제를 더 작게 쪼개기
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; // <-- 문제가 더는 작아지지 않는 순간 // 가장 작은 경우의 해결책을 적용한다. 
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 을 보다 엄밀하게(formally) 정의할 수 있다.

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

 

 

 

 

---

재귀는 언제 사용하는 게 좋을까?

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

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

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

 

• 모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현가능하다
• 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉬움
• 이 밖에도, 재귀는 알고리즘 문제의 많은 부분을 차지

 

---

재귀적으로 사고하기

 

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

• 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것

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

arrSum: [number] => number

 

 

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

• 입력값이나 문제의 순서와 크기를 기준으로 주어진 문제를 어떨게 쪼갤 것인지 고민
• 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같으면, 문제를 제대로 구분한 것

 

 

3. 단순한 문제 해결하기

• 문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결
• : 재귀의 기초(base case)
• 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성
• 함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0.
• arrSum: [number] => number
  arrSum([ ]) = 0
  arrSum([e1, e2, ... , en])

 

 

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(head), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 합한다
• arrSum: [number] => number
  arrSum([ ]) = 0
  arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])

 

 

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. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}