재귀 reccurssion.

Presentation on theme: "재귀 reccurssion."— Presentation transcript:

1 재귀 reccurssion

2 마트료시카, 러시아 인형

3

4 재귀(再歸, Recursion) 자신을 정의할 때 자신을 재참조하는 방법
함수에 적용한 재귀 함수(Recursion Function) 사진이나 그림 등에서 재귀의 형태를 사용 A recursive process is one in which objects are defined in terms of other objects of the same type. Using some sort of recurrence relation, the entire class of objects can then be built up from a few initial values and a small number of rules. The Fibonacci numbers are most commonly defined recursively. Care, however, must be taken to avoid self-recursion, in which an object is defined in terms of itself, leading to an infinite nesting. 는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법

5 재귀함수호출

6

7

8 어린왕자 그 다음 별에는 술꾼이 살고 있었다. 그 방문은 매우 짧았지만 어린 왕자를 깊은 우울에 빠뜨렸다. "뭘 하고 있어요?" 빈병 한 무더기와 술이 가득 차 있는 병 한 무더기를 앞에 놓고 말없이 앉아 있는 술꾼을 보고 그가 말했다. "술을 마시지.“ 침울한 표정으로 술꾼이 대꾸했다.... "왜 술을 마셔요?“ 어린 왕자가 그에게 물었다. "잊기 위해서지.“ 술꾼이 대답했다. "무엇을 잊기 위해서예요?“ 측은한 생각이 든 어린 왕자가 물었다. "부끄럽다는 걸 잊기 위해서지.“ 머리를 숙이며 술꾼이 대답했다. "뭐가 부끄럽다는 거지요?“ 그를 돕고 싶은 어린 왕자가 캐물었다. "술을 마시는 게 부끄러워!“ 이렇게 말하고 술꾼은 침묵을 지켰다. 그래서 난처해진 어린 왕자는 길을 떠나 버렸다. (어른들은 정말 참 이상하군)하고 어린 왕자는 여행을 하면서 혼자 속으로 중얼거렸다.

9 Factorial(팩토리알) 함수 (function)
C 언어로 “factorial” 함수 정의하기 unsigned int factorial(unsigned int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } 이 함수는 n을 입력으로 받을 때, 자기 보다 작은 n-1 을 함수 입력으로 받은 값에 n을 곱한다. 이 과정을 기본 과정 (n=1)에 도달할 때까지 계속함. n! = n x (n-1) x (n-2) x (n-3) x …x 3 x 2 x 1

10 컴퓨터 프로그래밍에서 재귀 재귀의 가장 큰 이 점 함수가 자신의 더 간단하거나 더 작은 버전으로 표현 되는 것
더 작은 그 간단 버전이나 작은 버전의 답을 사용해서 원 버전의 답을 구함. 재귀의 가장 큰 이 점 무한 집합의 문장이나 디자인이나 자료를 유한한 컴퓨터 프로그래밍으로 정의 할 수 있다는 것

11 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … a1 = 1 a2 = 1 an = an–1 + an–2   for n > 2

12

13 하노이의 탑 조건 문제 세개의 기둥, 서로 다른 크기의 N개의 원반 원반들은 세개의 기둥 중 하나에 꽃혀 있음
자신보다 작은 크기의 원반은 위에 올 수 없음 문제 기둥 1에 N개의 원반이 크기대로 꽃혀있음 이 원반을 기둥 3으로 모두 옮기기 옮기는 과정에서 기둥 2를 사용할 수 있음

14 하노이 타워 http://m.youtube.com/watch?v=9i51uoTF9qQ 재귀가 무엇인지?
동영상을 보고 "수학은 ( )을 찾는 것"의 괄호 속에 들어가는 2 글자를 찾아 보세요. 하노이 타원 6개 짜리 옮기기 시합한다면 1등할 수 있을까? 연습해 보시오. 1등하는 팀이나 개인은 상이 있습니다.

15 N개를 옮기는 것과 n-1개를 옮기는 것이 구조적으로 똑 같음.
// 하노이의 탑 // 1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다. // 2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다. // 3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다. // 원반을 from에서 to로 옮긴다. void move(int from, int to){     printf("\nMove from %d to %d", from, to); } // n개의 원반을 from 에서 by를 거쳐 to로 옮긴다. void hanoi(int n, int from, int by, int to){     if (n == 1)         move(from, to);     else{         hanoi(n - 1, from, to, by);    // 1번  N-1개의 원반을 기둥3을 거쳐 2로 옮긴다.         move(from, to);                // 2번 기둥 1에서 1개의 원반을 기둥 3으롱 롬긴다.         hanoi(n - 1, by, from, to);    // 3번 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.     } }

16 수학적 귀납법