함수호출(function call)
12 Sep 2017 | algorithm
이번 글에서는 함수호출(function call)과 이와 관련된 여러 개념에 대해 살펴보도록 하겠습니다. 이 글은 C언어를 바탕으로 설명해주신 고려대 김황남 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
점프와 프로그램 카운터
폰 노이만 아키텍처(Von-Neumann Architecture)는 헝가리 출신 미국인 수학자 존 폰 노이만(1903-1957)이 제안한 컴퓨터 구조입니다. 그는 저장된 프로그램(stored-program)이라는 개념으로 아키텍처를 설계했는데요. 데이터와 명령어를 따로 구분하지 않고 같은 공간에 저장한다는 것이 핵심입니다. 이 구조의 장점은 컴퓨터에 다른 작업을 시키려고 할 때 굳이 하드웨어를 재배치할 필요 없이 소프트웨어만 바꾸면 되기 때문에 범용성이 크게 향상된다는 것입니다. 이 때문에 현재 거의 모든 컴퓨터 중앙처리장치(CPU)는 이 구조를 따르고 있다고 합니다. 그 개념도는 다음과 같습니다.
레지스터(register)란 CPU에서 데이터와 명령어를 저장해두는 아주 빠른 기억 장소(위 그림에서 memory unit)입니다. 대부분의 CPU는 보조 메모리에서 레지스터로 데이터든 명령어든 옮겨와 이를 처리한 후 필요시 그 내용을 다시 보조 메모리로 저장하는 로드-스토어(Load-Store) 설계를 사용하고 있다고 합니다. 레지스터는 다양한 종류가 있는데, 이 중 함수호출과 직접 관련된 것은 프로그램 카운터(program counter)입니다. 프로그램 카운터란 다음에 실행될 기계어로 된 명령어의 메모리 주소를 저장해두는 레지스터의 일종으로 ‘명령어 포인터’라고도 불립니다.
한편 기계어(machine language)란 CPU가 직접 실행하는 명령어의 집합입니다. 기계어에는 로드, 스토어 같은 데이터 이동(data transfer) 명령, AND/OR 등 산술/로직(Arithmetic/Logic) 명령, 그리고 콘트롤(control) 명령 등이 있습니다. 콘트롤 명령은 프로그램 실행과 관련이 있는데요, 콘트롤 명령 가운데 함수호출과 직접 관련된 것은 점프(jump)라고 합니다. 보통 CPU는 프로그램을 순차적으로 처리합니다. 그런데 특정 조건이 만족돼 점프가 수행되면 프로그램 카운터에 저장돼 있는 주소값이 바뀌게 됩니다. 함수호출과 관련해 이를 다시 살펴보겠습니다.
예컨대 함수 A를 실행하다가 B를 호출하고, B를 실행하다가 C, C 이후 D를 차례로 호출하는 프로그램을 작성했다고 칩시다. 또 C는 함수 D의 실행 결과를 반환받아 나머지 코드를 실행한 뒤 그 결과를 B에, B는 다시 A에, 이로써 A는 최종 아웃풋을 산출하는 구조라고 가정해보겠습니다. 이 경우 CPU는 함수 A를 실행하다가 중간쯤에서 점프를 합니다. 프로그램 카운터가 함수 B가 저장된 주소값으로 바뀌게 됩니다. 아울러 B가 실행되는 중간쯤 다시 점프, 프로그램 카운터의 주소값이 함수 C의 시작 위치로 바뀝니다. 이러한 방식으로 함수호출이 점프, 프로그램 카운터와 긴밀한 관련을 맺게 되는 것입니다.
매개변수와 전달인자
그러면 함수 간 소통은 어떠한 방식으로 이뤄지는 걸까요? 다시 말해 위 그림에서 함수 D의 실행결과는 C, C가 리턴한 값은 B, B의 결과는 A의 연산에 영향을 미치는 갈색 화살표 방향이 우리의 주된 관심입니다. 이 때 중요한 개념이 바로 매개변수(parameters)와 전달인자(arguments)입니다. 매개변수란 서브함수에 입력값으로 전달되는 데이터를 가리키기 위한 변수(variable)이며, 전달인자는 서브함수를 호출할 때 전달되는 실제 값(value)을 뜻합니다. 보통 매개변수는 함수를 정의할 때 선언합니다. 예를 들어보겠습니다.
int incr( int i )
{
int j;
j = i + 1;
return j;
}
int main( void )
{
int k, m = 4;
k = incr(m);
printf( "k = %d, m = %d\n", k, m);
return 0;
}
incr 함수는 어떤 값을 넣으면 여기에 1을 더한 값을 반환하는 함수입니다. 위 코드에서 매개변수는 $i$, 전달인자는 4가 됩니다. main 함수는 incr을 호출할 때 4를 전달하며, incr 함수는 4를 $i$에 대입시켜 연산을 수행합니다. incr 함수의 최종 출력은 $j$인데, 여기엔 실제로 5라는 값이 들어 있게 되겠죠. 이 값이 다시 $main$ 함수의 $k$라는 변수에 저장되는 형식입니다.
C언어의 인자 전달(argument passing)에는 크게 값에 의한 호출(call-by-value)과 포인터에 의한 호출(call-by-pointer) 등이 있습니다. 위 예시는 바로 값에 의한 호출 방식으로 인자를 전달한 것인데요. 서브함수를 호출할 때 전달인자의 복사본을 전달하며, 함수의 전달인자는 별도의 변수로 관리됩니다. 인자의 복사본이 서브함수에 전달되기 때문에 인자가 서브함수 내에서 바뀌어도, 원래 함수의 변수는 변하지 않습니다.
위 예시를 기준으로 말씀드리면 $m$이 가리키는 값(4)의 복사본이 incr 함수에 전달되기 때문에 main 함수의 $m$의 값은 main 함수가 종료되더라도 4로 남아있게 됩니다.
포인터
포인터(pointer)란 변수의 메모리 주소 정보를 가리킵니다. 예를 볼까요?
int v = 1;
위 코드는 $v$에 해당하는 포인터에 1이라는 값을 할당(assign)하라는 뜻입니다. 그러면 포인터에 의한 호출과 관련해 아래 예시를 보겠습니다.
void incr( int* i )
{
*i = *i + 1;
}
int main( void )
{
int m = 4;
incr(&m);
printf( "m = %d\n", m);
return 0;
}
main 함수에서 ‘incr(&m)’이란 변수 $m$의 포인터를 incr 함수에 인자로 전달한다는 뜻입니다. incr 함수에서 ‘int* i’란 매개변수 $i$의 포인터가 가리키는 값을 불러온다는 뜻입니다. 따라서 incr 함수는 $m$의 포인터에 저장돼 있는 4라는 값을 불러와 여기에 1을 더한 뒤 다시 $m$에 저장합니다. 결과적으로 main 함수에서 출력되는 $m$의 값은 5가 되는 것입니다.
재귀함수
재귀함수(recursion)란 자기 자신을 반복적으로 호출하는 함수입니다. 다음 세 가지 조건을 만족해야 합니다.
(1) 종료조건(base case)이 존재한다 (=안 그러면 무한 루프)
(2) 반복문이 정의되어 있다
(3) 서브루틴을 수행할 수록 base case에 가까워진다 (=안 그러면 무한 루프)
이를 만족하는 대표적인 사례가 factorial(1부터 지정한 수까지의 모든 자연수의 곱)입니다. 코드는 다음과 같습니다.
int factorial(int n) {
if (n < 2) {
return 1;
} else {
return factorial(n-1) * n;
}
}
물론 위 함수를 반복문으로 작성할 수도 있습니다. 다음과 같습니다.
int factorial_iter(int n) {
int result = 1;
int i;
for (i = 1; i <= n; ++i) {
result *= i;
}
return result;
}
위 둘 가운데 재귀함수 방식의 계산복잡성이 아주 약간 높다고 합니다. 왜냐하면 실행 과정에서 인자를 전달해야하고, 수행 중에 점프를 해야 하는 등 함수호출 관련 추가적인 연산이 필요하기 때문입니다. 하지만 재귀함수로 코드를 작성하면 디버깅이 수월해지는 등의 장점이 있어서 선호되는 방식이라고 합니다.
그런데 재귀함수를 쓰면 되레 안 좋은 경우가 있습니다. 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)이 바로 그 예입니다(그림 출처). 딱 봐도 계산 중복이 많은데요(fib(3)는 세 번이나 계산해야 하네요). 이 경우에는 재귀함수보다는 저장해 두었다가 풀기(다이나믹 프로그래밍)를 쓰면 효율적이라고 합니다.
이번 글에서는 함수호출(function call)과 이와 관련된 여러 개념에 대해 살펴보도록 하겠습니다. 이 글은 C언어를 바탕으로 설명해주신 고려대 김황남 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
점프와 프로그램 카운터
폰 노이만 아키텍처(Von-Neumann Architecture)는 헝가리 출신 미국인 수학자 존 폰 노이만(1903-1957)이 제안한 컴퓨터 구조입니다. 그는 저장된 프로그램(stored-program)이라는 개념으로 아키텍처를 설계했는데요. 데이터와 명령어를 따로 구분하지 않고 같은 공간에 저장한다는 것이 핵심입니다. 이 구조의 장점은 컴퓨터에 다른 작업을 시키려고 할 때 굳이 하드웨어를 재배치할 필요 없이 소프트웨어만 바꾸면 되기 때문에 범용성이 크게 향상된다는 것입니다. 이 때문에 현재 거의 모든 컴퓨터 중앙처리장치(CPU)는 이 구조를 따르고 있다고 합니다. 그 개념도는 다음과 같습니다.
레지스터(register)란 CPU에서 데이터와 명령어를 저장해두는 아주 빠른 기억 장소(위 그림에서 memory unit)입니다. 대부분의 CPU는 보조 메모리에서 레지스터로 데이터든 명령어든 옮겨와 이를 처리한 후 필요시 그 내용을 다시 보조 메모리로 저장하는 로드-스토어(Load-Store) 설계를 사용하고 있다고 합니다. 레지스터는 다양한 종류가 있는데, 이 중 함수호출과 직접 관련된 것은 프로그램 카운터(program counter)입니다. 프로그램 카운터란 다음에 실행될 기계어로 된 명령어의 메모리 주소를 저장해두는 레지스터의 일종으로 ‘명령어 포인터’라고도 불립니다.
한편 기계어(machine language)란 CPU가 직접 실행하는 명령어의 집합입니다. 기계어에는 로드, 스토어 같은 데이터 이동(data transfer) 명령, AND/OR 등 산술/로직(Arithmetic/Logic) 명령, 그리고 콘트롤(control) 명령 등이 있습니다. 콘트롤 명령은 프로그램 실행과 관련이 있는데요, 콘트롤 명령 가운데 함수호출과 직접 관련된 것은 점프(jump)라고 합니다. 보통 CPU는 프로그램을 순차적으로 처리합니다. 그런데 특정 조건이 만족돼 점프가 수행되면 프로그램 카운터에 저장돼 있는 주소값이 바뀌게 됩니다. 함수호출과 관련해 이를 다시 살펴보겠습니다.
예컨대 함수 A를 실행하다가 B를 호출하고, B를 실행하다가 C, C 이후 D를 차례로 호출하는 프로그램을 작성했다고 칩시다. 또 C는 함수 D의 실행 결과를 반환받아 나머지 코드를 실행한 뒤 그 결과를 B에, B는 다시 A에, 이로써 A는 최종 아웃풋을 산출하는 구조라고 가정해보겠습니다. 이 경우 CPU는 함수 A를 실행하다가 중간쯤에서 점프를 합니다. 프로그램 카운터가 함수 B가 저장된 주소값으로 바뀌게 됩니다. 아울러 B가 실행되는 중간쯤 다시 점프, 프로그램 카운터의 주소값이 함수 C의 시작 위치로 바뀝니다. 이러한 방식으로 함수호출이 점프, 프로그램 카운터와 긴밀한 관련을 맺게 되는 것입니다.
매개변수와 전달인자
그러면 함수 간 소통은 어떠한 방식으로 이뤄지는 걸까요? 다시 말해 위 그림에서 함수 D의 실행결과는 C, C가 리턴한 값은 B, B의 결과는 A의 연산에 영향을 미치는 갈색 화살표 방향이 우리의 주된 관심입니다. 이 때 중요한 개념이 바로 매개변수(parameters)와 전달인자(arguments)입니다. 매개변수란 서브함수에 입력값으로 전달되는 데이터를 가리키기 위한 변수(variable)이며, 전달인자는 서브함수를 호출할 때 전달되는 실제 값(value)을 뜻합니다. 보통 매개변수는 함수를 정의할 때 선언합니다. 예를 들어보겠습니다.
int incr( int i )
{
int j;
j = i + 1;
return j;
}
int main( void )
{
int k, m = 4;
k = incr(m);
printf( "k = %d, m = %d\n", k, m);
return 0;
}
incr 함수는 어떤 값을 넣으면 여기에 1을 더한 값을 반환하는 함수입니다. 위 코드에서 매개변수는 $i$, 전달인자는 4가 됩니다. main 함수는 incr을 호출할 때 4를 전달하며, incr 함수는 4를 $i$에 대입시켜 연산을 수행합니다. incr 함수의 최종 출력은 $j$인데, 여기엔 실제로 5라는 값이 들어 있게 되겠죠. 이 값이 다시 $main$ 함수의 $k$라는 변수에 저장되는 형식입니다.
C언어의 인자 전달(argument passing)에는 크게 값에 의한 호출(call-by-value)과 포인터에 의한 호출(call-by-pointer) 등이 있습니다. 위 예시는 바로 값에 의한 호출 방식으로 인자를 전달한 것인데요. 서브함수를 호출할 때 전달인자의 복사본을 전달하며, 함수의 전달인자는 별도의 변수로 관리됩니다. 인자의 복사본이 서브함수에 전달되기 때문에 인자가 서브함수 내에서 바뀌어도, 원래 함수의 변수는 변하지 않습니다.
위 예시를 기준으로 말씀드리면 $m$이 가리키는 값(4)의 복사본이 incr 함수에 전달되기 때문에 main 함수의 $m$의 값은 main 함수가 종료되더라도 4로 남아있게 됩니다.
포인터
포인터(pointer)란 변수의 메모리 주소 정보를 가리킵니다. 예를 볼까요?
int v = 1;
위 코드는 $v$에 해당하는 포인터에 1이라는 값을 할당(assign)하라는 뜻입니다. 그러면 포인터에 의한 호출과 관련해 아래 예시를 보겠습니다.
void incr( int* i )
{
*i = *i + 1;
}
int main( void )
{
int m = 4;
incr(&m);
printf( "m = %d\n", m);
return 0;
}
main 함수에서 ‘incr(&m)’이란 변수 $m$의 포인터를 incr 함수에 인자로 전달한다는 뜻입니다. incr 함수에서 ‘int* i’란 매개변수 $i$의 포인터가 가리키는 값을 불러온다는 뜻입니다. 따라서 incr 함수는 $m$의 포인터에 저장돼 있는 4라는 값을 불러와 여기에 1을 더한 뒤 다시 $m$에 저장합니다. 결과적으로 main 함수에서 출력되는 $m$의 값은 5가 되는 것입니다.
재귀함수
재귀함수(recursion)란 자기 자신을 반복적으로 호출하는 함수입니다. 다음 세 가지 조건을 만족해야 합니다.
(1) 종료조건(base case)이 존재한다 (=안 그러면 무한 루프)
(2) 반복문이 정의되어 있다
(3) 서브루틴을 수행할 수록 base case에 가까워진다 (=안 그러면 무한 루프)
이를 만족하는 대표적인 사례가 factorial(1부터 지정한 수까지의 모든 자연수의 곱)입니다. 코드는 다음과 같습니다.
int factorial(int n) {
if (n < 2) {
return 1;
} else {
return factorial(n-1) * n;
}
}
물론 위 함수를 반복문으로 작성할 수도 있습니다. 다음과 같습니다.
int factorial_iter(int n) {
int result = 1;
int i;
for (i = 1; i <= n; ++i) {
result *= i;
}
return result;
}
위 둘 가운데 재귀함수 방식의 계산복잡성이 아주 약간 높다고 합니다. 왜냐하면 실행 과정에서 인자를 전달해야하고, 수행 중에 점프를 해야 하는 등 함수호출 관련 추가적인 연산이 필요하기 때문입니다. 하지만 재귀함수로 코드를 작성하면 디버깅이 수월해지는 등의 장점이 있어서 선호되는 방식이라고 합니다.
그런데 재귀함수를 쓰면 되레 안 좋은 경우가 있습니다. 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)이 바로 그 예입니다(그림 출처). 딱 봐도 계산 중복이 많은데요(fib(3)는 세 번이나 계산해야 하네요). 이 경우에는 재귀함수보다는 저장해 두었다가 풀기(다이나믹 프로그래밍)를 쓰면 효율적이라고 합니다.
Comments