Binary Search (3) - Recursive 방식으로 값 찾기

Binary Search를 Recursive한 방식, 즉 재귀적인 방법으로 구현해 보았다.

 

메인함수는 Binary Search (2) 와 같으며 Recursive 함수만 추가적으로 작성하였다.

int BinarySearch_recur(int* _arr, int _searchNum, int _head, int _tail, int* _searchCnt)
{
	int mid;
	(*_searchCnt)++; // 함수가 콜 될떄마다 카운트를 하나씩 증가시킨다.

	if(_tail < _head) { // _tail이 _head보다 작아지는것은 더이상 나눠질수 없다는 것이기 때문에
		return 0; // 0을 리턴시킨다.
	}

	mid = (_head + _tail) / 2;

	if(_searchNum > _arr[mid]) {
		return BinarySearch_recur(_arr, _searchNum, mid+1, _tail, _searchCnt);
	}
	else if(_searchNum < _arr[mid]) {
		return BinarySearch_recur(_arr, _searchNum, _head, mid-1, _searchCnt);
	}
	else if(_searchNum == _arr[mid]) {
		return 1;
	}

}

 

 

차이점이 있다면 return시에 함수를 다시 call 하게 되는 것인데, 함수의 인자로 mid 값을 이용하는 것이 중요한 것 같다.

 

예를들어 찾고자 하는 값이 중간값 (arr[mid]) 보다 크다면 head index로 mid+1을 넘겨주는것,

 

찾고자 하는 값이 중간값보다 작다면 tail index로 mid-1을 넘겨주는 것이다.

 

그리고 찾고자 하는 값이 중간값과 같다면 1을 리턴하면서 함수가 종료된다.

 

 

아... 하면서 매번 느끼지만 Recursive는 어려운것 같다...

 

 

어쨌든 이러한 방식으로 구현을 한 뒤 Iterative 함수를 사용했을때와 Recursive 함수를 사용했을때의 시간을 측정하고

 

비교해보았다.

 

 

 

6753 이라는 숫자를 검색하였을 때

 

먼저 Iterative한 방식에서는

 

 

3 microsec의 시간이 측정되었으며

 

Recursive한 방식에서는

 

 

역시 3 microsec의 시간이 측정되었다.

 

 

이는 속도상 큰 차이를 보이지 않음을 알 수 있었다.

 

 

하지만 내가 비교해본 숫자의 크기는 비교적 작은 단위이기 때문에 인터넷에서 검색을 좀 해보고 찾아봤는데

 

재귀함수는 보통 일정한 수행속도를 가지고, 반복문은 수행횟수에 따라서 수행속도가 길어질 수 있다고 한다.

 

그리고 궁금한점은 재귀함수를 사용하면 계속해서 함수가 STACK영역에 올라오게 될 텐데 메모리에 영향을 주는건 없을지...

 

이것도 좀 궁금증이 생기는것 같다.

 

 

그리고 무엇보다도 피부로 느끼는건 ㅋㅋ 재귀함수는 아직 어렵게 느껴진다...

 

하지만 이러한 과제를 하다보면 가끔은 재귀함수로 구현할때 더 쉽게 구현되는 것들이 있다. 예를들어서 Tree에서

 

Preorder, Postorder, Inorder 방식으로 Tree를 탐색하는 것이라던지... ㅋ 이런건 재귀함수가 더쉬운것 같다.

 

Tree에 대해서는 나중에 다시 포스팅 하도록 하겠다!