여기서는 C언어 또는 C++ 프로그램에서의 재귀호출 (recursive call)에 대해서 다뤄보겠습니다. 재귀호출에 대해 간단히 말하자면, 특정한 함수가 스스로를 호출하는 과정을 말하는데요. 재귀호출의 예시와 더불어 주의해야 할 점에 대해서도 짚어보겠습니다.
C언어나 C++ 프로그램에서 함수가 어떻게 정의되고 사용되는지 궁금하신 분들은 시작하기에 앞서서 다음 포스팅을 읽어보시면 큰 도움이 되리라 생각합니다.
C언어 프로그래밍 기초 : 함수와 라이브러리
이번 포스팅에서는 C언어 혹은 C++를 이용해서 복잡하면서도 규모가 큰 프로그램을 작성하는데 필수적인 요소인 함수 (function)와 라이브러리 (library)에 대해서 알아봅시다. 함수를 정의하고 호출
swstar.tistory.com
원리와 알고리즘
프로그램을 작성하다 보면 함수의 특정한 역할을 반복적으로 수행하는 것이 편리할 때가 있습니다. 예를 들자면 수학에서 배우는 점화식 혹은 재귀식 (recurrence relation)을 구현해야 하는 경우가 그렇죠. 이를 위해서는 함수를 정의하는 과정에서 스스로를 호출하는 구문을 추가하는 재귀호출이 한 방법이 될 수 있습니다.
재귀호출에 있어서 가장 주의해야 할 점은 중지 조건을 올바르게 설정해야 한다는 것입니다. 그렇지 않으면 함수가 스스로를 호출하는 게 무제한적으로 반복되어 무한루프에 빠질 위험이 있습니다. 따라서 함수 내에서 재귀호출을 하기 전에 종료를 위한 조건문을 추가할 필요가 있겠습니다. 다시 말해서 종료 조건을 만족하면 재귀호출을 하지 않고 리턴을 하는 것이죠.
가장 간단한 HelloWorld! 프로그램을 재구성해서 재귀호출에 대해 더 자세히 살펴봅시다. 재귀호출을 통해 원하는 횟수만큼 "Hello World!"를 출력하는 프로그램을 만들고자 합니다.
C언어 소스 코드입니다.
#include<stdio.h>
#include<stdlib.h>
/* "Hello World!"를
* 반복 출력하는 함수의 프로토타입
* 매개변수 : 출력 횟수 */
void greetings(unsigned int n_call);
// main 함수
int main(int argc, char *argv[]) {
unsigned int n_greet = 0;
if (argc > 1) {
/* 명령행 인자가 주어지는 경우,
* 실행파일 이름 바로 뒤에 나오는 인자로
* 출력 횟수 결정 */
n_greet =
(unsigned int)atoi(argv[1]);
} else {
/* 명령행 인자가 없으면,
* 프로그램 내에서 횟수를 입력받아
* "Hello World!" 출력 */
fprintf(stdout,
"Give me a number : ");
scanf("%u", &n_greet);
}
greetings(n_greet);
return 0;
}
void greetings(unsigned int n_call) {
/* 매개변수의 값이 1보다 작으면
* "Hello World!"를
* 출력하지 않고 리턴 */
if (n_call < 1) {
return;
}
fprintf(stdout,
" Hello World!\n");
/* 재귀호출
* 여기서 들어가는 매개변수의 값은
* 1 만큼 감소 */
greetings(n_call - 1);
}
프로그램의 main 함수는 greetings라는 함수를 호출하고 있고, greetings 함수는 스스로를 호출하는 재귀호출 과정이 있는 것을 볼 수 있는데요. 앞서 언급한 대로 재귀호출을 하기 전에 재귀호출을 중지하기 위한 조건이 설정되어 있습니다. greetings 함수의 인자로 들어가는 값이 1보다 작으면 재귀호출을 하지 않고 리턴 (return)을 하는 것이죠. 만약 매개변수의 값이 1 이상이라면 "Hello World!"를 한번 출력한 뒤, 매개변수의 값을 1 만큼 줄여서 greetings 함수를 다시 호출합니다. 결과적으로 맨 처음에 인자로 주어진 횟수만큼 재귀호출이 일어나는 것입니다.
소스 코드를 빌드해서 프로그램을 실행시켜보면 입력한 횟수만큼 "Hello World!"가 출력되는것을 확인할 수 있습니다.
Give me a number : 6
Hello World!
Hello World!
Hello World!
Hello World!
Hello World!
Hello World!
프로그램 내에서 횟수를 지정하는 방법 이외에도, 명령행 인자를 통해서 횟수를 지정할 수 있도록 코드를 구성했는데요. 터미널 콘솔에서 프로그램을 실행할 때, 실행파일 이름 뒤에 빈칸으로 분리해서 숫자를 하나 입력하면 그 횟수만큼 "Hello World!"가 출력됩니다.
예시
계승 (factorial)
프로그램에서 재귀호출을 사용해볼 수 있는 가장 간단한 수학적인 개념으로는 자연수의 계승 혹은 팩토리얼이 있죠. 자연수의 계승은 1부터 해당 숫자까지의 모든 자연수를 곱한 것으로 주어집니다. 예를 들어서 4의 계승은 1부터 4까지의 모든 자연수를 곱해서 24가 되는 것입니다. 그리고 0의 계승이 1이 된다는 점을 통해 음이 아닌 정수의 경우에 대해 확장할 수 있습니다.
수학적인 정의로부터 계승의 점화식을 도출할 수 있습니다. 자연수 N의 계승은 N-1의 계승에다가 N을 곱한것과 같습니다. 이러한 점을 이용해서 음이 아닌 정수를 매개변수로 받아서 계승을 계산하는 프로그램을 만들어볼 수 있습니다.
C언어 소스 코드입니다.
#include<stdio.h>
#include<stdlib.h>
typedef unsigned long int ULI;
ULI get_factorial(ULI n);
int main(int argc, char *argv[]) {
ULI number = 0;
if (argc > 1) {
number =
(ULI)atoi(argv[1]);
} else {
fprintf(stdout,
"Give me a number : ");
scanf("%lu", &number);
}
ULI n_factorial =
get_factorial(number);
fprintf(stdout,
" factorial(%lu) = %lu\n",
number, n_factorial);
return 0;
}
ULI get_factorial(ULI n) {
if (n < 1) {
return 1;
}
ULI ret =
n * get_factorial(n - 1);
return ret;
}
편의를 위해서 unsigned long int 자료형을 typedef를 통해 ULI로 줄여서 썼습니다. 재귀호출을 하는 get_factorial 함수가 인자로 받은 정수의 계승을 계산하는데요. 0의 계승이 1이라는 사실을 반영하여 재귀호출을 중지하는 조건을 설정했습니다. 재귀호출은 앞에서 언급한 점화식에 따라서 이루어집니다.
코드를 빌드하고 프로그램을 실행시키면, 0 이상의 정수를 입력하고 팩토리얼의 값을 출력받을 수 있게 됩니다.
Give me a number : 10
factorial(10) = 3628800
한가지 짚고 넘어가자면 자료형이 표현할 수 있는 범위에는 한계가 있기 때문에, 무한정 큰 수의 계승을 알아내기는 어렵습니다. 여기서 사용된 unsigned long int 자료형은 크기가 32비트이며, 0에서 4,294,967,295까지의 값을 가질 수 있죠. 따라서 계승의 값이 이 범위를 벗어나면 잘못된 결과를 얻게 되는 것입니다.
행렬식 (determinant)
재귀호출을 사용해볼 수 있는 또 다른 좋은 예시는 정사각행렬의 행렬식을 계산하는 경우입니다. 정사각행렬의 역행렬을 구하는 데 있어서 매우 유용한 개념인 행렬식은 특정한 점화식을 만족시킵니다. 주어진 정사각행렬의 행렬식은 크기가 더 작은 부분 행렬들의 행렬식의 합으로 주어지는데요. 행렬식의 정의와 이로부터 역행렬을 계산하는 방법에 대해서는 다음 포스팅에 더 자세한 내용이 소개되어 있습니다.
수학 상식 : 행렬식 (determinant)과 역행렬
이번 포스팅에서는 행 (row)과 열 (column)의 갯수가 같은 정사각행렬이 주어졌을때, 행렬식 (determinant)과 역행렬을 구하는 방법에 대해서 알아봅시다. 행렬식을 위한 점화식 (recurrence relation)이 어떤
swstar.tistory.com
재귀호출을 통해 행렬식과 역행렬을 계산하는 프로그램을 만들어볼 수 있습니다.
C언어 소스 코드입니다.
test1_matrix_det.c [다운로드]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXCHARACTER 1000
/* 텍스트 파일에 포함된
* 줄의 갯수를 세는 함수
* 매개변수 : 파일이름이 저장된 문자열의 포인터
* 리턴값 : 줄의 갯수 */
int get_number_lines_file(char *filename) {
int num;
char *str;
FILE *fin;
str = (char *)malloc((MAXCHARACTER + 1) *
sizeof(char));
fin = fopen(filename, "r");
if (fin == NULL) {
fprintf(stderr,
"file %s not found.\n", filename);
num = 0;
} else {
str = fgets(str, MAXCHARACTER, fin);
if (str == NULL) {
num = 0;
} else {
num = 1;
}
while (feof(fin) == 0) {
str = fgets(str,
MAXCHARACTER, fin);
if (str != NULL) {
num += 1;
}
}
fclose(fin);
}
free(str);
return num;
}
/* ir번째 행과 ic번째 열을 제외한 성분으로 구성된
* 더 작은 행렬을 구성하기 위한 함수
* ndim : 정사각행렬의 크기
* matrix : 원래 행렬을 포함한
* 2차원 배열의 포인터
* m_reduced : 특정 행과 열을 제외한
* 부분행렬을 포함한
* 2차원 배열의 포인터 */
void get_matrix_reduced(int ndim,
double **matrix,
int ir, int ic, double **m_reduced);
/* 재귀호출을 통해 행렬식 (determinant)를
* 계산하는 함수
* ndim : 정사각행렬의 크기
* matrix : 원래 행렬을 포함한
* 2차원 배열의 포인터 */
double get_determinant(int ndim,
double **matrix);
/* 역행렬을 계산하는 함수
* ndim : 정사각행렬의 크기
* matrix : 원래 행렬을 포함한
* 2차원 배열의 포인터
* m_matrix : 역행렬을 포함한
* 2차원 배열의 포인터 */
void get_matrix_inverse(int ndim,
double **matrix, double **m_inverse);
int main(int argc, char *argv[]) {
char fname_in[300];
if (argc > 1) {
strcpy(fname_in, argv[1]);
} else {
strcpy(fname_in, "matrix.txt");
}
int ndim =
get_number_lines_file(fname_in);
if (ndim < 1) {
return 1;
}
FILE *fin;
fin = fopen(fname_in, "r");
int success_read = 1;
fprintf(stdout, "# ndim = %d\n", ndim);
fprintf(stdout, "# matrix =\n");
double **matrix;
double **m_inverse;
matrix =
(double **)malloc(ndim *
sizeof(double *));
m_inverse =
(double **)malloc(ndim *
sizeof(double *));
for (int ir = 0; ir < ndim; ir++) {
matrix[ir] =
(double *)malloc(ndim *
sizeof(double));
m_inverse[ir] =
(double *)malloc(ndim *
sizeof(double));
for (int ic = 0; ic < ndim; ic++) {
int n_read =
fscanf(fin, "%lf",
&matrix[ir][ic]);
if (n_read == 0) {
success_read = 0;
break;
}
fprintf(stdout,
" %e", matrix[ir][ic]);
}
fprintf(stdout, "\n");
if (success_read == 0) {
break;
}
}
if (success_read == 0) {
fprintf(stderr,
"FAILURE in reading file.\n");
return 1;
}
fprintf(stdout, "\n");
double det_m =
get_determinant(ndim, matrix);
get_matrix_inverse(ndim,
matrix, m_inverse);
fprintf(stdout,
"# determinant = %e\n", det_m);
fprintf(stdout, "# m_inverse =\n");
for (int ir = 0; ir < ndim; ir++) {
for (int ic = 0; ic < ndim; ic++) {
fprintf(stdout,
" %e", m_inverse[ir][ic]);
}
fprintf(stdout, "\n");
}
fprintf(stdout, "\n");
fprintf(stdout, "# matrix * m_inverse =\n");
for (int ir = 0; ir < ndim; ir++) {
for (int ic = 0; ic < ndim; ic++) {
double element = 0.;
for (int j = 0; j < ndim; j++) {
element += matrix[ir][j] *
m_inverse[j][ic];
}
fprintf(stdout,
" %e", element);
}
fprintf(stdout, "\n");
}
for (int ir = 0; ir < ndim; ir++) {
free(matrix[ir]);
free(m_inverse[ir]);
}
free(matrix);
free(m_inverse);
fclose(fin);
return 0;
}
void get_matrix_reduced(int ndim,
double **matrix,
int ir, int ic, double **m_reduced) {
if (ndim == 1) {
return;
}
int kr = 0;
for (int jr = 0; jr < ndim; jr++) {
if (jr == ir) {
continue;
}
int kc = 0;
for (int jc = 0; jc < ndim; jc++) {
if (jc == ic) {
continue;
}
m_reduced[kr][kc] =
matrix[jr][jc];
kc += 1;
}
kr += 1;
}
}
double get_determinant(int ndim,
double **matrix) {
if (ndim == 1) {
return matrix[0][0];
}
double **m_reduced;
m_reduced =
(double **)malloc((ndim - 1) *
sizeof(double *));
for (int jr = 0; jr < ndim - 1; jr++) {
m_reduced[jr] =
(double *)malloc((ndim - 1) *
sizeof(double));
}
double det = 0.;
int ir = 0;
for (int ic = 0; ic < ndim; ic++) {
double sign;
if ((ir + ic) % 2 == 0) {
sign = 1.;
} else {
sign = -1.;
}
get_matrix_reduced(ndim, matrix,
ir, ic, m_reduced);
/* get_determinant 함수의 재귀호출 */
det += sign * matrix[ir][ic] *
get_determinant(ndim - 1, m_reduced);
}
for (int jr = 0; jr < ndim - 1; jr++) {
free(m_reduced[jr]);
}
free(m_reduced);
return det;
}
void get_matrix_inverse(int ndim,
double **matrix, double **m_inverse) {
if (ndim == 1) {
m_inverse[0][0] =
1. / matrix[0][0];
return;
}
double **m_reduced;
m_reduced =
(double **)malloc((ndim - 1) *
sizeof(double *));
for (int jr = 0; jr < ndim - 1; jr++) {
m_reduced[jr] =
(double *)malloc((ndim - 1) *
sizeof(double));
}
double det_m =
get_determinant(ndim, matrix);
for (int ir = 0; ir < ndim; ir++) {
for (int ic = 0; ic < ndim; ic++) {
double sign;
if ((ir + ic) % 2 == 0) {
sign = 1.;
} else {
sign = -1.;
}
get_matrix_reduced(ndim,
matrix, ir, ic, m_reduced);
double det_m_reduced =
get_determinant(ndim - 1,
m_reduced);
m_inverse[ic][ir] = sign *
det_m_reduced / det_m;
}
}
for (int jr = 0; jr < ndim - 1; jr++) {
free(m_reduced[jr]);
}
free(m_reduced);
}
행렬식을 계산하는 get_determinant 함수에서 재귀호출이 이루어지는데요. 먼저 특정한 행과 열을 제외한 성분으로 더 작은 행렬을 구성하고 이 행렬의 행렬식을 계산하는 과정이 포함되어 있습니다. 역행렬을 구하기 위해서는 행렬식이 필요하기 때문에, 역행렬을 구하는 get_matrix_inverse 함수가 get_determinant 함수를 호출하는 것 역시 확인할 수 있죠.
행렬식과 역행렬을 구하고자 하는 행렬을 텍스트 파일로부터 입력받는 형태로 프로그램을 구성했습니다. 한 줄당 하나의 행이 들어가고, 각 성분은 빈칸으로 분리됩니다. 예를 들어서 크기가 4인 정사각행렬이 있다면, 1줄에 4개의 숫자가 있고 파일 안에 총 4개의 줄이 있어야 하는 셈입니다.
matrix.txt
0.25 1. 0. 0.
1. 0.25 1. 0.
0. 1. 0.25 1.
0. 0. 1. 0.25
프로그램을 빌드하고 실행하면, 예시로 언급된 행렬의 행렬식과 역행렬을 계산해서 출력해줍니다.
원래 행렬과 역행렬을 곱하면 단위 행렬이 나오는 것도 확인할 수 있습니다.
앞에서 언급한 예제 프로그램에서 malloc 및 free 함수를 사용했는데요. 이들은 필요할때마다 변수를 위한 메모리 공간을 할당받기 위한 목적으로 사용되는 함수들입니다. 이를 두고 동적 메모리 할당이라고 부르며, 다음 포스팅에 더 자세한 내용이 소개되어 있습니다.
C언어 동적 메모리 할당 (malloc, free 함수)
일반적으로 C언어에서 변수나 배열을 선언하면, 해당 코드블록이 끝나서 범위를 벗어날때 까지 메모리를 차지하게 됩니다. 하지만 이렇게 되면 메모리 공간의 낭비가 발생할 수 있죠. 필요할 때
swstar.tistory.com
명령행 인자에 대해서도 언급했었는데, 이는 명령 프롬프트나 터미널 콘솔 등을 통해서 프로그램을 실행할 때 문자열로 넘겨줄 수 있는 변수들을 이야기합니다. C언어나 C++의 명령행 인자에 대한 더 자세한 내용이 궁금하시다면, 다음 포스팅이 큰 도움이 되리라 생각합니다.
Command-line arguments (C/C++ 명령행 인자)
C언어 또는 C++ 의 메인 (main)함수를 특별한 방법으로 정의해서, 프로그램을 실행시킬때 커맨드 라인에서 문자열들을 전달해줄 수 있습니다. 그러면 이들이 명령행 인자에 저장되어 프로그램 내
swstar.tistory.com
