※요약

재귀함수를 통해 10진수2진수로 변환한다.



※특징

10진수 n을 Dec2Binary함수에 넣으면 2진수로 출력해준다.

int형으로 값을 받으므로 2,147,483,647의 수까지 변환이 되며,

더 큰 수를 변환하고 싶으면 unsigned int나 unsigned __int64로 하면 된다.

unsigned __int64의 경우 18446744073709551615의 수를 2진수로 변환 할 수 있다.



※예제

#include <stdio.h>

void Dec2Binary( unsigned __int64 nNum );

int main( )
{
	unsigned __int64 nNum = 0;

	printf( "-1 입력시 종료 됩니다.\n" );

	while( nNum != -1 )
	{
		printf( "숫자를 입력하세요 : " );
		scanf( "%d", &nNum );

		Dec2Binary( nNum );
		printf( "\n\n" );
	}

	return 0;
}

void Dec2Binary( unsigned __int64 nDecimal )
{
	if( nDecimal < 2 )
	{
		printf( "%I64u", nDecimal );
	}
	else
	{
		Dec2Binary( nDecimal/2 );
		printf( "%I64u", nDecimal%2 );
	}
}


※결과


-unsigned __int64형으로 했을 때 변환할 수 있는 최대의 수


※요약

C언어에서 재귀 호출을 이용한 이진 탐색이다. 이진 탐색이란 이름 그대로 탐색할 데이터를 반으로 나눠 나머지 반만 탐색하는 방식을 반복하는 알고리즘이며 빠른 속도로 원하는 값을 찾을 수 있다. 이진 검색, 이분 검색 등으로도 불린다.


특징

 - 각 요소의 값들은 정렬되어 있어야 한다.

 - 각 요소의 값들은 모두 달라야 한다.


※예제

#include <stdio.h>

int RecusiveBinSearch( int nArr[], int nBegin, int nEnd, int nTarget )
{
	int nMid = 0;

	if( nBegin > nEnd )
	{
		return -1;	//탈출 조건 및 탐색 실패
	}

	nMid = (nBegin+nEnd) / 2;

	if( nArr[nMid] == nTarget )
	{
		return nMid;			//타겟을 찾았다.
	}
	else if( nTarget < nArr[nMid] )
	{
		return RecusiveBinSearch( nArr, nBegin, nMid-1, nTarget );
	}
	else
	{
		return RecusiveBinSearch( nArr, nMid+1, nEnd, nTarget );
	}
}

int main( )
{
	int nArr[] = { 1, 3, 5, 7, 9, 11, 13 };
	int nResult;

	nResult = RecusiveBinSearch( nArr, 0, sizeof(nArr)/sizeof(int)-1, 7 );
	
	if(nResult == -1)
	{
		printf( "값이 없습니다.\n" );
	}
	else
	{
		for( int i=0 ; i<sizeof(nArr)/sizeof(int) ; ++i )
		{
			printf( "%d ", nArr[i] );
		}
		printf( "\n%d번째 배열 요소에 있습니다.\n", nResult );
	}

	return 0;
}



결과



※요약

C언어에서 재귀 호출을 이용한 거듭제곱 구하는 함수다.

어떤 수 a에 대하여 n개 곱한 것을 a^n( a)이라 표시하고 a의 n제곱이라 하며, n을 거듭제곱의 지수라고 한다.

a = 3, n = 5일때 3^5 = 243 = 3 * 3 * 3 * 3 * 3 다.



※예제

#include <stdio.h>

double power( double a, int num );

int main( )
{	
	printf( "%.10lf", power( 3.141592653589793238462643383279, 3 ) );

	return 0;
}

double power( double a, int num )
{
    if( num == 0 )
        return 1;   
 
    return a * power( a, num-1 );
}


결과




요약

C언어에서 재귀 호출을 이용한 팩토리얼 구하는 함수이다.

정수 n의 팩토리얼은 n! 이라고 표시하며, n! = n * (n-1) * (n-2) * (n-3) * . . * 2 * 1 이며

5! 일 경우 5! = 120 = 5 * 4 * 3 * 2 * 1 다.



예제

#include <stdio.h>

unsigned __int64 factorial( unsigned __int64 num );

int main( )
{
	int nNum = 5;
	printf( "%d! : %I64u", nNum, factorial(nNum) );

	return 0;
}

unsigned __int64 factorial( unsigned __int64 num )
{
	if( num == 1 )
	{
		return 1;
	}

	return num * factorial( num-1 );
}


※결과



※요약

재귀 함수란 자기 자신을 호출하는 함수


일반적인 함수 호출 방법은 다음과 같다. 프로그램 실행 중 함수를 만나면 현재 위치를 저장 후, 호출할 함수의 주소로 점프해 함수 내용을 수행한다. 함수 실행이 끝나면 기억해뒀던 원래 위치로 복귀해 다음 코드를 수행한다. (일반적으로 잦은 함수 호출로 인한 점프의 반복은 속도를 느리게 한다.)


일반 함수나 재귀 함수나 위와 같은 방법으로 함수가 호출이 되는데 재귀 함수의 경우 함수의 실행이 채 끝나기도 전에 자기 자신을 호출한다. 이게 가능한 이유는 호출된 각 함수에 대한 복귀 번지, 인수, 지역 변수 등이 스택 프레임에 저장되기 때문에 기존의 작업 내용들이 서로 방해하지 않고 잘 동작할 수 있는 것이다.


※재귀 함수 특징

 - 무한 루프에 빠지지 않기 위해 일정한 탈출 조건이 있어야 한다.

 - 코드를 단순화 할 수 있다.

 - 재귀 함수는 호출 시 마다 스택 공간을 이용하므로 무리하게 호출하면 스택 오버플로우가 일어날 수 있다.

 - 재귀 함수의 호출 횟수는 스택의 남은 공간과 재귀 함수의 지역 변수 사이즈에 따라 달라진다.

 - 디버깅 및 실행 흐름을 파악하기 힘들다.



※예제

아래 예제는 기초적인 재귀 함수 예제다.

다음 게시물부터는 재귀를 이용한 팩토리얼(factorial), 거듭 제곱(power, square), 이진 탐색(binary search) 등을 알아보겠다.

#include <stdio.h>

void Recursive( int nCount )
{
	if( nCount <= 0 )
	{
		printf( "발사\n" );
		return ;
	}
	else
	{
		printf( "카운트 다운 : %d\n", nCount );
		Recursive( nCount-1 );        //인자로 받은 nCount에 -1을 줄여서 호출한다.
	}
}

int main( )
{
	Recursive( 5 );

	return 0;
}


결과


+ Recent posts