순환(재귀) 알고리즘, 이진(이원) 탐색

대부분의 전산학도들은 순환 기법을 Ackermann 함수나 factorial 연산 같은 특수한 부류의 문제에만 유용하다고 생각하는데, 이는 옳지 않다. 왜냐하면 지정문, if-else, while 문으로 작성할 수 있는 어떤 프로그램도 순환(재귀)으로 작성할 수 있기 때문이다.

때때로 이 순환 함수가 반복 함수보다 이해하기 쉬운 경우도 있다. 앞선 글에서 다루어보았던 이원 탐색 프로그램을 순환 방식으로 변환하기 위해서는 1) 순환 호출이 종결될 수 있도록 경계 조건들을 먼저 설정해야 하며, 2) 매 호출마다 해답을 향해 한 단계씩 가까워지게끔 순환 호출을 구현하여야 한다.

#define COMPARE(x,y) (((x) < (y)) ? -1: ((x) == (y)) ?

0 : 1) int binarySearch(int arr[], int target, int left, int right){ int mid; if (left <= right){ mid = (left + right) / ...