[Algorithm] 재귀

재귀란?

하나의 함수에서 자기 자신을 다시 호출해서 작업을 수행하는 알고리즘이다.

int func1(int n) {
	if (n == 0) return 0;
	return n + func1(n - 1);
}

재귀로 어떤 문제를 완전 탐색으로 해결하기 위해 필요한 과정은 다음과 같다! (출처: 영균이)

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을 지를 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례 (base condition)로 선택해 처리한다.

수학적 귀납법

1번 도미노가 쓰러진다. → 2번 도미노가 쓰러진다. → k번 도미노가 쓰러지면, k+1번 도미노도 쓰러진다.

void func1(int n) {
	if (n == 0) return;
	cout << n << ' ';
	func1(n - 1);
}

위의 함수 호출은 다음과 같이 이루어진다.

 

func1(3) 호출 → 3 출력 → func1(2) 호출 → 2 출력 → func1(1) 호출 → 1 출력 → func1(0) 호출 → 종료

 

즉, func(1)이 1을 출력하고,

func1(k)가 k, k-1, k-2, ..., 1을 출력하면

func1(k+1)은 k+1, k, k-1, … , 1을 출력한다.

 

재귀에 있어서 귀납적 사고가 중요하다!

 

재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. (base condition)

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

int func1(int n) {
	if (n == 0) return 0;
	return n + func1(n - 1);
}

위 함수에서 n = 0일 때, 자기 자신을 호출하지 않고 종료가 된다.

그렇기 때문에 n = 0일 때가 base condition이 된다.

 

재귀 특징

1. 함수의 인자로 어떤 것을 받고, 어디까지 계산한 후에 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
2. 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
3. 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만, 메모리/시간에는 손해를 본다.
4. 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.
5. 재귀 함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.

관련 문제들

백준 1629 풀이

백준 11729 풀이

백준 1074 풀이

백준 2447 풀이