(1-1) [자료구조/알고리즘] - 재귀 함수

 

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

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

 

 

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) 정의할 수 있다.

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

[코드] 함수 arrSum의 엄밀한 정의

 

만약 함수 arrSum 을 JavaScript 코드로 구현할 경우, 함수 arrSum 은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출한다. 이러한 호출 방식을 재귀 호출이라고 한다.

 

 

예제

예제로 재귀의 사용법에 대해 알아보자. factorial로 예를 들어보겠다. 5! (5 factorial) = 5 * 4 * 3 * 2 * 1 이다.
즉 n! (n factorial)은 n 부터 1까지 곱하는 연산을 의미한다. 이것을 재귀적으로 생각해본다면 

5!  은

5 * 4!

5 * 4 * 3!

5 * 4 * 3 * 2!  과 같이 나눌 수도 있다. 이를 이용해 factorial 을 계산하는 함수를 만들 수도 있다. 이를 코드로 작성해보자.

 

function Fac(n){
  if (n === 1) return 1;
  return n * Fac(n-1);
}

 

 

이의 실행 과정은 다음과 같다.

 

Fac(4) = return 4 * Fac (3)

                                  return 3 * Fac(2)

                                                    return 2 * Fac(1)

                                                                      return 1

                                                    return 2 * 1

                                   return 3 * 2 

                    return 4 * 6

Fac(4) = 24 

 

이처럼 함수 내에서 자기 자신을 계속 호출하는 과정(재귀) 를 거쳐, 실행 결과는 24 가 된다.