자료구조/알고리즘 - 재귀

학습 내용

* 재귀의 의미, 자바스크립트에서 재귀 호출
* 언제 재귀를 사용해야 하는가
* 재귀적 사고 연습을 통해 재귀함수를 base case와 resursive case로 나눠 작성하기
* Tree 구조에 재귀 함수를 사용해야 하는 이유 이해
- 실생활에 사용되는 유용한 Tree 구조
- 깊이를 알 수 없는 Tree 구조에 재귀 함수를 이용하여 모두 순회하기

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

하나의 문제를 해결하기 위해 다양한 방식으로 생각하는 능력을 기르는 것

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

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

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


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

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

이 함수를 재귀의 과정으로 보자

 

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

arrSum에 적용할 문제를 더 작게 쪼갠다

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

 

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

가장 작은 단위까지 쪼개는 것

arrSum([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;

 

이런 로직을 정리하면 다음과 같다

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

이를 js코드로 구현한다면 함수 arrSum은 (인자가 빈배열이 아닌 경우) 실행 과정 중에 자기 자신을 호출함
→ 이 호출 방식이 “재귀 호출”

재귀는 언제 사용?

* 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수(쪼갤 수) 있는 경우

* 중첩된 반복문이 많거나 반복문의 중첩 횟수(loop 횟수)를 예측하기 어려운 경우

모든 재귀 함수는 반복문으로 표현할 수 있지만 이 경우 아주 지저분해지고 코드가 복잡해짐
→ 재귀는 알고리즘 문제의 많은 부분을 차지하므로 이 부분에 대한 기초를 잘 다져야 한다!

 

재귀적 사고 연습하기

재귀 함수의 입력값과 출력값 정의

먼저, 문제를 가장 추상적으로(단순하게) 정의하기
→ 이를 위에서 본 함수 arrSum에 대응하면

입력값: number 타입을 요소로 가지는 배열
출력값: number 타입(숫자)을 리턴

`arrSum: [number] => number`

 

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

이제, 문제를 어떻게 쪼갤지 고민해야 한다. 이를 위해 문제를 쪼갤 기준을 정해야 함

일반적인 경우 “입력값”으로 이 기준을 정하는 데, 중요한 점은 “입력값이나 문제의 순서와 크기” 이다
→ 크기를 기준으로 구분 가능하거나, 순서를 명확히 정할 수 있다면 문제를 쪼개는데 도움이 됨
→ 이렇게 구분된(쪼갠) 문제를 푸는 방식이 모두 동일하다면(순서, 크기에 관계 없이) 문제를 제대로 쪼갠(구분)한 것

ex) 함수 arrSum은 입력값인 배열의 크기에 따라 문제를 쪼갤 수 있음

 

다음으로 주어진 입력값에 따라 경우의 수를 생각해야 함
→ 일반적으로 “문제를 더 이상 쪼갤 수 없는 경우”와 “그렇지 않은 경우”로 구분 가능

ex) 함수 arrSum의 경우 입력값이 빈 배열인 경우와 그렇지 않은 경우로 구분하여 각각 다른 방식으로 처리

 

단순한 문제부터 해결하기

문제를 여러 경우로 구분한 다음, “가장 해결하기 쉬운 단순한 문제”부터 해결하자
→ 이 case를 “재귀의 기초(base case)” 라 함
→ 재귀의 기초는 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성함

ex) 함수 arrSum의 경우, base case는 입력값이 빈 배열인 경우이고, 이 경우 arrSum([])의 리턴값은 0

 

복잡한 문제 해결하기

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

ex) 길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 
맨 앞의 요소(head)에 대한 결과를 따로 구하고, \
나머지 요소를 새로운 입력값으로 갖는 문제로 구분한 다음 이를 해결하여 얻은 결과를 head에 더한다

이를 수도코드로 보면

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, ...)
}

 

factorial(!)로 알아보는 재귀

재귀: 어떤 함수가 스스로를 호출하는 것

팩토리얼을 살펴 보면
5!= 5* 4!
   =5*4*3!

이를 코드화 해서 보자

function fac(n){
    if(n===1){    //base  case
        return 1;    
    }
    // 그렇지 않은 경우(recursive case)
    //가장 맨 처음 요소를 나두고 문제를 쪼갠다
    return n*fac(n-1);        // 자기 자신을 계속 호출하는 과정(재귀)

}