[c++] 재귀함수와 stack frame

stack frame이란?

함수가 호출되면 stack에 함수의 매개변수와 지역변수, 호출이 끝난 후 돌아갈 주소값이 저장된다.

이렇게 stack에 차례대로 저장되는 함수의 호출 정보를 stack frame이라고 한다.

 

재귀함수와 stack frame

c++언어로 재귀함수를 배우면서 stack frame이라는 개념이 나온 것은 출력순서를 이야기하면서 부터였다.

만약 n까지 출력하는 프로그램을 작성한다고 해보자

아래 코드와 같이 작성할 수 있다.

#include <iostream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void D(int x){
	if(x==0) return;
	else {
		D(x-1);	
		printf("%d ", x);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	D(n);
	return 0;
}

n이 3일 때, 위 코드의 결과는 1, 2, 3순으로 출력된다.

생각해보면 D(3), D(2), D(1)순으로 호출되는데 왜 1, 2, 3으로 출력이 되는걸까?

 

여기에서 위에서 설명한 stack frame개념이 나온다.

stack frame은 함수호출시 함수의 정보를 저장하는 곳이므로 함수가 재귀로 호출되면

stack frame에 함수 정보가 쌓이게 된다.

 

따라서 main 함수에서부터 n=3이므로 

D(3)에 매개변수는 3, 복귀주소는 9번째 줄(사실 주소값이지만 편의상 9번째 줄로 칭함)의 정보가 저장되고

D(3)에서 호출한 D(2)함수는 바로위 스택에 매개변수는 3, 복귀주소는 9번째 줄의 정보로 저장이 된다.

계속 마찬가지로 D(1), D(0)순으로 스택에 쌓이게 되며 출력은 스텍자료구조 특성상 

맨 나중에 저장된 함수부터 꺼내지게 된다.

따라서 D(0) -> D(1) -> D(2) -> D(3) 순으로 꺼내어지며 출력순서 또한 이에맞게 1, 2, 3이 되는 것이다.

 

만약 D(x-1)재귀함수보다 printf를 먼저 선언한다면?

이렇게 될 경우 재귀함수를 호출하기 전에 값을 출력하는 것이므로 3, 2, 1순으로 결과 나오게 된다.

 

 

예제) 재귀함수를 통해 2진수 출력해보기

재귀함수를 사용해서 2진수를 출력해보자

2진수를 출력하는 코드는 다음과 같다.

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void D(int x){
	if(x==0) return;
	else {
		D(x/2);
		printf("%d", x%2);	
	} 

}
int main() {
	int n;
	scanf("%d", &n);
	D(n);
	return 0;
}

위코드에서 재귀함수 D(x/2)를 출력하는 부분을 보면 printf보다 위에서 선언되어 있다.

n=11일 때 정답은 1011이다. 

 

이에 대한 과정을 설명하면 아래 그림과 같다.

스택에 쌓에 되는 순서는 main() -> D(11) -> D(5) -> D(2) -> D(1) -> D(0) 순이며

스택에서 꺼내어 지는 순서는 맨 나중에 들어한 함수부터 이므로 

D(0) -> D(1) -> D(2) -> D(5) -> D(11) 순이다. 따라서 결과도 1011로 출력된다.

 

마찬가지로 printf가 재귀함수보다 위에 있을 경우를 생각해보자 

그렇다면 먼저 정답을 출력하고 재귀함수가 호출될 것이다.

호출된 다는 것은 스택에 저장된다는 것을 의미하므로 스택에 저장되기전 결과가 출력되므로

결과는 1101순으로 출력될 것이다.