재귀(Recursion)

오늘은 재귀에 대해 다시 학습해 보려고 합니다.

 

재귀에 대해서 아주 잘 정리가 되어있길래, 바킹독님의 블로그를 참고했습니다.

 

참고한 사이트 : https://blog.encrypted.gg/731?category=773649

 

1. 재귀란?

- 어떤 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식 입니다.

 

자기 자신을 다시 호출할 때에는 현재 함수에서의 입력값보다 더 작은 값을 인자로 넘겨주어야 한다는 특징이 있습니다.

 

또, 함수의 입력값이 일정 크기 이하일 때에는 더 이상 자기 자신을 호출하지 말고 값을 바로 반환해야 합니다. 이러한 하위 문제를 base condition이라고 부릅니다.

 

아래 코드는 n을 입력 받아 n!을 계산하는 함수를 작성했습니다. 

#include <iostream>

using namespace std;

int func(int n) {
	if (n == 1) return 1;
	return n*func(n - 1);
}

int main(void) {

	cout << func(5);

	return 0;
}

 n을 입력 받고 자기 자신보다 작은 값을 인자로 넘겨주면서 n=1일 때, base condition을 만족하고 n!을 구할 수 있습니다.

 

2. 주의할 점

재귀로 함수를 작성할 때 몇 가지 주의할 사항들이 있습니다.

 

- 함수가 입력에 대해 어디까지 연산을 수행하고, 어떤 입력값을 자기 자신에게 다시 넘겨주어야 할지 잘 정해야 합니다.

 

- 모든 재귀 함수는 반복문으로 동일한 동작을 하는 함수를 만들어낼 수 있습니다.

 

반대로, 모든 반복문으로 동작하는 함수는 재귀 함수로 만들어 낼 수 있습니다.

 

재귀를 사용할 경우 코드가 간결해지고 쉽게 이해할 수 있다는 장점이 있지만, 메모리/시간에서는 손해를 봅니다.

 

 

* 그렇기 때문에 어떨 때 재귀를 사용하면 유리하고, 어떨 때 재귀를 사용할 필요가 없는지 알고 있는 것이 좋습니다.

 

 

BOJ 1629번 문제를 예시로 들어보겠습니다.

 

자연수 A를 B번 곱하는 문제 입니다.

 

이 문제를 2초 이내에 풀어야 하지만, B가 21억보다 작은 자연수이고 최악의 경우 B가 21억일 때 A를 21억번 곱해야 하는 경우가 생길수도 있습니다.

 

이 때, 시간복잡도를 O(lgn)으로 바꾸기 위해 B를 2가지 경우로 나눕니다.

 

B를 짝수, 홀수일 경우로 나눠서 코드로 작성합니다.

 

B = 2k일 때, A^B = (A^(k))^2

 

B = 2k + 1일 때, A^B = ((A^(k))^2)*A

 

이럴 경우 아래와 같이 코드를 작성하시면 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int a, b, c, ret;

//b = 2*k일 때, b = 2*k + 1일 때를 고려해서 함수 작성
long long func(int a, int b, int c) {
	if (b == 0) return 1;
	long long val = func(a, b / 2, c);
	val = val*val%c;
	if (b % 2 == 0) return val;	//b = 2*k일 때
	else return val*a % c;	//b = 2*k + 1일 때
}

int main(void) {

	scanf("%d %d %d", &a, &b, &c);

	cout << func(a, b, c);

	return 0;
}