배열 요소별 개수 세기 (재귀함수 사용)

c 언어 사용

 

 

 

문제 : 

1~10 숫자들이 랜덤으로 저장되어 있는 A배열을 만든다. 프로그램이 실행되면, 사용자에게 하나의 숫자를 입력받고, 해당 숫자가 A배열 안에 몇 개가 존재하는지 개수를 출력한다.

 

 

 

조건 :

1. 재귀 함수(Recursive Function)를 사용한다.
2. 참조에 의한 호출 (Call By Reference)을 사용한다.

 

 

 

풀이 코드 :

#include <stdio.h>

int NumberEqual(const int A[], int N, int X); // 개수세기 함수 선언
int main(void)
{
	// 변수 초기화 (X : 사용자 입력값, K : y/n 반복여부 입력값)
	int X;  
	char K;
	int A[15] = {5, 3, 7, 8, 3, 2, 7, 3, 9, 3, 1, 10, 2, 4, 5};


   	// 배열 요소 출력
	printf("배열 A의 요소 = {");
	for(int i=0; i<15; i++)
		printf("%d%s", A[i], (i!=14)?", ":"}\n");


	while(1)
	{
		printf("\n검색할 X의 값을 입력하세요 : ");
 		scanf(" %d",&X); //검색할 값 입력
		printf("%d의 개수 : %d", X, NumberEqual(A, 15, X)); // 개수세기 함수 호출
		printf("\n계속하시겠습니까 ? (y/n) ");
		scanf(" %c",&K);
		if(K=='n') 
		break;
	}
	return 0;
}


/**
 * int[] A : 배열을 함수로 call by reference로 전달
 * int N : 사용자가 입력한 숫자와 비교할 베열안의 요소 위치를 전달
 * int X : 사용자가 입력한 숫자를 전달
 **/
int NumberEqual(const int A[], int N, int X) //개수세기 함수 정의
{
	// N은 14(=배열 마지막 위치)부터 시작해서 0(=배열 처음 위치)이 될때 까지 반복
	if(N>=0)
	{
		// 사용자의 입력값 X와 배열의 N-1번째 위치의 요소가 맞으면
		if(A[N-1] == X){ 
			// 재귀함수로 자신을 다시 호출 & 재귀로 돌아오면 +1로 리턴	
			return (1 + NumberEqual(A, N-1, X)); 
		}
        
		// 사용자의 입력값 X와 배열의 N-1번째 위치의 요소가 틀리면	
		else{        
			// 재귀함수로 자신을 다시 호출 & 재귀로 돌아오면 자신만 리턴
			return (NumberEqual(A, N-1, X));
		}
	}
	else
		return 0;
}

 

 

 

풀이 결과 : 

배열 A의 요소 = {5, 3, 7, 8, 3, 2, 7, 3, 9, 3, 1, 10, 2, 4, 5}

검색할 X의 값을 입력하세요 : 5
5의 개수 : 2
계속하시겠습니까 ? (y/n) n

 

 

 

풀이 설명 :

랜덤값으로 초기화 배열을 도식화하면 아래처럼 그려진다. 나 같은 경우는 배열 크기를 15개로 고정시키고 랜덤값은 직접 아무거나 적어서 초기화했다. 코딩을 할 때 특히, 배열을 사용할 때는 배열의 값을 가져오기 위해 위치를 잘 생각해서 코딩해야한다. 헷갈리지 않도록 아래 그림처럼 배열은 0부터 시작한다는 것을 잘 알아두길 바란다.

 

[ 배열 A의 요소 ]

 

[조건 2] 처럼 참조에의한 호출을 사용한다는 것은 함수 입력매개변수의 타입을 주소로 사용하는 것을 말한다. 배열을 참조에 의한 호출(call by reference) 형태로 매개변수로 넘길 때, 2가지 방법으로 코딩이 가능하다. 아래 처럼 매개변수 타입을 배열 타입으로 하는 방법과 포인터를 사용하는 방법이다. 둘다 주소값을 넘기는 참조에 의한 호출(call by reference) 형태이기 때문에 어떤 방법을 사용해도 상관이 없다. 풀이 코드에서는 배열 매개변수 타입을 사용해서 작성했다.

 

// 배열(array) 매개변수
int NumberEqual(const int A[], int N, int X);

// 포인터(pointer) 매개변수
int NumberEqual(const int* A, int N, int X);

 

[조건 1] 처럼 재귀함수를 사용한다는 것은 호출한 함수 안에서 자신의 함수를 또 불러내는 형태의 코딩을 말한다. 배열의 개수를 셀 때, 간단하게 코딩을 한다면, 아래처럼 반복문(ex, for, while)을 사용해서 count변수에 하나씩 누적시키는 방법이 있을 것이다. 하지만, 조건이 재귀함수를 사용한는 것이기에 조금 다르게 만들어야 했다.

 

#include <stdio.h>
int main(void)
{
	int X=5; 
	int A[15] = {5, 3, 7, 8, 3, 2, 7, 3, 9, 3, 1, 10, 2, 4, 5};
	int count = 0;
	int N=15;

	for(int i=N; i>=0; i--) {
		if(A[i-1]==X) 
			count++;
	}
	printf("count : %d", count);
	return 0;
}

 

위 코드와 동일한 처리를 하는 코드를 재귀함수를 이용한 코드로 변경시킬 경우, 사용한 코드 중 조건문을 기준으로 수정하면 어렵지 않게 변경시킬 수 있다. 위 코드에서는 조건문이 2개가 있다. 하나는 15개의 요소의 반복을 멈추는 i>=0 문장이고, 다른 하나는 각 요소의 값과 사용자 입력값을 비교시켜주는 A[i-1]==X 문장이다.

i>=0 문장은, 재귀함수 내에서 반복적(=재귀적)으로 함수를 호출할 때, 재귀를 더 이상 못하도록멈추는 조건으로 사용한다. 작성된 풀이코드에서는 N>=0 문장을 동일한 역할을 하는 코드이다. 이 코드에 의해 NumberEqual 함수는 N(=배열의 인덱스 위치가)값이 0 이상일 경우 재귀를 계속하고, 0 미만일 경우 0을 리턴하고 재귀를 멈추게 된다.

A[i-1]==X 문장은, 재귀함수 내에서 카운트(=개수세기)하기 위해, 1을 증가시키는 조건으로 사용한다. 작성된 풀이코드에서는 A[i-1]==X 문장으로 동일하게 사용하였다. 그리고 조건이 맞을 경우 1을 증가시킨 후 리턴하고, 조건이 틀릴 경우 증가값 없이 리턴하도록 하였다. 이 코드에 의해 사용자가 입력한 값과 배열의 요소값이 동일할 때만 1이 증가해서 리턴하게 되며, 결과적으로는 마지막에 리턴하는 함수는 누적된 값을 리턴하게 된다.

 

[ 재귀함수(Recursive Function) & 배열(Array) & 스택(Stack) ]

 

조금 더 수월한 이해를 위해, Stack을 이용해 설명하는 그림을 추가했다. 재귀함수는 함수를 호출할 때마다 Stack이라는 메모리 공간에 차곡차곡 하나씩 쌓이게 되는데, 현재 작성된 풀이의 조건 중 하나인 N>=0일 경우에만 쌓이게 되는 것이다. 조건이 아닐 경우, Stack에 쌓인 함수들은 하나씩 차례로 리턴하게 되고 가장 마지막 함수는 이전 함수들에서 의해 처리된 결과들에 모두 영향을 받은 최종 결과물, 즉 여기서는 누적된 카운트값을 리턴하게 되는 것이다. 

 

재귀함수를 구현할 때는 스택(Stack)구조를 생각하면서 코딩하는 것이 도움이 된다. 재귀함수라는 말은 자신의 함수를 또 호출하는 것을 말해서 코딩하는 개발자 입장에서는 헷갈리는 기법이지만, 컴퓨터입장에서는 재귀함수도 그냥 일반적으로 다른 함수를 호출하는 것과 동일한 형태로, 함수를 호출할 때는 그저 스택(Stack)에 쌓아서 처리하기 때문이다.

 

저작자표시 비영리 변경금지

티스토리툴바