::
Recursion
함수의 재귀 호출
학습 목표
Recursion 의 필요성
Recursion 의 정의 및 사용법교재: 30장
recursion = recursive call
= 재귀 호출
3
MJU CE C Language Programming함수란?
병속의 지니와 같다.
평소에는 공간을 차지하지 않는다.❖
함수 선언
일을 시킬 때만 나타난다.❖
함수 호출미스터 손 (동영상)
5
MJU CE C Language Programming호출시 일어나는 일
오공아, 요괴가 세마리 나타났다. 어떻게 좀 해 봐라.main 함수 sohn
호출
Activation Record=함수의 실체
함수 main 함수 sohn
운영체제
7
MJU CE C Language Programming재귀 호출?
내가 나에게 일을 시킨다???자기 자신의 사본을 이용하기
"치키치키 차카차카... 펑 !"한마리는 내가
처치할테니 나머지는
니가 알아서 해! 알았어.
9
MJU CE C Language Programming복사본도 또 복사를...
한마리는 내가
처치할테니 나머지는 니가 알아서 해!
알았어.
"치키치키 차카차카.."
한마리는 내가
처치할테니 나머지는 니가 알아서 해!
펑!
알았어.
Recursion (재귀호출)
Stack top (최근에 생긴 activation record)
호출 호출
호출 결과반환
결과반환
결과반환
11
MJU CE C Language ProgrammingCFL의 재귀 호출 (demo)
재귀 호출의 방법
보통 함수의 호출과 같다.
void fun(){
...
fun();
...
}13
MJU CE C Language Programminglab27_01: 재귀함수의 호출
파일명: self.c
함수 fun 은 적절한 메시지("Hello\n")를 한 줄 출력하고 1초간 쉰 후 자기 자신을 재귀 호출하는 함수이다.
prototype:void fun();
1초간 쉬려면 sleep(1); 을 사용한다.#include <unistd.h> 필요
프로그램을 강제 종료 시키려면 ctrl-C 를 누른다. (주 의: ctrl-z 가 아님)무한 호출의 제한...
옙.셋! 치키치키...
넌 둘 까지만이야. 알았어. 둘! 치키치키...
넌 하나까지만이야 알았어. 하나!
끝이네.
오공아, 너 자신을
셋이상으로 복제하지 말아라.
15
MJU CE C Language Programming시도 1
앗. 끝 났는데...
17
MJU CE C Language Programming완성 (sohn2.cfl)
무한 호출의 제한
void fun(int n){
printf("%d\n", n);
if (n>0){
fun(n-1);
}
return;
}
int main(){
fun(3);
}
main
3 2 1
n
0n
n
n
19
MJU CE C Language Programminglab27_02/sohn.c
자기 자신을 호출하는 함수
int Mr_sohn(int n) 을 정의한다.
Mr_sohn()에서는 "요괴 X 마리 남았음."과 같은 메시 지를(숫자는 자신이 받은 파라메터 값) 한번 출력한 뒤 파라메터로 받은 값이 0보다 크면 자기 자신을 호출하 고 (이 때 실질 파라메터는 자신이 받은 값보다 1 작은 값을 준다.) 그렇지 않으면 그냥 0을 반환한다.
main에서는 정수를 입력받아 Mr_sohn을 호출한다.재귀적 문제 정의
1 부터 N-1 까지의 정수의 합이 X라면
1부터 N까지의 정수의 합은 얼마일까?21
MJU CE C Language Programming게으른 Mr.Sohn의 덧셈
야, 1에서 9까지
더하면 얼마냐? 야, 1에서 8까지
더하면 얼마냐 야, 1에서 7까지 더하면 얼마냐
오공아, 1에서 10까지 더하면 얼마냐?.
바보냐?
1이지
야, 1에서 1까지 더하면 얼마냐
...
45+10= 음...
55 입니다.
36+9= 음...
45 입니다.
재귀적으로 문제 해결하기
1.
함수가 할 일을 정의한다. 이때 주어지는 것은 무엇인지, 결과 는 무엇인지를 정확히 정의해야 한다.2.
만일 내가 받은 일이 "충분히 작을 때" 어떻게 처리할 것인지를 정한다. (trivial case)3.
만일 내가 받은 일이"클 때" (non-trivial case)어떻게 일을 나 누어 다른 clone 을 호출할 것인지를 정해야 한다. 현재 받은 일보다 작은 일은 문제없이 해결된다고 가정한다.4.
clone에게 시켜서 받은 결과를 어떻게 하면 "나의 임무"로 연 결시킬 수 있는지를 정한다.23
MJU CE C Language Programming예제
정수 N이 주어졌을 때 제귀적으로 1 ~ N 사이의 정수 구하기
1. 단계: 받는 파라메터: 정수 N, 반환 값: 1 부터 N 까지의 합
2단계: N=1 이라면 1부터 1까지의 합이므로 그냥 1을 반환하 면 된다.
3단계: 1 2 3 4 .... N-2 N-1 N이렇게 두 덩어리로 나눈다. 앞부분은 N보다 작은 문제이므로 함수 호출이 가능하다고 본다.
4단계: N 까지의 합은 N-1까지의 합에다가 N만 더하면 된다.1단계
받는 파라메터: 정수 N,
반환 값: 1 부터 N 까지의 합
함수명: add
프로토타입:int add(int N);
25
MJU CE C Language Programming2단계
2단계: N=1 이라면 1부터 1까지의 합이므로 그냥 1 을 반환하면 된다.:
int add(int N){
if (N==1) return 1;
}3단계
int add(int N){
N보다 작은 문제는 해결된다고 가정하고 1+2+...+N-1 은
add(N-1); 호출 결과를 활용
}27
MJU CE C Language Programming4단계
int add(int N){
답은 N+add(N-1) 이면 된다.
}통합 :
int add(int N){
if (N>1){
return N + add(N-1);
} else {
return 1;
}
코딩 표준
함수는 전역 변수를 사용하지 않는다.29
MJU CE C Language Programming나쁜 함수의 예
int num=0;
int main(){ … square(12); }
void square(int n){
num = n * n;
}전역 변수로 값을 보존한 경우
재귀의 나쁜 예
int num=0;
int main(){ … sum(12); }
void sum(int n){
if (n>0){
sum(n-1);
num = num + n;
}
}전역 변수로 값을 보존한 경우
31
MJU CE C Language Programming재귀의 나쁜 예 2
int num=0;
int main(){ … sum(10, 0); }
int sum(int n, int result){
if (n>0){
sum (n-1, result + n);
} else {
return result;
}
}파라메터로 결과를 전달하는 경우
개선된 코드
int sum(int n){
if (n>0){
return n + sum(n-1);
} else {
return 0;
}
}장점:
1. 단순하다.
2. 문제 정의에서 바로 답이 나온다.
33
MJU CE C Language ProgrammingNot so Elegant
int length (char * len, int n){
return (len[n]!=0)? length( len, n+1):n;
}Recursive definition 예제
n! 이란1, if n=1
𝑛 𝑛 − 1 !, if 𝑛 > 1
int fact(int n){
if (n>1) return n*fact(n-1);
return 1;
}10 * 9 * 8 * 7 *... * 2 * 1
10!
9!
8!
35
MJU CE C Language ProgrammingRecursive definition 예제
int fact(int n){
if (n>1){
int result = fact(n-1);
return n * result ;
} else {
return 1;
}
}3항 연산자를 이용하는 방법
int fact(int n){
return (n>0) ? n*fact(n-1) : 1;
}37
MJU CE C Language Programminglab27_03: r_add.c
1+2+...+n 을 구하려면 1+2+...+(n-1)의 답에다 n 만 더하 면 된다.
1+2+...+(n-1) 은 재귀호출로 부터 값을 반환 받으면 된다.
함수 plus(int n) 는 1부터 n까지 덧셈하는 함수. 만일 1이면 그냥 1을 반환하면 된다. 아니면 재귀호출
테스트: plus(10), plus(20) 을 호출해 본다.프로그램을 하기 전에
Hand simulation을 해보자
그냥 더하지 왜?
재귀 호출은 대개 비 능률적 (Why?)
그럼에도 사용하는 이유는?❖
Easy for the programmer❖
Hard for the computer❖
Which (you or the computer) is more valuable?
복잡한 문제는 non-recursive solution 거의 불가능39
MJU CE C Language ProgrammingTower of Hanoi (3개, 0->2)
0 1 2
0 2, 01, 21, 0->2, 10, 12, 02
Tower of Hanoi (4개)?
0 1 2
41
MJU CE C Language ProgrammingRecursion is powerful!
니가 3개 짜리를 풀어주면
나는 4개짜리를 풀 수 있어!
니가 2개 짜리를 풀어주면
나는 3개짜리를 풀 수 있어!
니가 1개 짜리를 풀어주면
나는 2개짜리를 풀 수 있어!
1개짜리?
거야 일도 아니지.
위의 세개는 한 덩어리로 본다
0 1 2
43
MJU CE C Language Programming"N개를 x -> y로 옮겨라"에 대한 Mr. 손의 행동 지침
1. N==1 이면 내가 한다.
2. 많으면 N-1개를 x,y가 아닌 다른 곳 (temp = 3-x-y) 으로 옮기게 한다.
3. 남은 하나를 y로 옮긴다.
4. N-1개를 다시 y로 옮기게 한다.
Solution
hannoi(int n, int from, int to){// peg는 0,1,2 로 번호
만일 n==1이면 그냥 옮긴다.
n>1이면:
temp = 3 – (from +to)
hannoi(n-1, from, temp);move(from, to)
hannoi(n-1, temp, to)
}45
MJU CE C Language Programming예제(1)
주어진 문제: 양의 정수 N 이 주어졌을 때 1부터 N 까 지의 합을 구하라.
작은 문제 (trivial case) N이 1이라면 답은 아주 쉽다.그냥 1을 돌려주면 된다.
return 1;
예제 (계속)
큰 문제: N이 1보다 큰 경우이다.
어떻게 일을 나누나?❖
방법 1. 반씩 나누어 일을 처리하는 방법❖
방법 2. 약간 작은 문제로 나누어주는 방법: N-1 까지의 합 을 clone에게 구하게 한다.*방법 2로 해보자.
47
MJU CE C Language Programming방법 2
"N까지의 합" 은 "N-1 까지의 합 + N"
따라서 clone에게는 N-1 까지 더하게 한 후 그 결과에 N을 더 하면 내게 주어진 임무 끝.
각 clone이 받은 문제의 크기는 전부 다르지만 문제를 푸는 방 법은 같아야한다.Quiz
1부터 N까지의 정수를 더해서 return하는 재귀적 함 수를 정의하고자 한다. 앞서의 방법 2를 채택하기로 한 다. 함수의 이름은 r_add 라 하고 파라메터의 이름을 N 이라고 하자. 이 함수의 프로토타입은 어떻게 생겼 는가?
답 : int r_add(int N);49
MJU CE C Language ProgrammingQuiz
앞의 함수를 정의함에 있어서 받은 파라메터의 크기에 따라서 행위는 달라져야 한다. 이렇게 하기 위해서 if 의 조건에 들어갈 부분은?
if ( ){// 여기서는 clone을 불러서 처리한다.
} else {
// 여기서는 내혼자 처리한다.
}
답: N>1 // 1<N //Quiz
앞의 함수를 정의함에 있어서 받은 파라메터의 크기에 따라서 행위는 달라져야 한다. 이렇게 하기 위해서 필 요한 부분은?
if (N > 1 ){// 여기서는 clone을 불러서 처리한다.
return N + ________________ ; } else {
// 여기서는 내혼자 처리한다.
}
답: r_add(N-1)51
MJU CE C Language ProgrammingLab27_04
N factorial 은 N*(N-1)*(N-2)*...2*1 로 정의된다.N factorial을 재귀적으로 구하는 함수를 작성하고
scanf로 정수를 하나 읽어서 이 정수의 factorial을 구 하여 출력하라.
파일명 factorial.clab27_05
파일명 square.c
임의의 양의 정수 n 이 있을 때, n 보다 같거나 작은 모든 (양의)짝수의 제곱의 합을 구하는 프로그램을 recursive function 을 이용하여 작성하고 scanf 로 정수 하나를 읽어 들여 결과를 구하고 출력한다.
22
+ 42
+ 62
+ ... + n2
53
MJU CE C Language ProgrammingHanoi Tower revisited
N개의 원판을 옮기기 위해 clone을 만든다면 clone에게 시킬 일은?
N-1개 짜리를 어떻게 옮기는지는 알 필요가 없다.
제일 밑바닥 판 하나는 내가 직접 옮기고 나머지는 한덩어리로 보고 clone에게 시킨다.
만일 내가 A에서 B로 전부 옮기고 싶으면 N-1개를 C로 옮기라 고 명령한 뒤 큰 판을 B로 옮기고 또다시 N-1개를 C에서 B로 옮기라고 하면 끝난다.Quiz
하노이 타워 문제에서 peg를 번호 0,1,2 로 나타내려 고 한다. 함수의 프로토타입을 다음과 같이 할 때 정수 from은 원반들이 있는 곳, to는 목적지, size를 원반의 개수라고 하자.
void hanoi(int size, int from, int to);
만일 내가 5,0,1 를 파라메터로 받았다면 내가 최초 호 출할 clone에게 전달해야할 파라메터 값은 얼마일까?(콤마로 구분)
답: 4, 0, 255
MJU CE C Language ProgrammingQuiz
하노이 타워 문제에서 peg를 번호 0,1,2 로 나타내려 고 한다. 함수의 프로토타입을 다음과 같이 할 때 정수 from은 원반들이 있는 곳, to는 목적지, size를 원반의 개수라고 하자.
void hanoi(int size, int from, int to);
만일 내가 5,0,1 를 파라메터로 받았다면 내가 두번째 로 호출할 clone에게 전달해야할 파라메터 값은 얼마 일까? (콤마로 구분)
답: 4, 2, 1Quiz
앞의 퀴즈에서처럼 파라메터를 숫자로 적을 수는 없다. from 파라메터는 그대로 전달하면 된다. 가장 어려운 부분은 to 파라 메터를 결정하는 것인데, 내가 받은 파라메터 from, to가0,1 이면 주어야할 주어야할 to 파라메터는 2 0,2 이면 주어야할 파라메터는 1
1,2 이면 0 이다.
여기서 공통점이 있는데 어느 경우든지 세개를 모두 더하면 3이 라는 것이다.
만일 내가 받은 파라메터가 from, to 이라면 주어야할 to 파라 메터의 값은 ? 3 - ( ) 이다.57
MJU CE C Language Programminglab27_06
파일: hanoi.c
하노이 타워 프로그램을 작성하여 테스트해보라. (키 보드에서 N값을 입력)
단 실제 옮기는 것을 흉내내기 위해서는 1->21->0 0->2
...처럼 출력을 한다.
나누는 방법 2
파라메터를 나눌때 N을 N-1로 하는 것이 아니라 반씩 나눌 수 있다. 예를 들어 1부터 N까지의 합을 구한다 면 하나의 clone에게는 1부터 N/2 까지의 합을 구하 게 하고 또다른 clone에게는 N/2+1 부터 N까지를 구 하게 한 다음 이 두 결과를 합하면 된다.
파라메터는 이에 따라 시작점과 끝점이 필요.59
MJU CE C Language ProgrammingQuiz
앞서 설명한 방법에 의해 함수를 작성하려 한다. 빈칸 에 들어갈 것은? (고르기)
int r_add(int from, int to){if ( ){
return from;
} else {
// 이 경우는 둘로 나눈다.
} }
답: from==to // from >= to //배열에서 최대값 구하기
배열 0 .. N-1 에서 최대값은 배열 앞의 반에서의 최대값과 뒤 쪽 반에서의 최대값을 비교하여 둘 중에 큰 것을 고르면 된다.예를 들어
