재귀함수(Recursive Function)

재귀함수는 기본적으로 반복적으로 함수를 호출해서 많은 메모리를 차지하면서 함수 stack을 통해 메모리에 부담을 주는 것으로 알려져있다. 그럼에도 불구하고 재귀함수를 사용하는 이유는 명확하다.

 

알고리즘 자체가 재귀적으로 표현이 더욱 쉬울 때가 존재한다.

 

예를 들어 팩토리얼을 구하는 공식을 살펴보면 다음과 같다.

해당 공식을 보면 n! = (n-1)! * n (n>0) 이 부분 자체가 재귀함수의 형태와 매우 닮아있다.

그래서 몇몇 알고리즘을 계산하는데 있어, 재귀함수가 유용할 때가 존재한다.

 

재귀함수를 사용할 때 주의해야할 3가지가 있다.

1) 종료조건(실패조건) : 재귀함수 호출 중 조건에 벗어나 그만 호출해야할 때

2) 종료조건(성공조건) : 재귀함수 호출 중 조건을 만족한 답을 구해서 그만 호출해야 할 때

3) 위 두가지를 제외한 모든 경우 : 재귀함수를 계속 호출해야 할때

 

이러한 주의점에 따라 알고리즘을 잘 설계하며 문제를 해결해야 한다.

 

1. 1, 2, 3 더하기 

문제참고 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

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

int func(int, int);

int main() {
	
	int cnt;
	cin >> cnt;

	// 입력받기
	for (int i = 0; i < cnt; i++) {
		int n;
		cin >> n; 
		cout << func(0, n)<<"\n"; // 함수 호출
	}
}

// 함수정의
int func(int sum, int goal) {
	
	// 탈출조건
	if (sum > goal)
		return 0;

	// 완성조건
	if (sum == goal)
		return 1;

	// 세가지 경우
	int now = 0;
	for (int j = 1; j <= 3; j++)
		now += func(sum + j, goal); // 현재 경우의 수에 더하기
	return now;
}

2. 암호 만들기

문제 참고 : https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

풀이

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

void make_pw(int, vector<char>, string,int);
bool check(string&);

int main() {
	int l, c;
	cin >> l >> c; // 입력
	vector<char> alpha(c);
	string pw = "";

	// 입력받기
	for (int i = 0; i < c; i++)
		cin >> alpha[i];
	sort(alpha.begin(), alpha.end()); // 정렬

	// 호출
	make_pw(0, alpha, pw, l);

}
// 암호 만들기
void make_pw(int idx, vector<char> alpha, string pw, int l) {
	
	// 완성 조건
	if (pw.size() == l) {
		if(check(pw))
			cout << pw << "\n";// 출력
		return;
	}

	// 종료 조건
	if (idx >= alpha.size())
		return;

	// 계속 진행
	make_pw(idx + 1, alpha, pw + alpha[idx], l); // 넣기
	make_pw(idx + 1, alpha, pw, l); // 안넣기

}
// 조건 체크
bool check(string &password) {
	int ja = 0;
	int mo = 0;
	for (char x : password) {
		if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x ==
			'u') {
			mo += 1;
		}
		else {
			ja += 1;
		}
	}
	return ja >= 2 && mo >= 1;
}

3. 로또 

문제 참고 : https://www.acmicpc.net/problem/6603

6603번: 로또

풀이

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

void make_lotto(vector<int>, vector<int>, int, int);

int main() {
	// 입력받기
	while (true) {
		int n;
		cin >> n;

		// 종료
		if (n == 0)
			break;

		// 벡터 선언
		vector<int> lotto(n); // 입력받기
		vector<int> make(0); // 만들어가기

		// 입력
		for (int i = 0; i < n; i++)
			cin >> lotto[i]; 

		// 로또 만들기
		make_lotto(lotto, make, 0, 0);
		cout << "\n";
	}

	return 0;
}
// 로또 만들기 함수
void make_lotto(vector<int> lotto, vector<int> make, int idx, int cnt) {

	// 성공조건
	if (cnt == 6) {
		for (int i = 0; i < 6; i++)
			cout << make[i]<<" "; // 출력
		cout << "\n";
		return;
	}

	// 종료조건
	if (idx >= lotto.size())
		return;
	
	// 그외 호출
	make.push_back(lotto[idx]); 
	make_lotto(lotto, make, idx + 1, cnt+1); // 넣기
	make.pop_back();
	make_lotto(lotto, make, idx + 1, cnt); // 안넣기
}

4. 부분 수열의 합

문제 참고 : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

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

int make_part(vector<int>, int, int, int);

int main() {
	int n, s, ans;
	cin >> n >> s; // 입력받기

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i]; // 입력받기

	ans = make_part(arr, 0, 0, s);
	if (s == 0)
		ans--;// 공집합 빼기

	cout << ans;
	return 0;
}

int make_part(vector<int> arr, int idx, int sum, int goal) {

	// 완성 조건
	if (sum == goal && idx == arr.size()) 
		return 1;

	// 실패 조건
	if (sum != goal && idx == arr.size())
		return 0;

	// 그 외 실행
	int now = 0;
	now += make_part(arr, idx + 1, sum + arr[idx], goal); // 넣기
	now += make_part(arr, idx + 1, sum, goal); // 안넣기
	return now;
}

5. 퇴사

문제 참고 : https://www.acmicpc.net/problem/14501

14501번: 퇴사

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int vmax = 0;

void quit_work(vector<int>, vector<int>, int, int);
int main() {
	int n;
	cin >> n; // 입력받기

	vector<int> T(n), P(n);
	for (int i = 0; i < n; i++)
		cin >> T[i] >> P[i]; // 입력받기

	quit_work(T, P, 0, 0);
	cout << vmax;
}

void quit_work(vector<int> T, vector<int> P, int idx, int sum) {
	// 실패조건
	if (idx > T.size()) {
		return;
	}

	// 성공조건
	if (idx == T.size()) {
		// max값 비교
		if (sum > vmax)
			vmax = sum;
		return;
	}

	// 그외 들어가기
	quit_work(T, P, idx + T[idx], sum + P[idx]); // 하기
	quit_work(T, P, idx + 1, sum); // 안하기
}

6. 연산자 끼워넣기

문제 참고 : https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int vmax = -10000000000;
int vmin = 10000000000;

void make_check(vector<int>, int, int,int,int,int,int);

int main() {
	int n;
	cin >> n; // 입력받기

	vector<int> arr(n), opt(4);
	for (int i = 0; i < n; i++)
		cin >> arr[i]; 

	int p, m, m2, d;
	cin >> p >> m >> m2 >> d;

	make_check(arr, 1, arr[0], p, m, m2, d);
	cout << vmax << "\n" << vmin << "\n";
}

void make_check(vector<int> arr, int idx, int sum, int plus, int minus, int mul, int div) {
		
	// 완성 조건
	if (idx == arr.size()) {
		// 최대 체크
		if (vmax < sum)
			vmax = sum;

		// 최소 체크
		if (vmin > sum)
			vmin = sum;

		return;
	}

	// 사칙연산(+ - * /)
	if (plus>= 1) {
		make_check(arr, idx + 1, sum + arr[idx], plus-1,minus, mul,div);
	}
	if (minus >= 1) {
		make_check(arr, idx + 1, sum - arr[idx], plus, minus-1, mul, div);
	}
	if (mul >= 1) {
		make_check(arr, idx + 1, sum * arr[idx], plus, minus, mul-1, div);
	}
	if (div >= 1) {
		make_check(arr, idx + 1, sum / arr[idx], plus, minus, mul, div-1);
	}
}