[완전탐색] 재귀호출

재귀 호출과 완전 탐색

재귀 호출

완전히 같은 코드를 반복해 실행하는 작업을 구현할때 사용 하는 개념. 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지 부분에서 자기 자신을 호출 한다. 예를 들면 자연수 n이 주어 졌을때 1 부터 n까지의 합을 반환하는 sum()이란 함수를 for 문과 재귀함수로 구현해 보자.

//코드 1 부터 n 까지의 합을 계산하는 반복 함수와 재귀 함수
//필수 조건  : n >= 1
//결과 : 1 부터 n 까지의 합을 반환
int sum(int n){
    int ret = 0;
    for(int i = 1; i <= n; i++)
        ret += i;
    return ret;
}
 
//필수 조건 : n >= 1
//결과 : 1 부터 n 까지의 합을 반환한다.
int recursiveSum(int n){
    if(n == 1) return 1;
    return n + recursiveSum(n - 1);
}

모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 되는데 이를 기저사례(base case)라 한다. 

기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경 써야 한다. 

재귀 호출은 기존에 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공한다. 문제의 특성에 따라 재귀 호출은 코딩을 더 간편하게 바꿔준다 

예제 : 중첩 반복문 대체

0부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력 하는 코드를 작성해 보자. 

예를 들면 n = 7이면 (0,1,2,3), (0,1,2,4), (0,1,2,4), ... ,(3,4,5,6) 뭐 이런식으로 출력하는 코드이다. 

for(int i = 0 ; i < n ; i++)
    for(int j = i + 1; j < n; j++)
        for(int k = j + 1; k < n; k++)
            for(int l = k + 1; l < n; l++)
                cout << i << " " << j << " " << k << " " << l << endl;

여기서 만약 5개를 고르면 5중 포문이고, 6개면 6중, ... n 개면 n중 포문을 돌아야된다. 어휴 거지같다 정말로... 이걸 재귀호출로 바꿔보자.

1. 각 조각에 하나의 원소를 고른다

2. 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성한다.

- 이때 남은 원소들을 고르는 '작업'을 다음과 같은 입력 들의 집합으로 정의한다

원소들의 총 개수

더 골라야할 원소들의 개수

지금까지 고른 원소들의 번호

//코드 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
 
//n : 전체 원소의 갯수
//picked : 지금까지 고른 원소들의 번호
//toPick : 더 고를 원소의 수
// 일 떄, 앞으로 toPick 개의 원소를 고르는 모든 방법을 출력
 
void pick(int n , vector<int>& picked, int toPick){
    //기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력
    if(toPick == 0) { printPicked(picked); return ;}
    //고를 수 있는 가장 작은 번호를 계산
    int smallest = picked.empty() ? 0 : picked.back() + 1;
    //이 단계에서 원소 하나를 고른다
    for(int next = smallest; next < n; next++){
        picked.push_back(next);
        pick(n, picked, toPick - 1);
        picked.pop_back();
    }
}

코드를 찬찬히 살펴 보도록 하자 . 입력 부분엔 전체 n개의 원소, picked이라는 선택된 원소를 담는 주머니, 그리고 toPick이라는 선택된 원소의 개수의 입력을 받는데 이는 수학에서 n개중 r개의 원소를 뽑는 nCr 의 조합의 수를 구하는 것과 같은 알고리즘인 셈이다.

그럼 기저사례를 보면 선택된 원소의 개수가 r개만큼 뽑았다면 picked에 담긴 원소들을 출력한다.

가장 작은 번호를 선택 후 for 문에서 n을 넘지 않을때까지 재귀호출 한다.

<소스코드>

https://github.com/JayStevency/Algorithm-Algospot/tree/master/6.Brute-force/NESTEDLOOP