Chapter 02 순환 (Recursion).

Presentation on theme: "Chapter 02 순환 (Recursion)."— Presentation transcript:

1 Chapter 02 순환 (Recursion)

2 Contents 2. 1 순환의 소개 2. 2 거듭 제곱의 값 계산 2. 3 피보나치 수열의 계산 2. 4 하노이탑 문제

3 2. 1 순환의 소개 순환 (Recursion) 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 정의자체가 순환적으로 되어 있는 경우에 적합한 방법 예) 팩토리얼 (factorial) 피보나치 수열 이항계수

4 2. 1 순환의 소개 팩토리얼 값 구하기 정의 (n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산 (순환 호출)
2. 1 순환의 소개 팩토리얼 값 구하기 정의 (n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산 (순환 호출) 함수 호출 순서 factorial(5) = 5 * factorial(4)         = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120

5 2. 1 순환의 소개 순환 알고리즘의 구조 순환 알고리즘은 다음과 같은 부분들을 포함 순환 호출을 하는 부분
2. 1 순환의 소개 순환 알고리즘의 구조 순환 알고리즘은 다음과 같은 부분들을 포함 순환 호출을 하는 부분 순환 호출을 멈추는 부분

6 2. 1 순환의 소개 순환  반복 컴퓨터에서의 되풀이 대부분의 순환은 반복으로 바꾸어 작성할 수 있음 순환 반복
2. 1 순환의 소개 순환  반복 컴퓨터에서의 되풀이 순환 (recursion): 순환 호출 이용 반복 (iteration): for나 while을 이용한 반복 대부분의 순환은 반복으로 바꾸어 작성할 수 있음 순환 순환적인 문제에서는 자연스러운 방법 함수 호출의 오버헤드 반복 수행속도가 빠르다. 순환적인 문제에 대해서는 프로그램 작성이 아주 어려울 수도 있음

7 2. 1 순환의 소개 팩토리얼의 반복적 구현

8 2. 2 거듭 제곱값 계산 거듭 제곱 프로그래밍 순환적인 방법이 반복적인 방법보다 더 효율적인 예
2. 2 거듭 제곱값 계산 거듭 제곱 프로그래밍 순환적인 방법이 반복적인 방법보다 더 효율적인 예 숫자 x의 n제곱값을 구하는 문제: xn 반복적인 방법

9 2. 2 거듭 제곱값 계산 거듭 제곱 프로그래밍 (Cont.) 순환적인 방법

10 2. 2 거듭 제곱값 계산 프로그래밍 분석 순환적인 방법의 시간 복잡도 반복적인 방법과 순환적인 방법의 비교
2. 2 거듭 제곱값 계산 프로그래밍 분석 순환적인 방법의 시간 복잡도 만약 n이 2의 제곱이라고 가정하면 다음과 같이 문제의 크기가 줄어듬 반복적인 방법과 순환적인 방법의 비교 반복적인 함수 slow_power 순환적인 함수 power 시간복잡도 O(n) O(logn) 실제수행속도 7.17초 0.47초

11 2. 3 피보나치 수열의 계산 피보나치 수열 순환 호출을 사용하면 비효율적인 예 순환적인 구현
2. 3 피보나치 수열의 계산 피보나치 수열 순환 호출을 사용하면 비효율적인 예 0,1,1,2,3,5,8,13,21,… 순환적인 구현

12 2. 3 피보나치 수열의 계산 피보나치 수열의 계산 순환 호출을 사용했을 경우의 비효율성 같은 항이 중복해서 계산됨
2. 3 피보나치 수열의 계산 피보나치 수열의 계산 순환 호출을 사용했을 경우의 비효율성 같은 항이 중복해서 계산됨 예를 들어 fib(6)을 호출하게 되면 fib(3)이 4번이나 중복되어서 계산됨 이러한 현상은 n이 커지면 더 심해짐

13 2. 3 피보나치 수열의 계산 피보나치 수열의 반복 구현 반복 구조를 사용한 구현

14 2. 4 하노이탑 문제 하노이탑 (Hanoi-tower) 문제는 막대 A에 쌓여있는 원판 n개를 막대 C로 옮기는 것 조건
2. 4 하노이탑 문제 하노이탑 (Hanoi-tower) 문제는 막대 A에 쌓여있는 원판 n개를 막대 C로 옮기는 것 조건 한 번에 하나의 원판만 이동 가능 맨 위에 있는 원판만 이동 가능 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 함

15 2. 4 하노이탑 문제 n = 3 인 경우 해답

16 2. 4 하노이탑 문제 일반적인 경우

17 2. 4 하노이탑 문제 남은 문제 어떻게 n-1개의 원판을 A에서 B로, 또 B에서 C로 이동하는가?
2. 4 하노이탑 문제 남은 문제 어떻게 n-1개의 원판을 A에서 B로, 또 B에서 C로 이동하는가? (Hint) 원래 문제가 n개의 원판을 A에서 C로 옮기는 것임을 기억 작성하고 있는 함수의 파라미터를 n-1로 바꾸어 순환 호출

18 2. 4 하노이탑 문제 하노이탑 프로그램 n-1개의 원판을 A에서 B로 옮기고 n번째 원판을 A에서 C로 옮긴 다음, n-1개의 원판을 B에서 C로 옮기면 됨

19 [ Exercises ] Chapter 02 (page. 62) 14 순환적 프로그램 17 순환 → 반복 구조 변환
14 순환적 프로그램 17 순환 → 반복 구조 변환 18 이항계수를 계산하는 순환 함수 작성 19 Ackermann 함수