[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (재귀 알고리즘 분석 - recur 메서드)

[재귀 알고리즘의 분석 - recur 메서드]

1. recur 메서드는 메서드 안에서 재귀호출을 2회 실행합니다.

2. 이처럼 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라 하며, 실제 동작은 매우 복잡합니다.

3. 이런 복잡한 구조를 가진 재귀 메서드는 좀 더 전략적으로 분석해야합니다.

' 왼쪽 화살표를 따라 하나 아래 상자로 이동하고, 다시 원래의 상자로 돌아오면 상자 안의 값을 출력하고 이어서 오른쪽 화살표를 따라 칸 아래 상자로 이동한다'로 그림을 해석하시면 되겠습니다.

​

<recur 하향식 분석>

1. 매개변수 n으로 4를 전달하면 recur 메서드는 아래 과정을 순서대로 실행합니다.

1) recur(3)을 실행합니다.

2) 4를 출력합니다.

3) recur(2)를 실행합니다.

2. 물론 2) 에서 4를 출력하는 것은 1의 recur(3) 실행이 완료된 다음입니다.

3. 이처럼 가장 위쪽에 위치한 상자의 메서드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 하향식 분석(top-down analysis)이라고 합니다. 그런데 이 그림 안에는 recur(1), recur(2)의 호출이 여러 번 있습니다.(같은호출), 꼭대기(top)부터 분석하면 이렇게 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 '하향식 분석이 반드시 효율적이다'라고 말할 수는 없습니다.

​

<recur 상향신 북석>

1. recur 메서드는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각해보겠습니다.

1) recur(0)을 실행합니다.

2) 1을 출력합니다.

3) recur(-1)을 실행합니다.

여기서 recur(0)과 recur(-1)은 출력할 내용이 없습니다. 따라서 1만 출력합니다.

2. 그럼 recur(2)에 대해 생각해봅시다.

1) recur(1) 을 실행합니다.

2) 2를 출력합니다.

3) recur(0)을 실행합니다.

recur(1)은 1을 출력하고 recur(0)은 출력할 내용이 없습니다. 전체 과정을 거치면 1과 2가 출력됩니다.

​

[재귀 알고리즘의 비재귀적 표현] - recur 메서드를 재귀 호출을 사용하지 않고 구현하는 방법

1. 꼬리 재귀의 제거

1) 메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2) 라는 말은 '인자로 n-2를 전달하여 recur 메서드를

호출한다'는 의미입니다. 따라서 이 호출은 아래처럼 바꿀 수 있습니다.

2) n의 값을 n-2로 업데이트 하고 메서드의 시작 지점으로 돌아갑니다.

2. 재귀의 제거

1) 꼬리 재귀와 달리, 앞에서 호출한 재귀 메서드의 제거는 쉽지 않습니다. 왜냐하면 변수 n의 값을 출력하기 전에

recur(n-1)을 먼저 수행해야 하기 때문입니다.

2) 즉, 현재 n의 값을 '잠시' 저장하고 recur(n-1)의 처리가 완료된 다음에 n의 값을 출력할 때는 '저장했던 n을 다시

꺼내 그 값을 출력합니다.'

< 재귀를 제거한 recur 메서드>