Chapter 05. 재귀 알고리즘

chapter 05 - 1 재귀의 기본

 

재귀

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 것

 

- 재귀를 효과적으로 사용한다면 프로그램, 정의를 간결하게 할 수 있음

- 직접 재귀 (direct) : 내부에서 자신과 같은 메서드 호출

- 간접 재귀 (indirect) : a가 b를 호출하고 b가 다시 a를 호출하는 구조

 

- 풀어야 할 문제, 계산할 메서드, 처리할 데이터 구조가 재귀로 정의되는 경우 가장 알맞음

 

  팩토리얼 구하기

  - 재귀적 정의

    ① 0! = 1

    ② n > 0인 경우 n! = n X (n - 1)!

 

  유클리드 호제법

  - 두 정수의 최대공약수(greatest common divisor) 구하기

    - 두 수를 직사각형의 각 변이라고 가정하여 짧은 변으로 하는 정사각형으로 분할 : 반복

    - a와 b라고 가정하면 a와 b의 나머지 와 b의 최대공약수를 구하는 과정 반복하여 return 

      → (b, a % b)

 

- 연습문제

   - 재귀 메서드 호출 사용하지 않고 factorial 메서드 작성

      (ⓒⓞⓓⓔ) ex01.java

   - 재귀 메서드 호출 사용하지 않고 gcd 메서드 작성

      (ⓒⓞⓓⓔ) ex02.java

   - 배열 a의 모든 요소의 최대공약수 구하는 메서드 작성

      (ⓒⓞⓓⓔ) ex03.java

 

 

 

chapter 05 - 2 재귀 알고리즘 분석

 

- 예제 코드 통해 하향식 분석 / 상향식 분석 정리

 

  - 하향식 분석 (top-down) : recur(4)인 경우

    ① recur(3)

    ② print 4 // ①번 재귀함수 모두 실행한 뒤 4가 출력됨

    ③ recur(2)

    - 가장 위쪽에 있는 메서드 호출부터 시작하여 계단식으로 자세히 조사하는 분석

    - 위의 코드처럼 같은 메서드 호출이 여러번 이루어질 수 있으므로 반드시 효율적이지는 않음. 

 

  - 상향식 분석 (bottom-up) : recur(4)인 경우

     ① recur(1) // n이 양수일 때만 실행하므로 1부터 시작

        ① recur(0)

        ② print 1

        ③ recur(-1)

     ② recur(2)

        ① recur(1) // print 1

        ② print 2

        ③ recur(0)

    ③ recur(3)

        ① recur(2) // print 1 2

        ② print 3

        ③ recur(1) // print 1

    ④ recur(4)

        ① recur(3) // print 1 2 3 1

        ② print 4

        ③ recur(2) // print 1 2

 

- 연습 문제

   - recur2 메서드 보고 하향식 분석과 상향식 분석 수행

      (ⓣⓧⓣ) ex04

 

 

재귀 알고리즘의 비재귀적 표현

- ex) recur(n - 2) 의미는 n의 값을 n-2로 업데이트하여 recur 다시 시작 (꼬리 재귀 제거)

- 가장 앞에 있는 recur(n-1)도 위와 같이 하게 되면 값이 바뀌기 때문에 잠시 값을 저장할 변수 필요

  → 스택 사용

 

- 연습문제

   - recur3 메서드를 비재귀적으로 표현

      (ⓒⓞⓓⓔ)

 

 

chapter 05 - 3 하노이의 탑

쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘

 

- 하노이의 탑 실행 조건

  - 모든 원반의 크기는 다르며, 처음에는 첫 번째 기둥에 쌓여 있음.

  - 원반은 1개씩만 이동 가능, 큰 원반은 작은 원반 위에 올리는 것은 불가능