Page 24 -

재귀(Recursion) 메서드는 자기 자신을 호출할 수도 있다(재귀호출이 낯설다면 연습문제 1.1.16
~1.1.22를 풀어보길 권장한다). 예를 들어 다음에 나오는 예제 코드는 BinarySearch의 rank() 메서
드를 다른 방식으로 구현하고 있다. 재귀호출을 이용하면 더 간단하고 이해하기 쉬운 코드를 만들 수
있다. 같은 알고리즘에 대해 재귀호출을 사용하는 경우와 사용하지 않는 경우 코드의 복잡도에서 매
우 크게 차이가 난다. 예를 들어 다음의 예제 코드의 주석만 보고서 이 코드가 어떤 동작을 하는지,
올바른 동작을 하는지 수학적으로 연역하여 쉽게 이해할 수 있다. 3.1절에서 재귀호출과 이진 탐색
의 동작 증명에 대해서 상세하게 다룬다. 재귀호출을 구현할 때는 다음과 같은 중요한 세 가지 경험

칙이 있다.
• 재귀호출은 종단 케이스를 가진다. 메서드의 첫 부분에 조건에 따른 리턴문이 들어간다.

• 재귀호출이 깊어 질수록 더 작은 문제를 다루게 된다. 다음의 코드에서 네 번째, 세 번째 인수
는 메서드가 호출될 때마다 작아진다.
• 재귀호출 간에는 다루는 문제가 중첩되어서는 안 된다. 다음의 코드에서 두 개의 하부 문제에
서 다루는 배열 항목들은 서로 분리되어 있다.

이와 같은 경험칙을 벗어난 재귀호출 코드는 잘못된 결과를 내놓거나 매우 비효율적이게 된다(참고:
연습문제 1.1.19~1.1.27). 이들 경험칙을 지키면 명료하고, 올바르고, 그 동작 성능을 이해하기 쉬
운 코드를 만들 수 있게 된다. 재귀호출 메서드를 이용하는 또 다른 이유는 동작 성능을 이해하기 위
한 수학적 모델을 쉽게 유추할 수 있기 때문이다. 이에 대한 내용은 3.2절에서 이진 탐색과 관련하여
상세하게 다루고 이 책 전반에 걸쳐 요소요소에서 이야기된다.

이진 탐색의 재귀적 구현
public static int rank(int key, int[] a)
{ return rank(key, a, 0, a.length - 1); }

public static int rank(int key, int[] a, int lo, int hi)
{ |/ a[]에 저장된 키의 인덱스는, 만약 존재한다면
|/ lo보다 작을 수 없고 hi보다 클 수 없다.
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank(key, a, lo, mid - 1);
else if (key > a[mid]) return rank(key, a, mid + 1, hi);
else return mid;
}

기본 프로그래밍 모델 static 메서드의 라이브러리는 자바 클래스 안에 정의된 static 메서드들
로 이루어진다. 자바 클래스는 pulic class 키워드 뒤에 클래스 이름을 지정하고, 중괄호를 열고,
static 메서드들의 구현부를 위치시키고, 중괄호를 닫음으로써 만들어진다. 이 코드를 클래스 이름

과 동일한 파일명을 가지고 확장자가 .java인 파일에 두게 된다. 기본적으로, 이 책의 자바 프로그램

036