함수의 재귀 호출

(1)

::

Recursion

함수의 재귀 호출

(2)

학습 목표



Recursion 의 필요성



Recursion 의 정의 및 사용법

교재: 30장

recursion = recursive call

= 재귀 호출

(3)

3

MJU CE C Language Programming

함수란?



병속의 지니와 같다.



평소에는 공간을 차지하지 않는다.

❖

함수 선언



일을 시킬 때만 나타난다.

❖

함수 호출

(4)

미스터 손 (동영상)

(5)

5

호출시 일어나는 일



오공아, 요괴가 세마리 나타났다. 어떻게 좀 해 봐라.

main 함수 sohn

호출

(6)

Activation Record=함수의 실체

함수 main 함수 sohn

운영체제

(7)

7

재귀 호출?



내가 나에게 일을 시킨다???

(8)

자기 자신의 사본을 이용하기



"치키치키 차카차카... 펑 !"

한마리는 내가

처치할테니 나머지는

니가 알아서 해! 알았어.

(9)

9

복사본도 또 복사를...

한마리는 내가

처치할테니 나머지는 니가 알아서 해!

알았어.

"치키치키 차카차카.."

한마리는 내가

처치할테니 나머지는 니가 알아서 해!

펑!

알았어.

(10)

Recursion (재귀호출)

Stack top (최근에 생긴 activation record)

호출 호출

호출 결과반환

결과반환

(11)

11

CFL의 재귀 호출 (demo)

(12)

재귀 호출의 방법



보통 함수의 호출과 같다.



void fun(){



...



fun();



...



}

(13)

13

lab27_01: 재귀함수의 호출



파일명: self.c



함수 fun 은 적절한 메시지("Hello\n")를 한 줄 출력

하고 1초간 쉰 후 자기 자신을 재귀 호출하는 함수이다.



prototype:

void fun();



1초간 쉬려면 sleep(1); 을 사용한다.

#include <unistd.h> 필요



프로그램을 강제 종료 시키려면 ctrl-C 를 누른다. (주 의: ctrl-z 가 아님)

(14)

무한 호출의 제한...

옙.셋! 치키치키...

넌 둘 까지만이야. 알았어. 둘! 치키치키...

넌 하나까지만이야 알았어. 하나!

끝이네.

오공아, 너 자신을

셋이상으로 복제하지 말아라.

(15)

15

시도 1

(16)

앗. 끝 났는데...

(17)

17

완성 (sohn2.cfl)

(18)

무한 호출의 제한

void fun(int n){

printf("%d\n", n);

if (n>0){

fun(n-1);

}

return;

}

int main(){

fun(3);

}

main

3 2 1

n

0

n

(19)

19

lab27_02/sohn.c



자기 자신을 호출하는 함수



int Mr_sohn(int n) 을 정의한다.



Mr_sohn()에서는 "요괴 X 마리 남았음."과 같은 메시 지를(숫자는 자신이 받은 파라메터 값) 한번 출력한 뒤 파라메터로 받은 값이 0보다 크면 자기 자신을 호출하 고 (이 때 실질 파라메터는 자신이 받은 값보다 1 작은 값을 준다.) 그렇지 않으면 그냥 0을 반환한다.



main에서는 정수를 입력받아 Mr_sohn을 호출한다.

(20)

재귀적 문제 정의



1 부터 N-1 까지의 정수의 합이 X라면



1부터 N까지의 정수의 합은 얼마일까?

(21)

21

게으른 Mr.Sohn의 덧셈

야, 1에서 9까지

더하면 얼마냐? 야, 1에서 8까지

더하면 얼마냐 야, 1에서 7까지 더하면 얼마냐

오공아, 1에서 10까지 더하면 얼마냐?.

바보냐?

1이지

야, 1에서 1까지 더하면 얼마냐

...

45+10= 음...

55 입니다.

36+9= 음...

45 입니다.

(22)

재귀적으로 문제 해결하기

1.

함수가 할 일을 정의한다. 이때 주어지는 것은 무엇인지, 결과 는 무엇인지를 정확히 정의해야 한다.

2.

만일 내가 받은 일이 "충분히 작을 때" 어떻게 처리할 것인지를 정한다. (trivial case)

3.

만일 내가 받은 일이"클 때" (non-trivial case)어떻게 일을 나 누어 다른 clone 을 호출할 것인지를 정해야 한다. 현재 받은 일보다 작은 일은 문제없이 해결된다고 가정한다.

4.

clone에게 시켜서 받은 결과를 어떻게 하면 "나의 임무"로 연 결시킬 수 있는지를 정한다.

(23)

23

예제



정수 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만 더하면 된다.

(24)

1단계



받는 파라메터: 정수 N,



반환 값: 1 부터 N 까지의 합



함수명: add



프로토타입:

int add(int N);

(25)

25

2단계



2단계: N=1 이라면 1부터 1까지의 합이므로 그냥 1 을 반환하면 된다.:



int add(int N){



if (N==1) return 1;



}

(26)

3단계



int add(int N){



N보다 작은 문제는 해결된다고 가정하고 1+2+...+N-1 은



add(N-1); 호출 결과를 활용



}

(27)

27

4단계



int add(int N){



답은 N+add(N-1) 이면 된다.



}

통합 :

int add(int N){

if (N>1){

return N + add(N-1);

} else {

return 1;

}

(28)

코딩 표준



함수는 전역 변수를 사용하지 않는다.

(29)

29

나쁜 함수의 예



int num=0;



int main(){ … square(12); }



void square(int n){



num = n * n;



}

전역 변수로 값을 보존한 경우

(30)

재귀의 나쁜 예



int num=0;



int main(){ … sum(12); }



void sum(int n){



if (n>0){



sum(n-1);



num = num + n;



}



}

전역 변수로 값을 보존한 경우

(31)

31

재귀의 나쁜 예 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;



}



}

파라메터로 결과를 전달하는 경우

(32)

개선된 코드



int sum(int n){



if (n>0){



return n + sum(n-1);



} else {



return 0;



}



}

장점:

1. 단순하다.

2. 문제 정의에서 바로 답이 나온다.

(33)

33

Not so Elegant



int length (char * len, int n){



return (len[n]!=0)? length( len, n+1):n;



}

(34)

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)

35

Recursive definition 예제



int fact(int n){



if (n>1){



int result = fact(n-1);



return n * result ;



} else {



return 1;



}



}

(36)

3항 연산자를 이용하는 방법



int fact(int n){



return (n>0) ? n*fact(n-1) : 1;



}

(37)

37

lab27_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을 해보자

(38)

그냥 더하지 왜?



재귀 호출은 대개 비 능률적 (Why?)



그럼에도 사용하는 이유는?

❖

Easy for the programmer

❖

Hard for the computer

❖

Which (you or the computer) is more valuable?



복잡한 문제는 non-recursive solution 거의 불가능

(39)

39

Tower of Hanoi (3개, 0->2)

0 1 2

0 2, 01, 21, 0->2, 10, 12, 02

(40)

Tower of Hanoi (4개)?

0 1 2

(41)

41

Recursion is powerful!

니가 3개 짜리를 풀어주면

나는 4개짜리를 풀 수 있어!

1개짜리?

거야 일도 아니지.

(42)

위의 세개는 한 덩어리로 본다

0 1 2

(43)

43

"N개를 x -> y로 옮겨라"에 대한 Mr. 손의 행동 지침

1. N==1 이면 내가 한다.

2. 많으면 N-1개를 x,y가 아닌 다른 곳 (temp = 3-x-y) 으로 옮기게 한다.

3. 남은 하나를 y로 옮긴다.

4. N-1개를 다시 y로 옮기게 한다.

(44)

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)

45

예제(1)



주어진 문제: 양의 정수 N 이 주어졌을 때 1부터 N 까 지의 합을 구하라.



작은 문제 (trivial case) N이 1이라면 답은 아주 쉽다.

그냥 1을 돌려주면 된다.

 return 1;

(46)

예제 (계속)



큰 문제: N이 1보다 큰 경우이다.



어떻게 일을 나누나?

❖

방법 1. 반씩 나누어 일을 처리하는 방법

❖

방법 2. 약간 작은 문제로 나누어주는 방법: N-1 까지의 합 을 clone에게 구하게 한다.

*방법 2로 해보자.

(47)

47

방법 2



"N까지의 합" 은 "N-1 까지의 합 + N"



따라서 clone에게는 N-1 까지 더하게 한 후 그 결과에 N을 더 하면 내게 주어진 임무 끝.



각 clone이 받은 문제의 크기는 전부 다르지만 문제를 푸는 방 법은 같아야한다.

(48)

Quiz



1부터 N까지의 정수를 더해서 return하는 재귀적 함 수를 정의하고자 한다. 앞서의 방법 2를 채택하기로 한 다. 함수의 이름은 r_add 라 하고 파라메터의 이름을 N 이라고 하자. 이 함수의 프로토타입은 어떻게 생겼 는가?



답 : int r_add(int N);

(49)

49

Quiz



앞의 함수를 정의함에 있어서 받은 파라메터의 크기에 따라서 행위는 달라져야 한다. 이렇게 하기 위해서 if 의 조건에 들어갈 부분은?



if ( ){

// 여기서는 clone을 불러서 처리한다.

} else {

// 여기서는 내혼자 처리한다.

}



답: N>1 // 1<N //

(50)

Quiz



앞의 함수를 정의함에 있어서 받은 파라메터의 크기에 따라서 행위는 달라져야 한다. 이렇게 하기 위해서 필 요한 부분은?



if (N > 1 ){

// 여기서는 clone을 불러서 처리한다.

return N + ________________ ; } else {

// 여기서는 내혼자 처리한다.

}



답: r_add(N-1)

(51)

51

Lab27_04



N factorial 은 N*(N-1)*(N-2)*...2*1 로 정의된다.

N factorial을 재귀적으로 구하는 함수를 작성하고

scanf로 정수를 하나 읽어서 이 정수의 factorial을 구 하여 출력하라.



파일명 factorial.c

(52)

lab27_05



파일명 square.c



임의의 양의 정수 n 이 있을 때, n 보다 같거나 작은 모든 (양의)짝수의 제곱의 합을 구하는 프로그램을 recursive function 을 이용하여 작성하고 scanf 로 정수 하나를 읽어 들여 결과를 구하고 출력한다.



2

²

+ 4

²

+ 6

²

+ ... + n

²

(53)

53

Hanoi Tower revisited



N개의 원판을 옮기기 위해 clone을 만든다면 clone에게 시킬 일은?



N-1개 짜리를 어떻게 옮기는지는 알 필요가 없다.



제일 밑바닥 판 하나는 내가 직접 옮기고 나머지는 한덩어리로 보고 clone에게 시킨다.



만일 내가 A에서 B로 전부 옮기고 싶으면 N-1개를 C로 옮기라 고 명령한 뒤 큰 판을 B로 옮기고 또다시 N-1개를 C에서 B로 옮기라고 하면 끝난다.

(54)

Quiz



하노이 타워 문제에서 peg를 번호 0,1,2 로 나타내려 고 한다. 함수의 프로토타입을 다음과 같이 할 때 정수 from은 원반들이 있는 곳, to는 목적지, size를 원반의 개수라고 하자.



void hanoi(int size, int from, int to);



만일 내가 5,0,1 를 파라메터로 받았다면 내가 최초 호 출할 clone에게 전달해야할 파라메터 값은 얼마일까?

(콤마로 구분)



답: 4, 0, 2

(55)

55

Quiz



하노이 타워 문제에서 peg를 번호 0,1,2 로 나타내려 고 한다. 함수의 프로토타입을 다음과 같이 할 때 정수 from은 원반들이 있는 곳, to는 목적지, size를 원반의 개수라고 하자.



void hanoi(int size, int from, int to);



만일 내가 5,0,1 를 파라메터로 받았다면 내가 두번째 로 호출할 clone에게 전달해야할 파라메터 값은 얼마 일까? (콤마로 구분)



답: 4, 2, 1

(56)

Quiz



앞의 퀴즈에서처럼 파라메터를 숫자로 적을 수는 없다. from 파라메터는 그대로 전달하면 된다. 가장 어려운 부분은 to 파라 메터를 결정하는 것인데, 내가 받은 파라메터 from, to가

0,1 이면 주어야할 주어야할 to 파라메터는 2 0,2 이면 주어야할 파라메터는 1

1,2 이면 0 이다.



여기서 공통점이 있는데 어느 경우든지 세개를 모두 더하면 3이 라는 것이다.



만일 내가 받은 파라메터가 from, to 이라면 주어야할 to 파라 메터의 값은 ? 3 - ( ) 이다.

(57)

57

lab27_06



파일: hanoi.c



하노이 타워 프로그램을 작성하여 테스트해보라. (키 보드에서 N값을 입력)



단 실제 옮기는 것을 흉내내기 위해서는 1->2

1->0 0->2

...처럼 출력을 한다.

(58)

나누는 방법 2



파라메터를 나눌때 N을 N-1로 하는 것이 아니라 반씩 나눌 수 있다. 예를 들어 1부터 N까지의 합을 구한다 면 하나의 clone에게는 1부터 N/2 까지의 합을 구하 게 하고 또다른 clone에게는 N/2+1 부터 N까지를 구 하게 한 다음 이 두 결과를 합하면 된다.



파라메터는 이에 따라 시작점과 끝점이 필요.

(59)

59

Quiz



앞서 설명한 방법에 의해 함수를 작성하려 한다. 빈칸 에 들어갈 것은? (고르기)



int r_add(int from, int to){

if ( ){

return from;

} else {

// 이 경우는 둘로 나눈다.

} }



답: from==to // from >= to //

(60)

배열에서 최대값 구하기



배열 0 .. N-1 에서 최대값은 배열 앞의 반에서의 최대값과 뒤 쪽 반에서의 최대값을 비교하여 둘 중에 큰 것을 고르면 된다.

예를 들어



int a[10]; 과 같은 배열이라면



a[0]~a[4] 중의 최대값과 a[5]~a[9] 중의 최대값을 비교하면 결정된다.



rmax(int a[], int start, int end);



main: rmax(b, 0, 9);



rmax: middle = (start+end)/2;



앞의 반 재귀 호출은 rmax(b, start, middle)로 호출한다. 뒤 는??

(61)

61

lab27_07/rmax.c



배열 0 .. N-1 에서 최대값은 배열 앞의 반에서의 최대 값과 뒤쪽 반에서의 최대값을 비교하여 둘 중에 큰 것 을 고르면 된다.



int rmax(int a[], int start, int end);



형태의 프로토타입을 이용한다.



함수내부에서는 start와 end 값을 비교하여 같으면 재 귀호출을 하지 않는다.



main에서는 10개의 정수를 표준입력에서 입력한 후 rmax(a, 0, 9); 를 호출한다.

(62)

숙제



Fibonnacci sequence ?



Parenthesis matching ?

(63)

63

단원 요구사항



재귀 함수 호출이 가능한 이유를 activation record로 설명할 수 있어야 한다.



주어진 문제를 재귀적인 정의로 (pseudo code 혹은 서술식) 바꾸어 기술할 수 있어야 한다.



재귀적으로 정의가 주어진 문제를 C언어의 재귀 함수 로 작성할 수 있어야 한다.