[알고리즘] 재귀(Recursion) 개념 이해

발상의 전환

 

해결해야할 문제가 있다

이 문제의 솔루션을 생각할 때 

동일한 구조의 더 작은 문제로 분해해서, 그 작은 문제를 해결함으로써 

전체 문제의 솔루션을 도출해낼 수 있는 방법을 재귀(recursion)이라고 한다

재귀 코드는 작게 분해해놨기 때문에 대부분 간결하고 이해하기 편하다는 장점이 있다 


본격적으로 배우기 전에 문제 하나를 가져와서 생각을 해보자

Q1) 자연수로 이루어진 리스트(배열)을 입력받고, 리스트의 합을 리턴하는 메소드 'arrSum'을 작성하라

우선 메소드 정의부터 선언해줄 필요가 있다

public int arrSum(int[] arr) {

}

 

arrSum은 int 타입, arrSum은 int 타입의 arr 배열을 매개변수로 가질 것이다

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

 

메소드의 동작 방식을 써내려 가기 위해 sum이라는 int 타입의 변수를 0으로 초기화
for문을 이용해,  int 타입 i가 0부터 배열 전체 길이까지 1씩 증가하며 
sum에 arr[i]를 더해 할당하고
그 sum을 return 한다

그러면 i가 0부터 배열 전체 길이까지 1씩 증가하며 배열의 구성요소에 접근해 sum에 더하는 구조가 된다


예를 들어, 자연수로 이루어진 리스트(배열) [10, 4, 7, 3] 합을 구한다고 생각해보면
이걸 잘게 분해할 수 있고 코드로 표현한다면 이렇게 된다

arrSum([10, 4, 7, 3]) = 10 + arrSum([4, 7, 3]);
arrSum([4, 7, 3]) = 4 + arrSum([7, 3]);
arrSum([7, 3]) = 7 + arrSum([3]);
arrSum([3]) = 3 + arrSum([]);
arrSum([]) = 0;

 

더이상 분해되지 않을 때 까지 세분화 한다

그러고나서 작은 문제부터 풀어나가는 방식으로
작은 문제를 보다 위의 문제에 대입하며

결국
동일한 구조의 더 작은 문제를 해결하면서 전체를 풀어나간다
이 방법을 재귀 라고 하는 것이다

arrSum 메소드를 예시로 들었는데 
저렇게 분해된 작은 문제 풀고 그 위 문제에 자기 자신을 호출하게 되는데 
이 호출 방식을 재귀 호출 이라고 한다

보다보니까 반복문과 매우 유사한 것을 알 수 있는데
실제로 모든 재귀함수는 반복문으로 표현할 수 있다

그렇지만 재귀를 적용할 수 있는 상황이면 재귀 적용하는 것이 코드가 간결해지는 길이다

그렇다면 이러한 재귀적 사고는 어떤 식의 흐름을 가질까 ?

가장 먼저해야할 일은 역시 간결하게 단순하게 추상화 시키는 것이다

위에 arrSum의 경우는 int 타입을 요소로 갖는 배열을 입력받고 int 타입을 리턴했는데

arrSum: [int] -> int 

이렇게 표현할 수 있다

이렇게 추상화를 했다면, 이제는 문제를 분해하고 경우의 수를 나누는 것도 필요하다

분해할 기준을 정하고 그 기준에 따라 문제가 더 큰 경우와 작은 경우로 구분할 수 있는지 여부를 확인하는데

일반적으로 입력값을 기준으로 정한다

그러면 중요 포인트는 입력값, 문제의 순서, 크기

주어진 입력값이나 문제 상황을 크기로 구분할 수 있거나 또는 순서를 명확하게 알 수 있고 정할 수 있으면 
문제를 구분하는데 도움이 된다

그렇게 구분한 문제를 푸는 방식이 순서, 크기에 관계 없이 같다고 한다면
그건 분명히 제대로 구분한 것이라고 말할 수 있다

위에서 본 것 처럼 arrSum은 입력값이 리스트(배열)의 크기에 따라 더 작게 분해할 수 있다
그리고 분해했고, 더 분해할 수 있는 경우와 아닌 경우로 나눈다

그러니 더이상 분해할 수 없는 빈배열의 경우와 그렇지 않은 경우는 각각 다른 방식으로 처리하면 된다
arrSum의 빈배열은 arrSum(new int[]{}) 
그렇지 않은 경우 arrSum(new int[]{e1, e2, ..., en}

이렇게 구분한 뒤에는 제일 해결하기 쉬운 문제부터 접근해 해결한다 
이것을 재귀의 기초(base case) 라고 한다
나중에 재귀함수를 구현할 때 재귀 탈출 조건을 구성하는데 필요하다

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

그러니까 다시 말해 빈배열의 경우는 처리했다고 하고 

arrSum: [number] => numberarrSum(new int[]{}) = 0

 

나머지 길이가 존재하는 배열이 arrSum에 입력된 경우
맨 앞 요소에 대한 결과를 구한 뒤에 (맨 앞 요소를 head라고 해보자)
나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이걸 해결해서 얻은 결과를 head에 더한다

arrSum([e1, e2, ... , en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}

 

코드로 표현해보는게 더 이해가 빠르니까 해보면

public int arrSum(int[] arr) {
  //Base Case : 문제를 더 이상 분해할수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
  /*
  * recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 분해할 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return head + arrSum(tail);
}

이걸 이제 템플릿화 시키면 이렇게 된다

public type recursive(input1, input2, ...) {
  // Base Case
  if (문제를 더 이상 분해할 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case

     return 더 작은 문제로 새롭게 정의된 문제
  // ex1) someValue + recursive(input1Changed, input2Changed, ...)
  // ex2) someValue * recursive(input1Changed, input2Changed, ...)
}