Data structures 02.3:programming recursive functions

Presentation on theme: "Data structures 02.3:programming recursive functions"— Presentation transcript:

1 Data structures 02.3:programming recursive functions
동의대학교 멀티미디어공학과 이광의 교수

2 Today’s topic 재귀함수의 예와 동작방법 mathematical induction수학적 귀납법 재귀함수의 활용
계승 함수와 그 동작방법 피보나치 함수와 그 동작방법 최소공배수 함수 mathematical induction수학적 귀납법 계승 함수의 증명 피보나치 함수의 증명 최소공배수 함수의 증명 재귀함수의 활용 징검다리 건너기 당근 캐기 거북이 옮기기 Dept. of Multimedia Engineering, DongEui Univ.

3 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

4 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 방법 1: 1, 2, 3 방법 2: 1, 2 방법 3: 1, 3 방법 4: 2, 3 방법 5: 2 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

5 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 1 3 2 Dept. of Multimedia Engineering, DongEui Univ.

6 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

7 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. 마지막으로 7번 거북이를 밟고 지나가는 방법 마지막으로 6번 거북이를 밟고 지나가는 방법 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

8 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

9 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

10 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2) 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

11 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2); F(0)= 1; F(1) = 2; 2 6 3 1 7 5 4 Dept. of Multimedia Engineering, DongEui Univ.

12 Programming Recursive Functions
징검다리 건너기: 토끼가 바다를 건너 당근 밭에 가고자 한다. 토끼는 바로 다음 거북이를 밟고 가거나 하나를 건너뛸 수 있다. 토끼가 바다를 건너는 방법은 모두 몇 가지 인가? 건너는 방법은 두 가지로 나눌 수 있다. F(7): 거북이가 7마리 있을 때 방법의 수 마지막으로 7번 거북이를 밟고 지나가는 방법 F(6) 마지막으로 6번 거북이를 밟고 지나가는 방법 F(5) F(7) = F(6) + F(5) >> F(n) = F(n-1) + F(n-2); F(0)= 1; F(1) = 2; 2 6 3 1 7 5 4 int F (int n) { if (n==0) return 1; // return 0 if (n==1) return 2; // return 1 return F (n-1) + F (n-2); } Dept. of Multimedia Engineering, DongEui Univ.

13 Programming Recursive Functions
징검다리 건너기: int F(int n) { if (n==0) return 1; if (n==2) return 2; return F(n-1) + F(n-2); } 증명 귀납법 기초: P(1), P(0) 귀납법 단계: 임의의 자연수 k에 대하여 {P(k-1) AND P(k-2)} -> P(k) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

14 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

15 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

16 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

17 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 1 1 Dept. of Multimedia Engineering, DongEui Univ.

18 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

19 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

20 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

21 Programming Recursive Functions
당근 캐기: 무사히 바다를 건넌 토끼가 집으로 가는 길에 당근을 캐려고 한다. 단, 토끼는 오른쪽과 아래로만 이동 가능하다. 토끼는 최대 몇 개의 당근을 캘 수 있는가? 당근 옆에 쓰인 수는 그 칸을 지날 때 캘 수 있는 당근의 수이다. 2 2 2 이 수를 C(i,j)라 하자 3 1 int max (int x, int y) { if (x>y) return x; else return y; } int F (int n, int m) { // F(int i, int j) if (n==0||m==0) return 0; return C (n, m) + max (F(n-1,m), F(n,m-1)); 1 2 F (n-1,m) 1 1 F (n,m-1) F(n,m) Dept. of Multimedia Engineering, DongEui Univ.

22 Programming Recursive Functions
당근 캐기: int max(int x, int y) { if (x>y) return x; else return y; } Int F(int n, int m) { if (n==0||m==0) return 0; return C(n,m) + max(F(n-1,m), F(n,m-1)); 증명 귀납법 기초: P(0, 0..m), P(0..n, 0) 귀납법 단계: 임의의 자연수 n과 m에 대하여 {P(n-1,m) AND P(n,m-1)} -> P(n, m) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

23 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? A B C Dept. of Multimedia Engineering, DongEui Univ.

24 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

25 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 (수조) A의 (가장 위에 있는) 거북이를 (수조) C로 이동한다. (A->C) A B C Dept. of Multimedia Engineering, DongEui Univ.

26 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 한 마리인 경우 (수조) A의 (가장 위에 있는) 거북이를 (수조) C로 이동한다. (A->C) A B C Dept. of Multimedia Engineering, DongEui Univ.

27 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

28 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

29 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

30 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

31 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 두 마리인 경우 A->B; A->C; B->C; A B C Dept. of Multimedia Engineering, DongEui Univ.

32 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

33 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

34 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

35 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

36 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

37 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

38 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

39 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

40 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 세 마리인 경우 A->C; A->B; C->B; A->C; B->A; B->C; A->B; A B C Dept. of Multimedia Engineering, DongEui Univ.

41 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

42 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

43 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

44 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

45 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 세 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (3, A, B, C); 네 번째 거북이를 이동한다. A->C Move (4, A, C); 세 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (3, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

46 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 A B C Dept. of Multimedia Engineering, DongEui Univ.

47 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

48 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

49 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

50 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); A B C Dept. of Multimedia Engineering, DongEui Univ.

51 Programming Recursive Functions
거북이 옮기기: 토끼가 거북이를 수조 A에서 C로 옮기고자 한다. 단, 거북이를 옮길 때는 한 마리씩 옮길 수 있으며, 바로 바로 수조에 다시 넣어야 한다. 또한, 수조 안에서 큰 거북이는 작은 거북이 위에 올 수 없다. 어떤 순서로 이동하여야 하는가? 네 마리인 경우 n-1 마리를 수조 A에서 수조 B로 옮긴다. MoveTurtles (n-1, A, B, C); n 번째 거북이를 이동한다. A->C Move (n, A, C); n-1 마리를 수조 B에서 수조 C로 옮긴다. MoveTurtles (n-1, B, C, A); void Move(int n, char S, char D) { cout << “move turtle” << n << “ from ” << S << “ to ” << D << endl; } int MTs (int n, char S, char D, char M) { if (n>1) MTs (n-1, S, M, D); Move (n, S, D); if (n>1) MTs (n-1, M, D, S); A B C Dept. of Multimedia Engineering, DongEui Univ.

52 Programming Recursive Functions
거북이 옮기기: void Move(int n, char S, char D) { cout << “move turtle” << n << “ from ” << S << “ to ” << D << endl; } int MTs (int n, char S, char D, char M) { if (n>1) MTs (n-1, S, M, D); Move (n, S, D); if (n>1) MTs (n-1, M, D, S); 증명 귀납법 기초: P(1) <- S, D, M은 중요 변수가 아니다. 실제로는 P(1, A, B, C), P(1, B, A, C), P(1, C, A, B) P(1, A, C, B), P(1, B, C, A), P(1, C, B, A) 모든 경우에 잘 동작한다. 귀납법 단계: n에 대하여 P(n-1) -> P(n) 귀납법 기초가 모든 경우에 종료될 수 있도록 충분하다. Dept. of Multimedia Engineering, DongEui Univ.

53 You are the one Who makes that happen!!! summaries 재귀함수의 활용 징검다리 건너기
당근 캐기 거북이 옮기기 You are the one Who makes that happen!!! Dept. of Multimedia Engineering, DongEui Univ.