알고리즘 : 함수 호출과 재귀 함수, 복잡도

다음과 같은 코드가 주어졌습니다.

int fact(int n) {
	if(n==0)
		return 1;
	else
		return fact(n-1)*n;
}

int main(void) {
	int num = 3, val;
	val = fact(num);
	printf("fact = %d\n", val);
	return 0; 
}

위 코드의 main 함수에서 fact() 함수를 호출할 때 일어나는 과정을 단계별로 적으려 합니다.

 

그 전에 함수 호출의 매커니즘에 대해 보고 넘어가도록 하겠습니다.

1. Instruction pointer를 1증가후 스택에 push : "IP+1"
2. return type용 공간을 스택에 push
3. 호출된 함수로 제어이동
4. 현 상태의 스택의 top을 stack frame이라는 특수 포인터로 유지 한다. 지금부터 리턴할 때까지 스택에 push되는 것을 이 함수의 “local”이라고 볼 수 있다
5. 함수를 부를때 사용된 인자들을 스택에 push
6. 함수 실행 시작
7. 함수 내부에 선언된 로컬변수들을 스택에 push

...뭔지 모르겠는데요?

이렇게 글로만 써놓으면 무슨말인지 저도 모릅니다.

그리고 이 문장들에 크게 신경 안 쓰셔도 됩니다. 저는 강의노트에 있기에 적은것 뿐.. 그래도 설명하자면,

1. Instruction pointer를 1증가후 스택에 push : "IP+1"

먼저 Instruction pointer는 "책갈피" 역할이라고 생각하시면 됩니다.

Visual Studio를 사용하면 우리는 F5를 눌러 디버깅 모드에 진입할 수 있습니다.

진입하기 전에 소스코드의 왼쪽에 마우스 우클릭으로 빨간색 점을 콕 찍을 수 있는데,

찍은 후 디버깅 모드로 진입하면 빨간 점을 찍은 줄 직전까지만 실행되다 중지됩니다. 

그렇게 중지된 상태에서 F10 혹은 F11을 누르면 한 단계 한 단계씩 진행되고, 

이렇게 함수를 만나게 되면 함수쪽으로 이동하게 되며, 

함수가 끝나면 다시 main함수로 돌아옵니다.

이 때, main함수에서 fact함수에 다녀오려 할 때 길을 잃지 않도록 책갈피를 껴놓는 것이 "IP+1" 입니다.

2. return type용 공간을 스택에 push

main에서 fact 함수로 넘어갈 때, fact 함수의 맨 앞에 "int" 라고 적혀있죠.

이는 fact 함수에서 리턴해주는 값이 int형, 즉 4bytes의 크기를 갖는다는 겁니다.

따라서 이 리턴값이 들어갈 곳을 확보해주기 위해 4bytes 만큼의 크기를 "예약"한다고 생각하시면 됩니다.

지금까지의 스택의 상태를 본다면 이런 느낌이겠죠.

3. 호출된 함수로 제어이동

말 그대로 이제 fact함수로 이동하게 됩니다.

4. 현 상태의 스택의 top을 stack frame이라는 특수 포인터로 유지 한다. 지금부터 리턴할 때까지 스택에 push되는 것을 이 함수의 “local”이라고 볼 수 있다.
5. 함수를 부를때 사용된 인자들을 스택에 push
6. 함수 실행 시작
7. 함수 내부에 선언된 로컬변수들을 스택에 push

4번부터는 글로만 보면 무슨 말인지 이해가 가질 않습니다. 그래서 이런 설명보다는 스택을 쌓아가는 과정을 보여드리려 합니다.

일단 "local"에 집중을 해 보겠습니다.

우리는 3번 과정에서 main 함수에서 호출한 fact(num) 으로 이동하게 됩니다.

여기서 보시면 fact 함수는 "num"이란 인자를 "n" 이라는 이름으로 받게 되죠.

 

쉽게 말하자면, main 마을에 사는 num 이라는 사람을 복제해서 fact 마을에 n이라는 이름으로 넣은 겁니다.

여기서 둘은 똑같이 3이라는 값을 가져요.

이 때, fact 마을이 바로 "함수의 local" 영역이며, main함수와는 별개의 영역입니다.

이 상태에서 fact 함수가 시작됩니다.

int fact(int n) {
	if(n==0)
		return 1;
	else
		return fact(n-1)*n;
}

fact 함수를 살펴보면, n==0 일 때 1을 리턴하고, 그렇지 않으면 fact(n-1)*n을 리턴합니다.

여기서 그냥 리턴값은 fact(n-1)*n 입니다~ 하고 fact 함수를 끝내고 main에 리턴해 버릴 수는 없겠죠? fact 함수는 int형, 즉 4bytes 짜리의 정수 값을 리턴해야 합니다.

 

우리는 이미 n값은 알고 있으니 "fact(n-1)"의 값을 알아야 fact(n-1)*n 을 계산해서 리턴해 줄 수가 있습니다.

fact(n-1)의 값을 알려면 fact 함수를 다시 한 번 돌려서 알아내야겠죠? 이렇게 리턴값에 fact 함수, 즉 자기 자신을 다시 불러오도록 하는게 "재귀 함수" 입니다.

 

우리가 main에서 호출한건 fact(3) 이니까, n==3일 때의 리턴값인 fact(2)*3 을 맞닥뜨리면 fact(2)의 값을 알아야 하니까 또 다시 fact 함수를 호출해야겠죠?

fact(2)를 호출하면 또 fact 함수를 한바퀴 돌게 되니까 fact(3)에서 처음에 n==3을 집어넣은 것 처럼 n==2를 스택에 집어 넣습니다.

fact(2)에서도 리턴값으로 fact(1)*2 를 맞닥뜨리게 되니까 fact(1)을 호출하고, fact(1)에서는 fact(0)*1을 맞닥뜨리니까 fact(0)을 호출하고...

그렇게 fact(0)까지 호출하고 난 후의 스택의 모습입니다. 

이처럼 스택이 쌓이는 과정을 스택이 "growing"한다고 합니다.

fact(0)에선 n==0이니까 드디어 재귀함수가 끝이 나네요. 이제부터 return을 시작합니다.

먼저 n==0일 때의 리턴값은 1이니까 fact(0)은 1을 리턴합니다.

추가로 설명드리자면, 지금까지 쌓인 스택을 처리할 때 순서는 프링글스를 생각하시면 됩니다.

일명 "LIFO" 라고 하는데, "Last In First Out" 구조로 프링글스처럼 제일 나중에 올려진 걸 제일 먼저 먹는 겁니다.

여담으로 Queue는 그 반대인 "FIFO(First In First Out)" 구조를 갖습니다.

 

다시 fact(1)로 와서, fact(1)의 리턴값은 fact(0)*1 이라서 fact(0)의 값이 필요했는데,

방금 fact(0)이 1임을 알았으니 이제 fact(1)은 fact(0)*1을 리턴해줄 수 있습니다.

fact(2)도 마찬가지로 fact(1)의 값이 필요했는데, 이것이 1임을 알았으니 fact(1)*2를 리턴해줄 수 있게 됩니다.

fact(3)도 마찬가지로 리턴값을 계산 해 줍니다.

fact(3)이 끝나면, fact 마을에서 볼 일이 없어졌으므로 다시 main마을로 돌아오게 되죠.

이렇게 돌아올 때 우리는 6이라는 최종 리턴 값을 들고 돌아옵니다. 마치 군대에서 출장 다녀온 동기가 밖에서 햄버거 하나 사다주는 것처럼요.

그렇다면 이제 main 함수를 살펴볼 시간입니다.

int main(void) {
	int num = 3, val;
	val = fact(num);
	printf("fact = %d\n", val);
	return 0; 
}

 

main 함수에서 아까 "책갈피"를 꽂아 둔 곳으로 돌아오면,

val = fact(num); 에서 그 리턴값이 val에 저장되니까 val의 값도 6이 됩니다.

이제 printf 문을 이용해서 "fact = 6" 이라는 문장을 출력하면 코드가 종료됩니다.

 

이 때, main 함수건 fact 함수건 모두 함수가 끝날 때 "}"로 괄호를 닫아 주는데, 이는 "스택이 비었음"을 의미합니다.

위에서 fact 마을에서 볼일이 끝났을 때에도, 스택의 fact 마을은 텅 비게 되죠.

이는 main에서도 똑같습니다. 마지막 "}"를 만나게 되면 main 마을도 텅 비게 됩니다.

이렇게 스택이 줄어드는 과정을 스택이 shrinking 한다고 합니다.

 

지금까지 함수의 호출을 스택이 쌓이고 처리되는 과정으로 알아보았습니다.

최종적으로 이를 통해 코드의 "복잡도"를 알아볼 수 있습니다.

 

복잡도는 "시간 복잡도(Time Complexity)"와 "공간 복잡도(Space Complexity)"로 나뉘는데, 우리가 위의 코드에서 그린 스택으로 공간 복잡도를 알아볼 수 있습니다.

fact(3)을 호출했을 때 최대로 쌓인 스택은 4층이었습니다.

fact(n)의 n을 더욱 늘려보아도 스택은 n+1개가 쌓이죠. 이 때 n+1을 이 코드가 돌아가는 데 필요한 공간이라고 생각하며, n+1의 공간이 필요할 때 공간 복잡도는 O(n)이 됩니다.

또한 재귀함수니까 fact(3)만 호출하는 것이 아니라 fact(0)까지 바퀴를 도는 데에 시간이 걸립니다.

이 때의 시간 복잡도도 O(n)이 됩니다.

 

여기서 O(n)은 n+1, n+2, 2n, 3n..... 등이 포함됩니다. 복잡도에 관해서는 다음 글에서 이어가도록 하겠습니다.

 

그렇다면 이 코드는 어떨까요?

int main(void)
{
	int i, n = 1;
	for(i=1; i<=3; i++)
		n *= i;
	printf("fact = %d\n", n);
	return 0;
}

이 코드는 위의 코드와 달리 따로 함수를 왔다갔다 하진 않습니다. main마을 말고는 스택이 쌓일 필요도 없죠.

이 때의 공간 복잡도는 O(1) 입니다.

 

그러나 여기에는 for 루프가 있습니다. for 루프에서 "시간 복잡도"를 알아낼 수 있습니다.

보통 for 루프 한번이면 시간 복잡도가 O(n)이라고 표현합니다.

이중 for 루프라면, 겉의 for 루프가 한번 돌 때 안쪽 for 루프가 n번 돌아가니까 n*n = n², 시간 복잡도는 O(n²) 가 됩니다.

 

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>