[알고리즘] 재귀함수 (Recursion Function)

재귀함수의 개념

재귀: 자신을 정의 할때 자기 자신을 재참조 하는 것, 원래 자리로 되돌아온다. 

재귀함수: 어떤 알고리즘이나 함수가 자기 자신을 호출하여 작업을 수행하는 함수

재귀함수의 원리

스택(STACK) 자료구조

스택은 함수가 호출될때 마다 메모리 공간을 확보한다. 재귀함수가 호출될 때마다 스택의 가장 위에 쌓이며 실행 완료되면 제거된다. 나중에 들어온 것이 가장 위쪽으로 쌓이고 제일 먼저 들어온 것은 가장 마지막에 제거되므로 LIFO(Last In First Out) 구조이다. 현재 스택에서 가장 위에 있는 함수가 다음으로 실행되는 함수이다.  

 

기저조건

재귀함수를 탈출하기 위한 조건이다. 어떤 특정 조건(기저조건)이 충족될때 return 하고 함수 호출을 중단하는 것이다. 재귀함수는 자기 자신을 계속해서 호출하므로 만약 기저 조건이 없으면 함수가 무한히 호출되어 스택 오버플로우(stack overflow)가 발생한다. 문제를 더 이상 분할 할 수 없을 때를 기저 조건으로 설정하는 것이 좋다.

 

재귀함수 예시

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void A(int a) {
	if (a == 0)
		return;
	printf("%d ", a);
	A(a - 1);//재귀함수호출
}
int main() {
	A(10);//A함수 호출
	printf("\n\n");
}

 

이제 main에서부터 차근차근 시작해보면

 

1. A(10) 호출 

처음 A함수에 10이라는 숫자를 넣어줬다.

if문에서 a는 0이 아니므로 바로 printf("%d ", a)를 통해 a값을 출력한다. 

현재 출력값: 10

A(a-1)를 호출한다. 현재 a의 값이 10이므로 다음 a는 9이다.

 

2. A(a-1)

다시 A함수 처음으로 돌아와 if문과 비교한다. 또 다시 a는 0이 아니므로 a값을 출력한다.

현재 출력값: 10 9

A(a-1)를 호출한다. 현재 a의 값이 9이므로 다음 a는 8이다.

위 과정을 반복하다보면 이러한 결과를 얻는다.

전체 출력값: 10 9 8 7 6 5 4 3 2 1 

3. A(0)

마지막 a가 1일때 1-1은 A는 0이므로 if(x==0)에서 return 된다. 

그 후 다시 원래 함수가 호출되었던 자리 A(a-1)로 차근차근 돌아가다 함수를 빠져나온다. 

이해가 잘 안된다면 두번째 예시를 보면 된다.

재귀함수 예시2

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void A(int a){
	if (a == 0) return;
	printf("%d ", a);
	A(a - 1);
	printf("\n%d번 함수", a);
}
int main() {
	A(10);//A함수 호출
	printf("\n\n");
}

앞선 코드와 달리 A(a-1) 즉 재귀함수를 호출하는 부분 다음에 추가로 문장이 생겼다. 이제 다시 한줄씩 살펴보겠다.

 

1. main 함수에서 A(10) 실행.

A함수를 호출하여 if문 비교한다. false 이므로 return 안함.

printf("%d ", a); 실행

현재 출력값: 10

A(a-1) 호출. 다시 처음으로 돌아간다. 

 

2. A(a-1) 실행

앞서 설명했던 것과 같은 방법으로 A(a-1) 호출을 반복한다. 

현재 출력값: 10 9 8 7 6 5 4 3 2 1 

 

3. if(a==0) return;

a가 0일때 return 되므로 다시 원래 호출되었던 자리로 돌아간다.

현재 a가 0이므로 원래 호출되었던 자리 

A(1-1) //a가 1일때

printf("\n%d번 함수", a);

현재 출력값:

10 9 8 7 6 5 4 3 2 1 

1번 함수

현재 a의 값은 1이므로 1번 함수가 출력되며 다시 return 된다.

 

4. A(a-1)

a가 1일때 return 되었으므로 다시 a(1)이 호출되었던 곳으로 되돌아가면

A(2-1) 이다. 따라서 현재 a의 값은 2이므로, 다음 문장을 실행한다. 

현재 출력값:

10 9 8 7 6 5 4 3 2 1 

1번 함수

2번 함수

앞선 과정을 반복하다보면 최종적으로 출력값은 이렇게 된다.

재귀함수 실행 결과

글로만 설명해서 잘 이해 안갈수도 있으니 그림으로도 나타내보았다. 

재귀함수 설명

정리하자면 재귀 함수는 문제를 여러 조각으로 분해하여 자기 자신을 호출해 코드를 보다 간결하고 확실한 계층적 구조를 만들어낸다. 그러나 기저 조건이 제대로 주어지지 않을 경우 스택 오버플로우가 발생할 수 있고, 호출 횟수가 많아지면 일반 함수보다도 시간이 오래 걸린다. 따라서 재귀함수는 주어진 경우에 적합할 때에만 사용하고, 한번 사용할때 이를 구성하는 함수를 잘 이해하고 코드를 짜야한다.  

재귀함수에 대한 더 자세한 응용은 문제와 함께 풀면서 정리해야겠다.