CSE117 프로그래밍기초강의노트 1 7 재귀함수 Recursive Functions 한양대학교 ERICA캠퍼스컴퓨터공학과도경구 2013년 2학기 (version 0.6) 1 c 도경구 (2013). 본문서는한양대학교 ERICA 캠퍼스컴퓨터공학과프로그래밍기초강의용으로제

1. 귀납정의 Inductive Definition 수학에서는 1보다큰거나같은정수를자연수natural number라고하지만, 컴퓨터과학에서는일반적으로여기에 0을포함시킨다. 자연수는무한히많이있어서집합으로보면무한집합이다. N = {n n 0, n Integer} = {0, 1, 2,...} 이무한집합을유한하게표현하는방법이있을까? 자연수의귀납정의 1. ( 기초Basis) 0은자연수이다. 2. ( 귀납Induction) n이자연수이면, n + 1도자연수이다. 3. 그외에다른자연수는없다. 자연수의개수는무한하지만, 이귀납정의를이용하면아무리큰자연수라도유한한시간안에그수가자연수임을확인할수있다. 예를들어, 4가자연수인지확인하고싶다고하자. ( 귀납 ) 에의해서 3이자연수이면 4도자연수라고할수있다. 그러면 3이자연수인지만확인하면된다. 또다시 ( 귀납 ) 에의해서 2가자연수이면 3도자연수라고할수있다. 그러면 2가자연수인지만확인하면된다. 또다시 ( 귀납 ) 에의해서 1이자연수이면 2도자연수라고할수있다. 그러면이제 1이자연수인지만확인해보면된다. 또다시 ( 귀납 ) 에의해서 0이자연수이면 1도자연수라고할수있다. 그러면이제는 0이자연수인지만확인해보면된다. 그런데 ( 기초 ) 에의하면 0은자연수이다. 따라서 1이자연수이고, 따라서 2가자연수이고, 따라서 3이자연수이고, 따라서 4가자연수임을확인하였다. 이러한자연수의귀납구조를써서자연수계산을재귀함수recursive function로표현할수있다. 2. 선형재귀 Linear Recursion 2.1 계승구하기자연수 n의계승factorial n! 은 n (n 1) (n 2)... 2 1을계산한결과이다. 이를자연수의귀납정의구조를이용하여다음과같이재귀로정의할수있다. 0! = 1 n! = n (n 1)! (n > 0) 자연수 n의계승은자연수의귀납정의구조의틀에맞춰서그대로사용하여재귀recursive로정의하였다. 즉, 자연수귀납정의의기초basis인 0의계승은 1로정의한다. 그리고 1 이상의자연수 n의계승은 n 1의계승에 n을곱한값으로정의한다. 이렇게재귀로정의해놓으면, 자연수의개수는무한히많이있지만, 아무리큰자연수라도유한한시간내에계승값을구할수있다. 예를들어, 3의계승값은 2의계승값에다 3을곱하여 1

구하고, 2의계승값은 1의계승값에다 2를곱하여구하고, 1의계승값은 0의계승값에다 1을곱하여구하고, 0의계승값은재귀정의에따라 1이다. 이구조를그대로본따서 Python 재귀함수로다음과같이작성할수있다. def fac(n): if n == 0: return 1 return n * fac(n-1) 이프로그램을 Python 실행기로실행해보자. >>> fac(5) 120 이프로그램이어떻게작동하는지다음과같이계산추적해보면계산과정을이해할수있다. fac(5) 5 * fac(4) 5 * (4 * fac(3)) 5 * (4 * (3 * fac(2))) 5 * (4 * (3 * (2 * fac(1)))) 5 * (4 * (3 * (2 * (1 * fac(0))))) 5 * (4 * (3 * (2 * (1 * 1)))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 fac(5) 를호출하면바로이어서 fac(4) 를호출하고또바로이어서 fac(3) 을호출하고, 이와같은과정을 fac(0) 을호출할때까지계속반복한다. 즉, 곱셈을하기위해서양쪽인수가모두있어야하는데왼쪽인수만알고있으므로오른쪽인수를구하기위해서재귀호출을하는것이다. 마침내 fac(0) 의결과값인 1을알면바로 fac(1) 의값을계산할수있고, fac(1) 의결과값을알면바로 fac(2) 의값을계산할수있고, 이와같은과정을반복하여마침내 fac(5) 의결과값을얻는다. 음수입력처리 fac(-3) 을 Python 실행기로계산해보자. 어떻게될까? 다음과같은오류메시지를내주며비 정상적으로계산을멈춘다. 2

RuntimeError: maximum recursion depth exceeded in comparison 왜그럴까? if문의조건식이 True가되는상황이절대생기지않기때문에이론적으로는재귀호출을무한반복하여계산이끝나지않는다. 그런데 Python 실행기는이를방지하기위하여일정횟수이상연속적으로재귀호출을반복하면실행오류로취급하여오류를발생하며비정상적으로계산을끝낸다. 이런상황을방지하고항상정상적으로답을내주며계산이끝나게하기위해서는음수의입력에대한대비책이있어야한다. 일단다음과같이프로그램하면비정상적으로끝나는경우는없어지지만음수의계승은 1이아니므로좋은방법은아니다. def fac(n): if n <= 0: return 1 return n * fac(n-1) 이를완벽하게해결하는방법은 9장에서자세히배운다. 계산복잡도 계산시간 : n 의크기에비례 사용공간 : n 의크기에비례 꼬리재귀 Tail Recursion 앞에서공부한계승구하는함수는재귀호출하여계산한뒤곱할수를기억해두어야하므로재귀호출의횟수만큼추가공간이필요했었다. 만약재귀호출한다음계산이끝나고돌아와서더이상할계산이없으면이러한추가공간이필요없을것이다. 재귀호출이그함수의마지막계산이되는재귀함수를꼬리재귀함수라고한다. 위의계승구하는함수도꼬리재귀함수로만들수있다. 계산을남겨두지않기위해서미리곱해버리고그값만기억하고있으면된다. 즉, 곱할수가나오면바로곱해서결과를기억하게하면된다. 그러기위해서는중간계산결과를기억하는변수를하나만들고, 시작값은 1로한다. ( 어떤수에다 1을곱해도자신이되므로곱셈의기본값은 1이다.) 이중간계산결과는재귀함수에인수를하나추가하여전달한다. 다음프로그램은꼬리재귀형태로작성한계승구하는함수이다. def loop(n,ans): if n <= 0: return ans return loop(n-1,n*ans) def fact(n): 3

return loop(n,1) loop 함수의첫째파라미터는루프의종료를제어하기위한카운터counter 역할을하고둘째파라미터는계산결과를축적해나가는누산기accumulator 역할을한다. 이함수를계산추적해보면다음과같다. fact(5) loop(5,1) loop(5-1,5*1) loop(4,5) loop(4-1,4*5) loop(3,20) loop(3-1,3*20) loop(2,60) loop(2-1,2*60) loop(1,120) loop(1-1,1*120) loop(0,120) 120 재귀호출하기전에필요한곱셈을하며, 계산결과는인수로전달한다. 아렇게꼬리재귀형태로재귀호출을하면더이상곱할인수를저장해둘필요가없어서공간을절약할수있다. 계산복잡도 계산시간 : n 의크기에비례 사용공간 : 상수 함수의지역화위에서 loop 함수는 fact 만사용하는함수이므로사용자에게공개할필요가없으므로, 다음과같이 fact 함수안에넣어서외부로부터감출수있다. def fact(n): def loop(n,ans): if n <= 0: return ans return loop(n-1,n*ans) return loop(n,1) loop함수는이제 fact 함수내부용으로만사용하고, 밖에서는보이지않으므로사용할수없다. 이렇게함수내부용으로만정의된함수를지역함수local function라고한다. 즉, fact 함수는 loop 함수를지역함수로만들어외부에서보이지않도록감추었다. 이를캡슐화라고한다. 4

꼬리재귀와반복문 while문으로작성한다음함수와위의꼬리재귀함수를비교해보자. def facw(n) : ans = 1 while n > 0 : ans = n * ans n = n - 1 return ans 꼬리재귀는반복문과사실상똑같다. 일단꼬리재귀함수를만들고난후, 거의기계적으로반복문을유도해낼수있다. 2.2 b n 계산하기 b는유리수이고 n은자연수일때, b n 은 b를 n번곱한것과같다. b n 을 n의귀납정의구조를이용하여다음과같이재귀로정의할수있다. b 0 = 1 b n = b b n 1 (n > 0) 이를 Python 함수로바꾸면, def exp(b,n): if n == 0: return 1 return b * exp(b,n-1) 계산추적 exp(2,7) 2 * exp(2,6) 2 * (2 * exp(2,5)) 2 * (2 * (2 * exp(2,4))) 2 * (2 * (2 * (2 * exp(2,3)))) 2 * (2 * (2 * (2 * (2 * exp(2,2))))) 2 * (2 * (2 * (2 * (2 * (2 * exp(2,1)))))) 2 * (2 * (2 * (2 * (2 * (2 * (2 * exp(2,0))))))) 2 * (2 * (2 * (2 * (2 * (2 * (2 * 1)))))) 2 * (2 * (2 * (2 * (2 * (2 * 2))))) 5

2 * (2 * (2 * (2 * (2 * 4)))) 2 * (2 * (2 * (2 * 8))) 2 * (2 * (2 * 16)) 2 * (2 * 32) 2 * 64 128 계산복잡도 계산시간 : n 의크기에비례 사용공간 : n 의크기에비례 꼬리재귀함수 def expt(b,n): def loop(b,n,r): if n == 0: return r return loop(b,n-1,b*r) return loop(b,n,1) 여기서 loop 함수의둘째파라미터는루프의종료를제어하기위한카운터역할을하고셋째파라미터는계산결과를축적해나가는누산기역할을한다. 그런데첫째파라미터는변하지않고항상참조가가능하므로파라미터로들고다닐필요가없다. 첫째파라미터를제거한프로그램은다음과같다. def expt(b,n): def loop(n,r): if n == 0: return r return loop(n-1,b*r) return loop(n,1) 계산추적 expt(2,7) loop(7,1) loop(7-1,2*1) loop(6,2) 6

loop(6-1,2*2) loop(5,4) loop(5-1,2*4) loop(4,8) loop(4-1,2*8) loop(3,16) loop(3-1,2*16) loop(2,32) loop(2-1,2*32) loop(1,64) loop(1-1,2*64) loop(0,128) 128 계산복잡도 계산시간 : n 의크기에비례 사용공간 : 상수 연습문제 : 반복문버전 위의꼬리재귀함수를 while 문을이용한함수로변환해보자. 2.3 b n 더빨리계산하기 n이짝수이면 b n = (b n/2 ) 2 과같은등식이성립한다는수학적성질을이용하면 b n 을다음과같이재귀로정의할수있다. b 0 = 1 b n = (b n/2 ) 2 b n = b b n 1 (n > 0, n is even) (n > 0, n is odd) 이를 Python 함수로바꾸면, def fastexp(b,n): if n == 0: return 1 elif n % 2 == 0: return fastexp(b,n/2)**2 return b * fastexp(b,n-1) 계산추적 fastexp(2,7) 2 * fastexp(2,6) 2 * fastexp(2,3)**2 7

2 * (2 * fastexp(2,2))**2 2 * (2 * fastexp(2,1)**2)**2 2 * (2 * (2 * fastexp(2,0))**2)**2 2 * (2 * (2 * 1)**2)**2 2 * (2 * 2**2)**2 2 * (2 * 4)**2 2 * 8**2 2 * 64 128 계산복잡도 계산시간 : log n 의크기에비례 사용공간 : log n 의크기에비례 꼬리재귀함수 def fastexpt(b,n): def loop(b,n,r): if n == 0: return r elif n % 2 == 0: return loop(b**2,n/2,r) return loop(b,n-1,b*r) return loop(b,n,1) 계산추적 fastexpt(2,7) loop(2,7,1) loop(2,7-1,2*1) loop(2,6,2) loop(2**2,6/2,2) loop(4,3,2) loop(4,3-1,4*2) loop(4,2,8) loop(4**2,2/2,8) loop(16,1,8) loop(16,1-1,16*8) loop(16,0,128) 128 8

계산복잡도 계산시간 : log n 의크기에비례 사용공간 : 상수 연습문제 : 반복문버전 위의꼬리재귀함수를 while 문을이용한함수로변환해보자. 9

3. 나무가지형재귀 Tree Recursion 3.1 피보나찌수열 피보나찌수열Fibonacci sequence은이전두개의수를더하여다음수를정하는수열로서다음과 같이무한히나열할수있다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,... n번째피보나찌수는자연수의귀납구조를이용하여다음과같이재귀로정의할수있다. F ib(0) = 0 F ib(1) = 1 F ib(n) = F ib(n 1) + F ib(n 2) (n > 1) 즉, 각정수 n에대한피보나찌수 F ib(n) 값을표로그려보면다음과같다. n 0 1 2 3 4 5 6 7 8 9 10 F ib(n) 0 1 1 2 3 5 8 13 21 34 55 피보나찌재귀프로그램위의재귀정의는다음과같이 Python 함수로만들어바로실행해볼수있다. def fib(n): if n == 0: return 0 elif n == 1: return 1 return fib(n-1) + fib(n-2) 이프로그램을실행추적해보면다음과같이된다. fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + fib(3) ((fib(2) + fib(1)) + fib(2)) + fib(3) (((fib(1) + fib(0)) + fib(1)) + fib(2)) + fib(3) (((1 + fib(0)) + fib(1)) + fib(2)) + fib(3) (((1 + 0) + fib(1)) + fib(2)) + fib(3) ((1 + fib(1)) + fib(2)) + fib(3) ((1 + 1) + fib(2)) + fib(3) 10

(2 + fib(2)) + fib(3) (2 + (fib(1) + fib(0))) + fib(3) (2 + (1 + fib(0))) + fib(3) (2 + (1 + 0)) + fib(3) (2 + 1) + fib(3) 3 + fib(3) 3 + (fib(2) + fib(1)) 3 + ((fib(1) + fib(0)) + fib(1)) 3 + ((1 + fib(0)) + fib(1)) 3 + ((1 + 0) + fib(1)) 3 + (1 + fib(1)) 3 + (1 + 1) 3 + 2 5 이프로그램의실행추적을통해서실행순서를관찰해보면다음그림의화살표와같은순서로재귀호출이진행되었음을알수있다. ( 이를깊이우선나무가지훑기라고하는데언젠가는자세히배울날이오리라.) 이프로그램을 fib.py라는이름의파일에저장하고내 imac에서실행기에올려서 fib(10), fib(20), fib(30), fib(40) 을차례로실행해보았다. 다음과같이결과가나왔다. >>> fib(10) 55 >>> fib(20) 6765 >>> fib(30) 11

832040 >>> fib(40) 102334155 여기서각호출의결과를얻는데걸린시간이판이하게다르다는점을주목해야한다. 첫두결과는눈깜빡할사이에얻었다. fib(30) 는커서가세번깜빡인후에결과가나왔다. 그런대로참을만하다. 그런데 fib(40) 은커서가계속깜빡이는데결과가나오지않는다. 커서깜빡이는횟수를세기시작했는데 30번이넘은후에후회를하기시작했다. 타이머를심어놓을것을... 그런데이왕시작했으니참고계속세었다. 막포기하려는데결과가나왔다. 198번깜빡인후였다. 왜이런현상이발생할까? 40번째피보나찌수를구하는데나의고성능 imac이왜이렇게밖에하지못할까? 손으로탁상용계산기를두드렸어도 3분안에답을구했을텐데... 계산복잡도문제는위프로그램이계산을수행하면서동일한재귀호출를엄청나게많이중복호출하여시간과공간을잡아먹는다는사실이다. 호출횟수를따져보자. fib(n) 을호출하면, 재귀호출을 2번하고, 이는각각재귀호출을 2번씩하여총 4번재귀호출을하고, 또이는각각재귀호출을 2번씩하여총 8번재귀호출을하고, 또이는각각재귀호출을 2번씩하여총 16번재귀호출을하고, 또이는각각재귀호출을 2번씩하여총 32번재귀호출을하고, 어렇게계속하면 40번째에총재귀호출횟수는 2 40 번이되어 1조번이넘게재귀호출을한다. 똑같은호출을얼마나많이중복시도하는지상상해보면끔직하다. 이러니내최신 imac도답을구하는데시간이걸릴수밖에없지. 사용하는공간도따져보면한번재귀호출할때마다결과를얻은후돌아와서해야할남은계산을기억해두어야하는데, 이도 n을기준으로지수적으로비례한만큼많이필요하다. n이조금만커도아마내메모리를다잡아먹고모자라서빠알간피를토하며 (!) 죽어버릴것이다. 결과적으로 fib(n) 을계산하는데필요한시간과공간은다음과같이요약할수있다. 계산시간 : 2 n 에비례한만큼걸리고 사용공간 : 2 n 에비례한만큼필요하다. 결과적으로위에서만든피보나찌재귀함수는실용적으로사용할수없다. 그러나다행히이재귀함수는꼬리재귀함수형태로변형할수있다. 꼬리재귀함수 중복계산을피하기위해서는작은피보나찌수부터계산한후에기억해두었다가큰피보나찌 수를구할때사용하면중복계산을피할수있다. 그런데피보나찌수는정수시퀀스에서바로 앞의두수만가지고가지고계산이가능하다. 즉, 다음과같이테이블을만들어보자. n 0 1 2 3 4 5 6 7 8 9 10 F ib(n) 0 1 1 2 3 5 8 13 21 34 55 F ib(n 1) 0 1 1 2 3 5 8 13 21 34 12

그러면 n = k인열에서 F ib(n) 값을구하려면 n = k 1 열의 F ib(n 1) 값과 F ib(n) 값을더하면된다. 그리고 n = k인열에서 F ib(n 1) 값은 n = k 1 열의 F ib(n) 이된다. 이런식으로왼쪽에서오른쪽으로테이블을구축해나갈수있다. 이렇게테이블을구축하면 n = k 열의 F ib(n 1) 값과 F ib(n) 값을구할때필요한열은 n = k 1 열뿐이다. 즉, n = k 2 이하의열의값은알필요가없다. 결국, 각 n과같은열에있는 F ib(n 1) 와 F ib(n) 값은 n + 1 열의 F ib(n 1) 와 F ib(n) 값을구하는데사용된다. 이점에착안하여위의재귀함수를꼬리재귀함수형태로변형해보자. 최근에계산한피보나찌수를두개기억해두고다음피보나찌수를계산해야하므로, 재귀호출의인수 a와 b를 2개추가하여이를전달한다. a에는가장최근에계산한피보나찌수를 b에는바로그전에계산한피보나찌수를담는다. 그러면 9번째피보나찌수를구하기위해서다음과같이테이블을왼쪾에서오른쪽으로구축해나간다. a의초기값을 1로, b의초기값을 0으로두고, n을 9로두고시작하여다음과같이각열을계산해나가면 n이 0이되는순간 b의값이 9번째피보나찌수가된다. n 9 8 7 6 5 4 3 2 1 0 a 1 1 2 3 5 8 13 21 34 55 b 0 1 1 2 3 5 8 13 21 34 그렇게작성한꼬리재귀함수로작성한피보나찌함수는다음과같다. def fibt(n): def loop(a,b,n): if n == 0: return b return loop(a+b,a,n-1) return loop(1,0,n) 이프로그램을계산추적해보자. fibt(9) loop(1,0,9) loop(1,1,8) loop(2,1,7) loop(3,2,6) loop(5,3,5) loop(8,5,4) loop(13,8,3) loop(21,13,2) loop(34,21,1) loop(55,34,0) 34 13

각재귀호출의인수값이위테이블의각열과일치함을볼수있다. 계산복잡도이프로그램은 loop을정확하게 n + 1번호출하고추가공간을사용하지않으므로매우호율적이다. 계산시간 : n의크기에비례 사용공간 : 상수이프로그램을실행기에올려서 fibt(10), fibt(20), fibt(30), fibt(40) 을차례로실행시켜보자. 앞에서와는다르게결과가모두눈깜빡할사이에나온다. 반복문버전 이꼬리재귀함수는 while 문으로다음과같이기계적으로변환할수있다. def fibw(n): a, b = 1, 0 while n > 1: a, b, n = a+b, a, n-1 return b 3.2 하노이탑 Tower of Hanoi 재귀로문제풀기 원반이 n 개쌓여있고, 1 번말뚝에서 3 번말뚝으로어떻게옮길지재귀로생각해보자. n 1 개의원반을옮기는방법은안다고가정하면, n 번째원반은다음과같이옮기면된다. 14

1. 1번말뚝에서 n 1개의원반을 2번말뚝으로옮긴다. 2. 1번말뚝의맨아래에있었던가장큰원반을 3번말뚝으로옮긴다. 3. 2번말뚝에있는 n 1개의원반을 3번말뚝으로옮긴다. 아하! 이제 n 1개원반을옮기는방법만알아내면되니문제가조금간단해졌네! 이렇게조금씩문제를줄여나가면결국가장쉬운문제에도달하겠지? 원반을옮기는순서를프린트하는재귀함수는다음과같다. def towerofhanoi(n): def loop(n,src,dst,tmp): if n == 0: pass loop(n-1,src,tmp,dst) print("move from", src,"to",dst) loop(n-1,tmp,dst,src) loop(n,"r1","r3","r2") 이프로그램을실제로돌려보자. towerofhanoi(3) towerofhanoi(5) towerofhanoi(8) towerofhanoi(16) 실행결과가어떻게나타나는가? 계산시간이얼마나걸리는지생각해보자. 이재귀함수를꼬리재귀형태로바꿀수있을까? 15

프로그래밍연습문제 곱셈함수만들기단순무식한곱셈함수만들기곱셈연산자가없다면덧셈과뺄셈연산자만가지고다음과같이곱셈함수를구현할수있다. 여기서 m과 n 값은항상 0보다크거나같다고가정한다. 즉, 음수의곱셈은고려하지않는다. def mult(m,n): if n == 0: return 0 return m + mult(m,n-1) 이재귀함수는덧셈을하는횟수가 n에비례하고, 공간사용량도 n에비례한다. 1. 위프로그램을공간사용량이상수에비례하는꼬리재귀형태로함수를재작성하시오. 2. 위에서작성한꼬리재귀함수를참조하여재귀함수의호출없이 while 문을사용하여곱셈 함수를재작성하시오. 빠른곱셈함수만들기다음두함수 double과 halve를이용하여곱셈함수의덧셈을하는회수가 log n에비례하는곱셈함수 multfast를재귀함수로작성하시오. def double(n): return n * 2 def halve(n): return n // 2 즉, 두번째인수 n이짝수인경우 multfast(double(m),halve(n)) 을재귀호출하고, 홀수인경우 m + multfast(m,n-1) 을재귀호출하도록작성하면된다. 1. 작성한 multfast 함수를공간사용량이상수에비례하는꼬리재귀형태로함수를재작성하시오. 2. 위에서작성한꼬리재귀함수를참조하여재귀함수의호출없이 while문을사용하여곱셈함수를재작성하시오. 16

러시아농부의곱셈함수만들기러시아농부들은두수를곱할때구구단없이덧셈, 두배하기 (double함수), 반나누기 (halve 함수 ) 만가지고곱셈을계산하는영특한방법을사용했다. 곱셈방법은다음과같다. 곱할두수를나란히적는다. 첫째수는두배를하고, 둘째수는반으로나누되나머지는버린다. 이과정을둘째수가 1이될때까지계속한다. 둘째수가짝수인줄은모두지운다. 남은줄의첫째수를모두더한값이답이다. 예를들어, 57 86은다음과같이계산한다. 1. 이를구현하는 multrp 함수를재귀함수로작성하시오. 2. 작성한 multrp 함수를꼬리재귀함수로재작성하시오. 3. multrp 함수와 multfast 함수를덧셈의횟수와사용공간을기준으로성능을비교분석해보시오. 17

조합계산하기 수학에서조합 combination 은 n 개에서순서에상관없이 r 개를뽑는가지수이다. 이를구하는공 식은다음과같이재귀로정의한다. nc 0 = 1 nc n = 1 nc r = n 1 C r 1 + n 1 C r if r 0 and n r 이공식은다음과같이간단하게 Python 함수로작성할수있다. def comb(n,r): if r == 0: return 1 elif r == n: return 1 return comb(n-1,r-1) + comb(n-1,r) 그런데이함수를돌려보자. 일단 comb(30,3) 과 comb(30,27) 을실행해보자. 바로답을내준다. 그런데 comb(30,7) 과 comb(30,23) 을실행해보면, 시간이조금더걸린다. 참을만하다. 그런데 comb(30,10) 과 comb(30,20) 을실행해보면, 시간이훨씬더많이걸린다. 언제답이나오나궁금해하면서잠시기다렸더니결국나타난다. comb(30,15) 를시도해보자. 인내심을요구한다. 언젠가는답을내주긴하지만말이다. 왜인수에따라서계산시간이천차만별일까? comb(100,50) 을실행해보자. 어떤결과가나오나?... 결국이함수는현실적으로사용할수없다. 다행히도이함수도꼬리재귀형으로바꾸어현실적으로사용가능한함수로만들수있다. 프랑스수학자였던빠스깔Pascal이고안해낸삼각형을이용하면된다. 빠스깔의삼각형은다음과같은모양을지닌다. 이삼각형을잘살펴보면결국조합의계산결과를나열해놓은삼각형테이블임을알수있다. 18

0C 0 1C 0 1 C 0 2C 0 2 C 1 2 C 2 3C 0 3 C 1 3 C 2 3 C 3 4C 0 4 C 1 4 C 2 4 C 3 4 C 4 5C 0 5 C 1 5 C 2 5 C 3 5 C 4 5 C 5 결국하향식재귀로조합을계산하는대신, 빠스깔삼각형을꼭지점부터채워나가며만들어서원하는조합에해당하는값을삼각테이블을얻으면훨씬빨리계산할수있다. 이점에착안하여인수의크기에상관없이빨리답을내주는 comb 함수를작성하시오. 꼬리재귀버전을먼저작성하고, 이를토대로 while루프버전을작성하시오. 19