티스토리 뷰

자료구조와 알고리즘

재귀 함수) 재귀함수의 특성에 대해 알아보기

Bennett Kim 2018. 4. 30. 23:45

안녕하세요? 오늘은 재귀함수에 대해 알아보는 시간을 갖도록 하겠습니다.


재귀(recursion)란? 사전적 정의를 보면 다음과 같습니다.

: 원래의 자리로 되돌아가거나 되돌아옴.(네이버 국어사전)


원래의 자리로 되돌아가거나 되돌아온다. 무슨 말일까요? 그리고 그런 특성을 가진 함수를 재귀함수라고 하는데 뭔가 알것 같기도 하고... 


하나하나씩 살펴보겠습니다. 

void recursion(){
    recursion()
}

코드를 이렇게 짜놓으면 어떻게 될까요? 코드의 순서를 보며 프로그램의 흐름을 보겠습니다. 먼저 [line 1] 에서 recursion()함수가 시작합니다. 그리고 [line 2]에서 또 다시 recursion()함수가 호출됩니다. 그러면 또 다시 코드의 흐름은 [line 1]에서 부터 시작하게 됩니다.

이렇듯 사전적 정의 처럼, 원래의 자리로 되돌아가거나 되돌아오는 함수, 즉 자기 자신을 호출하는 함수를 재귀함수라고 합니다.


그럼 여기까지 재귀함수의 개념에 대해 살펴보았고 이제부터 몇 가지 실험을 하도록 하겠습니다. 


다음 코드를 보겠습니다. 

처음 코드와 달리 종료 조건(terminate condition)을 추가하였고 구분을 쉽게 하기 위해 각 recursion() 함수의 호출 순서를 번호로 표시하였습니다.

#include <iostream>
using namespace std;

void recursion(int num) {
	if (num > 3)
		return;
	cout << "Recursion" << num << endl;
	recursion(num + 1);
}

int main() {
	recursion(1);
	return 0;
}

실행 결과는 다음과 같습니다.


메인함수에서 recursion을 호출하고 인자로 정수 1을 넘겨줍니다.

피호출자인 recursion은 매개변수 num으로 인자를 넘겨받고 

만약 이 num이 3보다 크다면 return; 문으로 현재 함수를 종료하고, 

크지 않다면 "Recursion num"을 출력합니다.

그리고 num에다 1을 더하여 또 다시 자기 자신을 호출합니다.

이런식으로 진행하다보면 언젠가는 num이 3보다 커질 경우가 반드시 존재하게 되고 그경우 return; 문이 실행되어 그동안 실행되었던 모든 함수의 순서에 반대인 역순서로 함수가 차례로 종료하게 되고 프로그램은 끝나게 됩니다.


인터넷 혹은 교재를 보면 재귀함수는 original 함수가 copy되어 작동한다고 설명되어있거나 그림으로 묘사 되어있습니다.


진짜로 그런지 직접 실험을 통해 확인해보겠습니다.

#include <iostream>
using namespace std;
typedef void (*FunctionPointer) (int);

void recursion(int num) {
	if (num > 3)
		return;
	FunctionPointer fp;
	fp = recursion;
	string str = "Wow";
	cout << "Recursion" << num << "'s memory address is "<< fp <<endl;
	cout << "Recursion" << num << "'s str address is " << &str << endl;
	cout << "Recursion" << num << "'s num address is " << num << endl << endl;
	recursion(num + 1);
}

int main() {
	recursion(1);
	return 0;
}

다음은 실행결과입니다.


출력문을 보시면 Recursion함수 메모리상 위치는 모두 동일하였고 내부 변수들의 메모리 위치는 서로 상이하다는 것을 확인할 수 있습니다.


위에서 봤던 그림을 처음 딱 봤을 땐, 마치 재귀함수가 실행될 때마다 각 함수는 매번 메모리에 새로 할당되는 것처럼 보였으나 실제로는 함수는 할당위치는 고정되어있는 상태에서 내부 변수들만 새롭게 할당된다는 사실을 알 수 있었습니다.


그림과 실제 결과가 살짝 다른 것을 확인할 수 있습니다.


또한 재귀함수의 호출 가능 횟수는 RAM의 크기에 따라 정해지는데요, 그 이유는 지역변수는 메모리의 stack에 저장되고 이 stack은 RAM에 있기 때문이죠.


자 그럼 또 다른 실험을 진행해보겠습니다.

#include <iostream>
using namespace std;

int cnt = 0;
void recursion(int num) {
	cnt++;
	cout << cnt << endl;
	recursion(num);
}
int main() {
	recursion(1);
	return 0;
}

위 코드의 실행결과는 다음과 같습니다.

함수의 호출 횟수 4762번에서 stack overflow로 프로그램이 종료되었습니다.


이번에는 좀 더 무거운 재귀를 돌려 보겠습니다. 그러기 위해서 불필요한 변수를 선언해보겠습니다.

다음 코드를 보시죠

#include <iostream>
using namespace std;

int cnt = 0;
void recursion(int num) {
	cnt++;
	int *garbage = new int[num];
	cout << cnt << endl;
	recursion(num);
}
int main() {
	recursion(1);
	return 0;
}

실행결과입니다.

이번에는 4282번에서 stack overflow현상이 발생하였습니다.


지금까지의 실험을 총 정리해보면

1. 재귀함수는 자기 자신을 호출하는 함수이다.

2. 재귀함수는 호출될 때 함수의 메모리 상 위치는 그대로 유지하되 내부 지역 변수를 모두 메모리에 새롭게 할당한다.

3. 할당되는 메모리는 stack memory이며, 이는 RAM에 있다.

4. 따라서 RAM의 용량과 재귀함수 내 지역 변수의 크기에 따라 재귀함수의 호출 가능 횟수가 결정된다. 

댓글