CHAP 2:순환 2016. 3. 17 순천향대학교 컴퓨터공학과

순환(recursion)이란? 순환은 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 문제나 자료구조가 순환적으로 정의되는 경우, 알고리즘을 순환적으로 표현하는 것이 적합 예제: 정수의 팩토리얼 정의 Factorial 알고리듬 재귀적 정의

순환 알고리즘의 구조 순환 알고리즘은 다음과 같은 부분들을 포함한다. 만약 순환 호출을 멈추는 부분이 없다면?. 순환 호출을 하는 부분 else return n * factorial(n-1); int factorial(int n) { 순환을 멈추는 부분 순환호출을 하는 부분 } if( n <= 1 ) return 1 만약 순환 호출을 멈추는 부분이 없다면?.

순환 vs. 반복 대부분의 순환은 반복 버전으로 표현할 수 있고, 모든 반복은 순환 버전으로 표현할 수 있다. 순환 반복 순환적인 문제에서는 매우 자연스러운 방법 비효율적 반복 수행속도가 빠르다. 순환적인 문제에 대해서는 프로그램 작성이 아주 어려울 수도 있다.

순환 vs. 반복 팩토리얼 함수를 정의하라. 팩토리얼 함수 fact(n)을 알고리즘으로 작성하라. n! = 1 if n = 0 n*(n-1)*(n-2)*….*1 if n>0 팩토리얼 함수 fact(n)을 알고리즘으로 작성하라. Factorial 순환 버전 Factorial 반복 버전

Quiz 다음 함수를 sub(10)으로 호출시에 어떤 값이 반환되는가? int sub(int n) { if ( n < 0) return 0; return n + sub(n-3); }

예제: 거듭제곱  

예제: 거듭제곱  

예제: 거듭제곱 power(), power2()의 알고리즘 복잡도 비교 구분 Power1 Power2 알고리즘 시간복잡도

예제: 피보나치 수열 피보나치 수열 정의 0,1,1,2,3,5,8,13,21,… fib(n)의 알고리즘을 작성하라.

예제: 피보나치 수열 피보나치 순환 알고리즘은 어떻게 동작하는가? 이 알고리즘은 효율적인가? n= 6인 경우를 고려 fib(6) fib(4) fib(5) fib(2) fib(3) fib(3) fib(4) fib(1) fib(0) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3)

예제: 피보나치 수열 fib(7)이 호출될 경우에, fib(4)는 몇 번이나 중복 계산되는가?

예제: 피보나치 수열 알고리즘 반복 버전

예제: 피보나치 수열 알고리즘 복잡도 비교 구분 반복 버전 순환 버전 알고리즘 시간복잡도

예제: Hanoi 탑 문제 기원 1883년 프랑스 수학자 Edouard Lucas에 의해서 소개 옛날에 인도의 Kashi Vihswanath에 있는 브라만교 대사원에 하노이 탑이 있었고, 이 탑에는 3개의 다이어몬드 기둥과 그 한 기둥에 순금 원판 64개가 쌓아 있었다고 한다. 신이 브라만 승려들에게 다음 원칙으로 원판을 옮기라고 하였고, 원판은 한번에 한 개씩만 옮긴다 작은 원판 위에 큰 원판을 올려놓을 수 없다 64개의 원판이 다른 원판에 모두 옮겨졌을 때, 세상의 종말이 온다고 하였고, 승려들은 아직까지도 옮기고 있다고 함 http://en.wikipedia.org/wiki/Tower_of_Hanoi 웹 사이트: http://vornlocher.de/tower.html 스마트폰 어플: Tower of Hanoi

예제: Hanoi 탑 문제 A B C 문제 가정 문제 각 원판의 크기는 다르다. 한번에 하나의 원판만 이동 가능 크기가 작은 원판 위에 큰 원판을 쌓는 것 불가 위의 조건을 충족하면서 막대 A상의 모든 원판을 막대 C로 이동하는 알고리듬을 작성하라. A B C 가정 문제

예제: Hanoi 탑 문제 원판의 개수가 3인 경우 A B C

예제: Hanoi 탑 문제 원판의 개수가 n인 경우 A B C n-1개의 원판 1개의 원판

예제: Hanoi 탑 문제 알고리즘 생각 A B C Goal: A 상의 원판 n개를 막대 B를 이용하여 C로 이동하라. hanoi_tower(n, A, B, C) 문제를 순환적으로 생각 A 상의 원판 n-1개를 B로 이동 (C를 이용) A의 하나 남은 원판을 A에서 C로 이동: move(A, C) B상의 원판 n-1개를 C로 이동 (A를 이용) A B C

예제: Hanoi 탑 문제 알고리즘 A B C A 상의 원판 n-1개를 B로 이동 (C를 이용) A의 하나 남은 원판을 C로 이동 B상의 원판 n-1개를 C로 이동 (A를 이용) A B C hanoi_tower(int n, char from, char tmp, char to) // from상의 n개 원판을 tmp를 이용하여 to로 이동 { }

예제: Hanoi 탑 문제