(작성 중) [C++/Algorithm] 재귀(recursion)

1. 재귀 호출(recursive call)이란?

작업 중에 자기 자신을 호출하는 것을 재귀호출(recursive call)이라고 하고, 재귀 호출을 하는 함수를 재귀 함수(recursive function)이라고 한다.
감이 잘 오지 않는다면 1부터 N까지의 합을 구하는 다음의 코드를 간단하게 알아보자.

int sum(int N) {
	if (N==0) reutrn 0;
    else 
    	return N + sum(N-1);
}

1) 재귀 함수의 구성 요소

//재귀 함수 템플릿
(반환값형) func(인수) {
	if(베이스 케이스) { 
    	return 베이스 케이스에 해당하는 값;
    }
    
    //재귀 호출
    func(다음 인수);
    return 응답;
}

재귀 함수의 베이스 케이스란 종료조건과 같다. '베이스 케이스에 대한 처리'가 굉장히 중요한 게, 만약 베이스 케이스일때 0을 리턴하거나 빠져나가는 처리를 하지 않으면 재귀호출을 무한반복하게 되기 때문이다.
또 다른 주의점은 '재귀호출을 할 때 인수가 베이스 케이스에 가까워지냐'이다. 예컨대 위의 코드에서 sum(N-1)이 아닌 sum(N+1)이라면, 재귀 호출하는 인수가 6, 7, 8...로 점점 늘어나 0에 수렴하지 못해 종료되지 못할 것이다.

2. 재귀 사용 예

1) 유클리드 호제법

재귀 함수를 이용하여 명쾌하게 서술 가능한 알고리즘의 예로는 유클리드 호제법이 있다.(Euclidean algorithm)
유클리드 호제법은 두 정수 m, n의 최대공약수 GCD(m,n)을 구하는 알고리즘이다. 이는 다음의 성질을 이용한다.

GCD(m, n) = GCD(n, m%n);

이 성질을 이용하면 다음과 같은 절차로 m, n의 최대공약수를 구할 수 있다:

1. m을 n으로 나눈 나머지를 r이라고 한다.
2. r = 0 이면, 이 시점에서  n이 구하는 최대 공약수이므로 n을 리턴하고 종료한다.
3. r != 0 이면, m ← n, n ← r로 지정하고 1번으로 돌아간다.

정말 간단하지 않은가! 이 유클리드 호제법의 복잡도는 m>=n>0이면, O(lgn)이다. 매우 빠른 알고리즘이 되는 것이다.

#include <iostream>
using namespace std;

int gcd(int m, int n) {
	//베이스 케이스
	if(n == 0) return m;
    else {
    	// 재귀 호출
    	return gcd(n, m%n);
        }
}

int main() {
	cout << gcd(51, 15) << '\n'; //3출력
    cout << gcd(15, 51) << '\n'; //3출력
}

2) 피보나치 수열

피보나치 수열이란 F_n = F_n-1+F_n-2를 만족하는 수열이다.
F_0 = 0, F_1 = 1이다.

3) 부분 합 문제

부분 합 문제
$N$ 개의 양의 정수 $a_0, a_1, ... a_{n-1}$ 과 양의 정수 $W$ 가 주어졌을 때,
$a_0, a_1, ... a_{n-1}$ 에서 정수를 몇 개 골라 그 합이 $W$가 될 수 있는지 확인하라.

다음과 같은 문제를 재귀적으로 설계하면, 두 가지 케이스로 나눌 수 있다.

1) $a_{n-1}$ 을 선택할 때

▶ $N-1$ 개의 양의 정수 $a_0, a_1, ... a_{n-2}$ 과 양의 정수 $W-a_{n-1}$ 을 만들 수 있는지 여부

2) $a_{n-1}$ 을 선택하지 않을 때
▶ $N-1$ 개의 양의 정수 $a_0, a_1, ... a_{n-2}$ 과 양의 정수 $W$를 만들 수 있는지 여부

와 같은 부분 문제로 나누어 설계할 수 있다.
둘로 나눈 부분 문제에서 적어도 한쪽이 Yes라면 원래 문제의 답도 Yes이고, 둘 다 No라면 원래 문제의 답도 No가 된다.

부분 합을 푸는 재귀 함수
bool func(int i, int w) ← $a_0, a_1, ... a_{n-1}$ 범위 에서 최초 $i$개($a_0, a_1, ... a_{n-1}$) 중 몇 개를 골라 총합이 $w$가 되는지 bool형으로 돌려주는 함수

이때 최종 답은 $func(N, W)$가 된다.
일반적으로 $func(N,W)$의 값은
$func(N-1, W)$ 나 $func(N-1, W-a_{n-1})$의 값이 true가 될 때 true가 된다.

3) 부분 합 문제를 재귀 함수를 이용해서 전체 탐색으로 풀기

#include <iostream>
#include <vector>
using namespace std;

bool func(int i, int w, const vector<int> a) {
	//베이스 케이스
    if (i == 0) {
    	if (w == 0) return true;
    	else return false;
   }
   
   //a[i-1]을 선택하지 않음
   if(func(i-1, w, a)) return true;
   
   //a[i-1]을 선택
   if(func(i-1, w-a[i-1], a)) return true;
   
   //둘 다 false라면 false를 리턴 
   else return false;
}

int main() {
	int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for(int i =0 ; i < N; i++) cin >> a[i];
    
    //재귀적으로 풀기
    if(func(N, W, a)) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}