56. 재귀함수 분석(스택 사용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include <stdio.h>

using namespace std;

void recur(int x)
{
	if(x>0)
	{
		recur(x-1);
		printf("%d ", x);
	}
}


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

1. 재귀함수는 기본적으로 stack을 사용한다. 위 코드로 예시를 들어보겠다.

- main() 메서드에서 recur()를 호출한다.

- recur() 에서 매개변수로 받은 int x가 0이 아니라면 자기 자신을 한 번 더 호출하고, printf()로 x를 출력한다.

- 여기서 잘못 생각하기 쉬운데, 바로 printf()가 실행되지 않는다는 점이다.

- n = 3 일 때 예로 들어보겠다.

recur(3) 의 스택 프레임(매개변수로 받은 int x, 복귀주소)

main() 의 스택 프레임(매개변수, 지역변수, 복귀주소 등)

recur(3)이 최초로 main()에서 호출된다. 3 > 0이기 때문에 recur(2)가 호출된다.

recur(2) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(3)의 recur(x-1) 라인)

recur(3) 의 스택 프레임(매개변수 :  int x, 복귀주소 : main()의 recur(n) 라인)

main() 의 스택 프레임(매개변수, 지역변수, 복귀주소 등)

recur(2)에서는 recur(1)이 호출된다.

recur(0) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(1)의 recur(x-1) 라인)

recur(1) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(2)의 recur(x-1) 라인)

recur(2) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(3)의 recur(x-1) 라인)

recur(3) 의 스택 프레임(매개변수 :  int x, 복귀주소 : main()의 recur(n) 라인)

main() 의 스택 프레임(매개변수, 지역변수, 복귀주소 등)

이렇게 반복하고나서 recur(0) 부터 차례대로 실행되는 원리이다.

recur(0) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(1)의 recur(x-1) 라인) -> return

recur(1) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(2)의 recur(x-1) 라인) -> printf(1)

recur(2) 의 스택 프레임(매개변수 : int x, 복귀주소 : recur(3)의 recur(x-1) 라인) -> printf(2)

recur(3) 의 스택 프레임(매개변수 :  int x, 복귀주소 : main()의 recur(n) 라인) -> printf(3)

main() 의 스택 프레임(매개변수, 지역변수, 복귀주소 등)

 

위와 같이 스택이 쌓이는데, 스택을 더이상 저장할 공간이 없어져버릴 때 stackoverflow가 일어나게 된다.