재귀 함수란 정의 단계에서 자신을 재참조 하는 함수를 의미. 주로 문제를 작은 부분으로 나누어서 풀 때 활용한다.
대표적인 예시로 펙토리얼과 피보나치 수열이 존재한다.
#include <iostream>
using namespace std;
int factorial(int n){
if (n == 0 || n == 1) return 1;
return n * factorial(n-1);
}
int main(){
cout << "Factorial" << endl;
cout << factorial(5) << endl << endl;
}
재귀함수를 사용하는 경우 반드시 종료조건을 달아 주어야 하며, 사이클이 존재하는 경우 사용해서는 안된다.
또한 반복문으로 가능한 경우, 반복문이 함수 호출에 대한 cost를 save할 수 있어서 유리하다.
서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열이라고 한다.
순열의 식은 아래와 같다.
next_permutation() 함수를 사용해서 간단하게 순열을 구현할 수 있다.(algorithm 라이브러리에 있음)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
cout << "Permutation" << endl;
vector<int> v;
for(int i : a) v.push_back(i);
do{
cout << v[0] << v[1] << v[2] << endl;
}while(next_permutation(v.begin(), v.end()));
cout << endl;
do{
cout << v[0] << v[1] << v[2] << endl;
}while(next_permutation(v.begin(), v.begin() + 2)); // 앞에 두개만 고치게 된다.
cout << endl;
cout<< "unsorted case" << endl;
int b[3] = {2,1,3};
v.clear();
for ( int i : b) v.push_back(i);
do{
cout << v[0] << v[1] << v[2] << endl;
}while(next_permutation(v.begin(), v.end())); // 그 다음번째 순열을 만들어내기 때문에 정렬되지 않은 상태로 진행하면 문제가 발생할 수 있다.
cout<< endl;
sort(v.begin(), v.end());
do{
cout << v[0] << v[1] << v[2] << endl;
}while(next_permutation(v.begin(), v.end()));
cout<< endl;
}
이때 유의할 점은 반드시 정렬을 진행하고 사용해야 한다는 점이다.
next_permutation() 함수는 그 다음번째 순열을 만들어주는 함수 이기에, 정렬을 진행하지 않고 진행한다면, 우리가 원하지 않는 결과를 얻을 수도 있다.
배열에 대해서 진행하는 경우 다음과 같이 구현 가능하다.
do{
cout<< a[0] << a[1] << a[2] << endl;
}while(next_permutation(&a[0], &a[3]));
do{
cout<< a[0] << a[1] << a[2] << endl;
}while(next_permutation(&a[0], &a[0] + 3));
do{
cout<< a[0] << a[1] << a[2] << endl;
}while(next_permutation(a, a + 3)); // 위의 세개 모두 동일한 코드. 항상 시작 주소, 마지막 주소 +1 로 넣어주면 된다.
cout << endl;
아래와 같은 방법으로 직접 재귀함수를 만들어 주는 방법도 가능하다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[3] = {1,2,3};
void makePermutation(int n,int r, int depth){
if( r == depth) {
cout << a[0] << a[1] << a[2] << endl;
}
for(int i = depth; i < n; i++){
swap(a[i], a[depth]);
makePermutation(n,r, depth + 1);
swap(a[i], a[depth]);// 원본으로 회귀
}
}
int main(){
cout << "Permutation with Recur" << endl;
makePermutation(3,3,0);
}
포인트는 재귀 함수를 호출 한 뒤에 호출하기 전으로 되돌려준다는 점이다.
depth가 증가함에 따라 시작점 증가, 시작 점 다음 부터 한칸씩 swap해 나가는 구조이다.
출력되는 순서를 생각해보면
123 >> 132 >> 213 >> 231 >> 321 >> 312 순이다.
서로 다른 원소를 가진 집합에서 원소들을 택하여 만든 부분집합을 조합이라 부른다.
조합의 식은 아래와 같다
다음과 같이 구현 가능하다.
#include <iostream>
#include <vector>
using namespace std;
int n = 5, k=3, a[5] = {1,2,3,4,5};
void print(vector<int> &v){
for(int i : v) cout << i;
cout << endl;
}
void combination(int n , int k, int start , vector<int> &b){// 이렇게 계속 레퍼런스로 타고 들어가도 되는건가?
if(b.size() == k){
print(b);
return;
}
for(int i = start + 1; i < n ; i++){
b.push_back(a[i]);
combination(n,k, i, b);
b.pop_back();
}
return;
}
int main(){
vector<int> b;
combination(n, k, -1, b);
return 0;
}
출력되는 순서를 고려해 보면
123 >> 124 >> 125 >> 134 >> 135 >> 145 >> 234 >> 235 >> 345 순으로 출력된다.
순열과 조합 모두 코딩 테스트에서 요긴하게 쓰일 수 있으니 기억해 두는 것이 좋다. 특히 순열을 재귀함수를 이용하여 구현하는 것은 로직이 복잡하니 자주 복기해주는 것이 좋을 것 같다.