[0x0B] 재귀

모든 입력은 base condition으로 수렴해야 한다.

 

인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.

 

모든 재귀 함수는 반복문만으로 동일한 동작을 할 수 있다.

반복문으로 구현했을때에 비해 코드가 간결해지지만 메모리와 시간에서 손해를 본다.

 

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.

 

재귀함수를 절차적으로 계속 따라들어가며 생각하면 답이없다. 절차지향적인 사고를 탈피해야 한다.

 

재귀함수 예제문제들을 풀어보니 문제에 귀납적인 내용이 적혀있다. 이걸 토대로 구현하면 될 것 같다.

작거나 큰 문제를 확장시키거나 쪼개간다는 점에서 DP와 개념은 비슷한데 memoization이 사용되지 않는다는 점이 차이인 것 같다.

 

연습 문제

 

1629: 곱셈

#include <iostream>

using namespace std;
using ll = long long;

ll powmod(ll a, ll b, ll c)
{
	if (b == 1) return a % c;

	ll val = powmod(a, b / 2, c);
	val = val * val % c;

	if (b % 2 == 0) return val;
	else return val * a % c;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	ll a, b, c;

	cin >> a >> b >> c;

	cout << powmod(a, b, c);
	
	return 0;
}

 

a^b = a^b/2 * a^b/2

(a*b)%c = (a%c)*(b%c)%c

위 두개를 알아야 한다. 그리고 b가 홀수인 경우 a를 한번 더 곱해줘야 한다는 걸 주의해야 한다.

큰 문제를 작은 문제로 쪼개서 해결한다는 점에서 뭔가 DP랑 유사한 것 같다.

 

11729: 하노이 탑 이동 순서

#include <iostream>

using namespace std;

void tower_of_hanoi(int n, int start, int dest)
{
	if (n == 1)
	{
		cout << start << " " << dest << '\n';
		return;
	}

	tower_of_hanoi(n - 1, start, 6 - start - dest);
	cout << start << " " << dest << '\n';
	tower_of_hanoi(n - 1, 6 - start - dest, dest);
	return;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;

	cin >> n;

	cout << (1 << n) - 1 << '\n';
	tower_of_hanoi(n, 1, 3);
	
	return 0;
}

 

n이 성립되면 n-1도 성립되는것을 이해해야 한다.

n-1을 2번, n을 3번, n-1을 3번으로 옮긴다는 것을 알면 금방 풀 수 있는 문제이다.

즉, 귀납적 사고법이 반드시 필요한 문제.

 

1074: Z

#include <iostream>

using namespace std;

int z_search(int n, int r, int c)
{
	if (n == 0)	return 0;

	int half = 1 << (n - 1);

	if (r < half && c < half) return z_search(n - 1, r, c);
	else if (r < half && c >= half) return half * half + z_search(n - 1, r, c - half);
	else if (r >= half && c < half) return 2 * half * half + z_search(n - 1, r - half, c);
	else return 3 * half * half + z_search(n - 1, r - half, c - half);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	// r행 c열
	int n, r, c;

	cin >> n >> r >> c;

	cout << z_search(n, r, c);
	
	return 0;
}

 

재귀의 n값마다 행과 열의 사분면을 파악해서 재귀 호출이 달라져야한다.

예를들어 3사분면에 있다면 1-2분면의 값을 모두 더하고 나머지값은 더 작은 사분면으로 판단시키기 위해 값을 조정하여 재귀를 호출한다.

n=1일때의 사분면 판정을 생각하면 확장이 쉽다.

 

기본 문제

 

1780: 종이의 개수

#include <iostream>

using namespace std;

int paper[2200][2200];
int cnt[3];

bool same_paper_judge(int x, int y, int n)
{
	int t = paper[x][y];

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (t != paper[x + i][y + j])
			{
				return false;
			}
		}
	}

	return true;
}

void recursion(int x, int y, int n)
{
	if (same_paper_judge(x, y, n))
	{
		cnt[paper[x][y] + 1]++;
		return;
	}

	int div = n / 3;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			recursion(x + div * i, y + div * j, div);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> paper[i][j];
		}
	}

	recursion(0, 0, n);

	for (int i = 0; i < 3; ++i)
	{
		cout << cnt[i] << '\n';
	}
	
	return 0;
}

 

9개로 나누어 분할정복 하는것이 포인트

 

1992: 쿼드 트리

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string quad[65];
vector<char> answer;

bool same_judge(int x, int y, int n)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (quad[x][y] != quad[x + i][y + j])
			{
				return false;
			}
		}
	}

	return true;
}

void quad_tree(int x, int y, int n)
{
	if (same_judge(x, y, n))
	{
		answer.push_back(quad[x][y]);
		return;
	}
	int div = n / 2;

	answer.push_back('(');

	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			quad_tree(x + div * i, y + div * j, div);
		}
	}
	answer.push_back(')');
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> quad[i];
	}

	quad_tree(0, 0, n);

	for (auto& a : answer)
	{
		cout << a;
	}
	
	return 0;
}

 

4개로 분할 정복 하면서 중간에 괄호를 끼워넣는게 포인트

 

2630: 색종이 만들기

#include <iostream>

using namespace std;

int paper[128][128];
int answer[2]; // 흰0 파1

bool same_judge(int x, int y, int n)
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (paper[x][y] != paper[x + i][y + j])
			{
				return false;
			}
		}
	}

	return true;
}

void recursion(int x, int y, int n)
{
	if (same_judge(x, y, n))
	{
		answer[paper[x][y]]++;
		return;
	}
	int div = n / 2;

	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			recursion(x + div * i, y + div * j, div);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> paper[i][j];
		}
	}

	recursion(0, 0, n);

	for (int i = 0; i < 2; ++i)
	{
		cout << answer[i] << '\n';
	}
	
	return 0;
}