마지막으로 Binary Search를 Recursive한 방식, 즉 재귀적인 방법으로 구현해 보았다.
메인함수는 Binary Search (2) 와 같으며 Recursive 함수만 추가적으로 작성하였다.
차이점이 있다면 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에 대해서는 나중에 다시 포스팅 하도록 하겠다!
'Computer Science > 자료구조' 카테고리의 다른 글
Sparse Matrix (2) - 2차원 배열을 생성하고 희소행렬로 표현하기 (0) | 2012.07.28 |
---|---|
Sparse Matrix (1) - 희소행렬이란? (0) | 2012.07.28 |
Binary Search (2) - Iterative 방식으로 값 찾기 (0) | 2012.07.17 |
Binary Search (1) - 동작 방식 (0) | 2012.07.17 |
Selection Sorting의 시간 측정 (0) | 2012.07.16 |