이산수학 - 집합과 함수

주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀 (recursive)  집합 집합은 서로 다른 (distinct) 객체의 모음이다 . 예: 한 대학에서 1학년으로 이루어지는 그룹은 한 집합이 되고 , 1학년 중 컴퓨터를 전공하는 학생의 그룹도 또 하나의 집합이 된다 . 집합의 표시는 S={a,b,c} 의 형태로 나타낼 수 있고 , 여기서 S는 집합의 이름을 나타내며 , a,b,c 는 집합의 원소 (element) 라고 한다 . a.S는 원소 a가 집합 S의 원소임을 나타내고 , a.S는 d가 집합 S의 원소가 아님을 나타낸다 .  집합 표시법 1.원소 나열법 S={1,3,5,7,9} 라는 집합은 10보다 작은 홀수를 나타내는 집합의 원소를 나열한다 . 2. 조건 제시법 S={x |x 는 10보다 작은 홀수 }로 나타낼 수 있다 . 일반적으로는 조건 제시법은 {x |x 가 가지고 있는 성질 }로 나타낸다. 공집합(empty set) 도 집합이다 .: {}, .으로 표시한다 . 집합은 다른 집합을 원소로 가질 수 있다 . 예: A={a,b}, B={c,d,{a,b}}  집합 P의 모든 원소가 또한 집합 Q의 원소가 되면 P는 Q의 부분집합이라 하고 기호로는 P⊆Q로 표현한다 . 예: 집합 {a,b} 는 집합 {a,b,c,d} 의 부분집합이고 집합 {a,c,d} 의 부분집합은 아니다 . 부분 집합의 성질 1. 모든 집합 P에 대하여 P는 P의 부분 집합이다 . 2. 공집합은 모든 집합의 부분집합이다 . 공집합이 모든 집합의 원소가 되는 것은 아니다 . 3. 집합 {.}는 집합 {{.}}의 부분집합이 아니고 집합 {.} 는 집합 {{.}}의 원소이다 .  두 집합이 같다는 말은 그 각각이 같은 객체를 포함하고 있다는 의미이다 . 두 집합 P, Q가 서로 부분집합의 관계에 있으면 두 집합은 서로 같다 . 예: P={x|x는 10보다 작거나 같으며 , 0 보다 큰 짝수의 집합 } Q={x|x=y+z, yε{1,3,5}, zε{1,3,5}} P와 Q는 같은 집합이다 .  주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀 (recursive)  합집합(union) 집합 A와 집합 B의 합집합은 그 원소로 A 또는 B 혹은 A와 B의 원소로 이루어진 집합을 의미한다 . AUB로 표시한다 . 예 {a,b}∪{c,d}={a,b,c,d} {a,b}∪{a,c}={a,b,c} {a,b}∪={a,b} {a,b}∪{{a,b}}={a,b,{a,b}}  교집합(intersection) 집합 A와 집합 B의 교집합은 그 원소로 A의 원소이면서 동시에 B의 원소인 원소로 이루어진 집합을 의미한다 . A∩B로 표시한다 . 예 {a,b}∩{a,c}={a} {a,b}∩{c,d}= . {a,b}∩. = .  정의에 의하면 다음의 합집합과 교집합은 교환 법칙이 성립한다 . A∪B=B∪A A∩B=B∩A 예: P: 이산수학 과목을 듣는학생의 집합 Q: 윈도우 프로그래밍 과목을 듣는 사람의 집합 R: 혈액형이 AB 형인 학생의 집합 교내 방송에서 이산 수업 과목과 윈도우 프로그래밍 과목에서 혈액형이 AB 형인 학생을 찾는다고 하면 우리가 찾는 학생의 집합은 (P∪Q)∩R이 된다 . 또한 우리가 찾는 학생의 집합은 이산 수학을 들으면서 혈액형이 AB 형인 학생과 윈도우 프로그래밍을 들으면서 혈액형이 AB 형인 학생의 합집합 즉, (P∩R)∪(Q∩R) 연산으로도 구해진다 .  <정리> R∩(P∪Q)=(R∩P)∪(R∩Q) 1) 먼저, R∩(P∪Q)⊆(R∩P)∪(R∩Q) 임을 증명한다 . xεR∩(P∪Q) 이라면 , 교집합의 정의에 의하여 xεR 이고, xεP∪Q 이어야 한다 . xεP∪Q에서 xεP라면 xεR∩P이고 , xεQ라면 xεR∩Q가 된다 . 따라서 xε(R∩P)∪(R∩Q)이 된다 . 결국 R∩(P∪Q)⊆(R∩P)∪(R∩Q)임을 알 수 있다 . 2) 다음으로 (R∩P)∪(R∩Q)⊆R∩(P∪Q)을 증명한다 . 먼저 xε(R∩P)∪(R∩Q) 이라고 하자 . 합집합의 정의에 의하여 xεR∩P 또는 xεR∩Q이 된다 . 따라서 xεR이고, xεP∪Q이다 . 그러므로 xεR∩(P∪Q)이 된다 . 결국 (R∩P)∪(R∩Q)⊆R∩(P∪Q)이 성립한다 . 1), 2) 에 의하여 R∩(P∪Q)=(R∩P)∪(R∩Q)이 성립한다 .  차집합(Difference) 차집합은 B의 원소에 속하지 않는 A의 원소로 이루어진 집합이다. A-B 로 표시한다 . 예: {a,b,c}-{a}={b,c} {a,b,c}-{a,d}={b,c} {a,b,c}-{d,e}={a,b,c}  대칭 차집합 (symmetric difference) 대칭 차집합은 A 또는 B에 존재하는 원소이면서 A와 B의 교집합에는 포함되지 않는 원소로 이루어지는 집합을 의미한다 . 즉, A.B=(A∪B)-(A∩B)이다 . A.B로 표현한다 . 예 {a,b}.{a,c}={b,c} {a,b}. . ={a,b} {a,b}.{a,b}= .  보집합(complement) 집합A의보집합은전체집합U에는속하고집합A에는속하지않는원소로구성된집합이다. }|{AxandUxxA...  예: 만일 학생이 이산 수학 과목에서 A학점을 받으려면 , 두 번의 퀴즈에서 점수를 잘 받아야 하고 , B학점을 받으려면 두 번 중 한번 퀴즈 점수를 잘 받으면 되고 , 두 번의 퀴즈를 전부 점수를 잘 못 받으면 C학점을 받는다고 하자 . P: 첫 번째 퀴즈를 잘 친 학생의 집합 , Q: 두 번째 퀴즈를 잘 한 학생의 집합 그러면 집합 P∩Q에 속하는 학생은 A 학점을 받을 것이고 , 집합 P.Q에 속하는 학생은 B 학점을 받을 것이다 . S를 이산 수학 과목을 듣는 학생의 집합이라고 하면 , 집합 S-(P∪Q)에 속하는 학생은 C 학점을 받을 것이다 .  멱집합(power set) 멱집합은 집합 A의 모든 부분집합을 그 원소로 가지는 집합을 의미한다 . P(A) 로 표시한다 . 예: P({a,b})={{},{a},{b},{a,b}} P({ }) = {{ }} 이고 모든 집합 A에 대하여 { }εP(A) 이면서 { }⊆P(A)이다 .  벤 다이어 그램 (Venn diagram)  주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀 (recursive)  집합의 크기 집합의 크기 : 집합을 구성하는 원소의 개수 유한집합셀수있는무한집합무한집합셀수없는무한집합  A+ : A의 계승자 (successor) A∪{A} 예 A={a,b}이면 A+ ={a,b}∪{{a,b}}={a,b,{a,b}}이다 . 예: 0= . 1={.} 2={.,{.}} 3={.,{.},{.,{.}}} ... 그러면 1=0+, 2=1+, 3=2+, … 이 집합을 집합 N으로 정의한다 .  1. 집합N은집합0를포함한다. 2. 만일집합n이집합N의한원소이면, 집합n+도집합N의원소이다. 3. N 은다른집합은포함하지않는다. 집합N 1. 집합N은집합0를포함한다. 2. 만일집합n이집합N의한원소이면, 집합n+도집합N의원소이다. 3. N 은다른집합은포함하지않는다. 집합N 집합 0= . 집합1={.} 집합2={.,{.}} 집합3={.,{.},{.,{.}}} 이집합은N={0,1,2,3,...} 의형태로명확한무한집합이된다.  1:1 대응관계두집합P, Q에대하여만약P의모든원소가Q의서로다른원소와각각짝을지을수있으면집합P의원소와집합Q의원소간에1:1 대응관계가있다고한다. 1:1 대응관계두집합P, Q에대하여만약P의모든원소가Q의서로다른원소와각각짝을지을수있으면집합P의원소와집합Q의원소간에1:1 대응관계가있다고한다. 예 집합 {a,b} 의 각 원소와 집합 {c,d}의 각 원소는 서로 1:1 대응 관계가 있다 . 왜냐하면 a는 c, b는 d 또는 a는 d, b는 c와 짝을 지을 수 있기 때문이다 . 그러나 집합 {a,b,c} 와 집합 {a,d} 는 그 원소간에 1:1 대응 관계는 불가능하다 .  어떤집합의원소와n.N 인집합n의원소간에1:1 대응관계가있으면그집합은유한집합이고그크기는n이다. 유한집합과그크기(cardinality) 어떤집합의원소와n.N 인집합n의원소간에1:1 대응관계가있으면그집합은유한집합이고그크기는n이다. 유한집합과그크기(cardinality) 예 집합 {a,b,c}, {a, .,d}, {.,{.},{.,{.}}}는 모두 크기가 3 셀수있는무한집합어떤집합의원소와집합N의원소간에1:1 대응관계가있으면그집합은셀수있는무한집합이다. 예 집합 {0,1,2,3,...} 은 명확히 셀 수 있는 무한집합이고 집합 {0,2,4,6,...} 도 셀 수 있는 무한집합이다 . 집합 {0,2,4,6,...} 의 경우에는 집합 N의 원소 i=0,1,2,... 에 대하여 2i로 대응이 될 수 있다 .  1. 두개의셀수있는무한집합의합집합은역시셀수있는무한집합이다. 2. 셀수있는무한집합이유한개존재할때그들의합집합도셀수있는무한집합이다. 3. 셀수있는무한집합이셀수있게무한개존재할때그들의합집합도셀수있는무한집합이다. 셀수있는무한집합의성질1. 두개의셀수있는무한집합의합집합은역시셀수있는무한집합이다. 2. 셀수있는무한집합이유한개존재할때그들의합집합도셀수있는무한집합이다. 3. 셀수있는무한집합이셀수있게무한개존재할때그들의합집합도셀수있는무한집합이다. 셀수있는무한집합의성질 셀 수 없는 무한 집합 예:0과 1 사이의 실수의 집합은 셀 수 없는 무한 집합이다 .  집합 연산의 원소 개수 |P∪Q| . |P| + |Q| |P ∩ Q| . min(|P|, |Q|) |P.Q| = |P| + |Q| -2 |P ∩ Q| |P-Q| . |P| -|Q| |P∪Q| = |P| + |Q| -|P ∩ Q| |P∪Q ∪R | = |P|+|Q|+|R|-|P ∩ Q|-|Q ∩ R|| P ∩ R|+ |P ∩ Q ∩ R | |P|: 집합 P의 원소 개수  예1 200명의 학생 중 50명이 이산 수학 과목을 듣고 , 140명의 학생이 윈도우 프로그래밍 과목을 듣고 , 24명의 학생이 이산 수학과 윈도우 프로그래밍 과목을 동시에 듣는다고 하자 . 만일 중간 고사가 있어서 이산 수학 혹은 윈도우 프로그래밍을 듣는 학생은 저녁에 있는 파티에 참가할 수 없다고 하면 파티에 참가할 수 있는 학생 수는 몇 명인가 ? 집합 A: 이산 수학을 듣는 학생의 집합 , 집합 B: 윈도우 프로그래밍을 듣는 학생의 집합 이산 수학 또는 윈도우 프로그래밍 과목을 듣는 학생의 수는 |A|+|B|-|A∩B|=50+140-24=166 따라서 파티에 참가할 수 있는 학생의 수는 200-166=34  예2 200명의학생 중 60명이 학부생이고 학부생 중 20명이 이산 수학을 듣고 , 45 명이 윈도우 프로그래밍 과목을 듣고 , 16명이동시에 듣는다면대학원 생 중파티에 참가할 수있는 학생 수를 구해보자 . |P∪Q ∪R |=|P|+|Q|+|R|-|P ∩ Q|-|Q ∩ R|-|P ∩ R|+ |P ∩ Q ∩ R | C: 학부생의 집합 |A∪B∪C|=50+140+60-24-20-45+16=177 따라서대학원생 중 파티에참석할 수 있는학생 수는 200-177=23  주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀 (recursive)  Method of proof:deduction( 연역) Axiom( 공리) : self-evident truth( 자명한 진리 ) .underlying assumption about mathematical structure .already proven theorem .definition( 정의) Proof ( 증명) Inference( 추론) Lemma(corollary) : 보조 정리 Theorem( 정리): conclusion(results)  귀납법(induction) Known facts 김철수도 죽었다 . 안길수도 죽었다 . . . . Conclusion(theorem) 사람은 모두 죽는다 .  수학적 귀납법 1. n=n0일 때 그 문장이 참 (true)임을 보인다 . 2. 그 문장이 n=k(k> n0 )일 때 참임을 가정하고 n=k+1일 때 참임을 보인다 .  예1: 다음을 증명하시오 . 6)12)(1( 21222.. .... nnnn. 1. n=1 일때 , 632112.. . 이므로 성립 . 2. n=k 일 때 성립한다고 가정하면 , (1) 이 성립한다 . 식 (1)의 양변에 (k+1)2을 더하면 6)12)(1( 21222.. .... kkkk. 22222)1( 6)12)(1( )1(21.. .. ......kkkkkk. 6)1)1(2)(2)(1(.... . kkk 따라서 주어진 식은 n=k+1일 때도 성립한다 . 따라서 주어진 식은 n.1에 대하여 성립한다 .  예2: 한 나라의 왕이 그들 신하가 얼마나 영리한지 알기 위하여 다음과 같이 신하들에게 말하였다고 한다 . "내가 너희들 중 일부에게 하얀색 모자를 씌우고 , 나머지에게는 검정색 모자를 씌울 것이다 . 너희들은 서로 말할 수 없고 , 자신의 모자 색은 볼 수 없지만 남들이 쓴 모자 색은 볼 수 있다 . 내가 한 시간에 한번씩 방에 들어올 텐데 너희들 중 자신이 하얀색 모자를 쓰고 있다는 사실을 아는 순간에 말하여야 한다." 이 문제는 하얀색 모자를 쓴 신하가 n 명이면 그들은 모두 n 시간 안에 그들이 자신이 하얀 모자를 쓰고 있다는 사실을 알 수 있다는 사실이 증명되었다 . n=1일때 , 즉 하얀색 모자를 쓴 신하가 1명이면, 그 신하는 왕이 첫 번째 들어왔을 때 자신이 하얀색 모자를 썼다는 사실을 알 수 있다 . 왜냐하면 그 신하는 다른 신하가 모두 검은 모자를 썼는데 반드시 한명 이상은 하얀색 모자를 씌운다고 했으므로 자신이 하얀색 모자를 썼다는 사실을 알 수 있다 . 2. n=k 일때 , 즉, 하얀색 모자를 쓴 신하가 k명일 때 그들은 k 시간 안에 그들이 하얀색 모자를 썼다는 사실을 안다고 가정하자 . 만일 하얀색 모자를 쓴 사람이 k+1 명이라면, 하얀색 모자를 쓴 사람들은 k명이 하얀색 모자를 쓰고 있다는 사실을 알 수 있는데 k 시간일 때 아무도 안 나간다는 사실에서 자신이 하얀 모자를 쓰고 있다는 사실을 알 수 있다 . 왜냐하면 자신이 검정 모자를 쓰고 있고 하얀 모자를 쓴 사람이 k명이면 가정에 의하여 k시간에 하얀 모자를 쓴 사람들은 자신이 하얀 모자를 쓰고 있다는 사실을 알았을 것이기 때문이다 . 그런데 아무도 안 나간 사실에서 자신이 하얀 모자를 썼다는 사실을 알 수 있고 k+1 시간에 자기가 하얀 모자를 쓰고 있다는 사실을 말할 수 있다 .  예3: 조각 맞추기 장난감이 있다고 하자 . 하나 이상의 조각이 아귀가 맞으면 큰 하나의 조각으로 맞추어 진다고 하자 . 블록을 하나의 조각이거나 두개 이상의 조각이 아귀가 맞아서 이루어진 큰 조각이라고 하자 . 조각 맞추기 게임은 작은 블록들을 모아서 결국 하나의 큰 블록을 만드는 게임이다 . 아귀가 맞는 두개의 블록을 하나의 블록으로 만드는 과정을 하나의 스텝이라고 하자 . 수학적 귀납법을 이용하여 n개의 조각으로 이루어진 조각 맞추기 게임이 끝나기 위해서는 n-1 의 스텝이 항상 필요하다는 것을 증명하라 . 1. n=1일 때 즉 조각이 한 개일때는 스텝이 필요없이 게임이 종료될 수 있으므로 성립한다 . 2. 조각이 n일 때(1≤n≤k) n -1 스텝이 필요하다고 가정하자 . 이제 게임이 k+1 조각으로 이루어져 있다고 가정하면 , 마지막 스텝의 바로 이전에 두개의 블록이 존재할 것이다 . 그 하나의 블록이 n1 조각으로 이루어지고, 다른 하나가 n2 조각으로 이루어진다고 가정하자 . 여기서 n1+n2=k+1이 된다 . 가정에 의하면 마지막 남은 두개의 블록은 각각 n1-1 스텝과 n2-1 스텝으로 만들어졌을 것이다 . 따라서 마지막 스텝을 포함하여 게임을 종료시키기 위하여 (n1-1)+(n2-1)+1=k 번의 스텝이 필요함을 알 수 있다 . 즉, n=k+1 일때 k번의 스텝이 필요함을 알 수 있다 .  주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀 (recursive)  함수(function) 집합 A로부터 집합 B로의 이진 관계 R은 만약 집합 A의 모든 원소 a에 대하여 (a,b)εR인 집합 B의 유일한 원소 b가 존재하면 함수라고 불린다 . a.A, b.B R: a . b A에서 B로의 함수 R에 대하여 (a,b)εR 이라는 식 대신에 R(a)=b라는 식을 쓸 수 있다 . 이때 b는 a의 이미지 (image) 라고 하며 , 집합 A를 함수 R의 정의구역 (domain), 집합 B를 함수 R의 치역(혹은 공변역 range) 라고 한다 .  함수를 그래프로 표현하면 , 집합 A={a,b,c,d,e}로부터 집합 B={A,B,C,D} 의 함수 f .a .b .c .d .e .a .b .c .d f .a .b .c .d .e .a .b .c .d g BB AA 관계g는 함수가 아니다 . A 의 d는 B의 b와 d에 매핑되기 때문이다 .  전사 함수 (onto function) A에서 B로의 함수가 있을 때 , B의 모든 원소는 하나 혹은 그 이상의 A의 원소의 이미지이면 그 함수를 전사 함수라고 한다 . .a .b .c .d .e .a .b .c .d B A  일대일 함수 (one-to-one function) A에서 B로의 함수가 어떠한 A의 두 원소도 같은 이미지를 갖지 않으면 일대일 함수라고 한다 . .a .b .c .d .e .a .b .c .d .e .f A B  일대일 전사 함수 A에서 B로의 함수가 전사 함수이면서 동시에 일대일 함수이면 일대일 전사 함수라고 한다 . .a .b .c .d .e .a .b .c .d .e AB  예 집합 A를 노동자의 집합이라고 하고 , 집합 B, C, D 를 직장의 집합이라고 하자 . A에서 B로의 전사 함수가 정의되려면 모든 직장에 대하여 적어도 하나 이상의 노동자를 가지고 있어야 한다 . A에서 C로의 일대일 함수가 정의되려면 어떠한 노동자도 같은 직장을 가져서는 안된다 . A에서 D로의 일대일 전사 함수가 정의되려면 모든 직장이 각각 노동자를 가져야 하고 , 다른 노동자는 각각 다른 일자리를 가져야 한다 .  역함수 f를 집합 A에서 집합 B로 일대일 전사 함수라고 하자 . f의 역함수는 B에 속하는 한 원소 b에 대하여 f(a)=b인 유일한 A의 한 원소 a로 대응시키는 함수를 의미 기호는 f-1 로 나타낸다 . 즉, f(a)=b 이면 f-1(b) = a 가 된다 . 함수 f의 역함수가 존재하려면 반드시 f가 일대일 전사함수여야 한다. 함수 f가 일대일 전사 함수가 아니면 함수 f의 역함수가 존재할 수 없다 .  예1 함수 f: 정수에서 정수로의 함수로 f(x)=x+2 함수 f의 역함수가 존재하는가 ? 만일 존재한다면 역함수는 어떻게 되는가 ? 모든 정수 x,y에 대하여 x≠y 이면 x+2≠y+2 이므로 함수 f는 일대일 함수이고 , 모든 y에 대하여 x+2=y를 만족하는 x가 존재하므로 함수 f는 전사함수이다 . 따라서 함수 f는 일대일 전사함수이므로 역함수가 존재한다 . f-1(y) = y-2 가 역함수가 된다 .  예2 함수 f: 정수에서 정수로의 함수 , f(x)=x2 함수 f의 역함수가 존재하는가 ? f(2)=f(-2) 이므로 함수 f는 일대일 전사함수가 아니다 . 따라서 역함수가 존재하지 않는다 .  복합 함수 함수 f: A . B 함수g: B . C A에서 C로의 복합 함수 h는 모든 원소 aεA에 대하여 h(a)=g(f(a))를 만족하는 함수이다 . h=g.f로 표현된다 . 예 집합 A={a1,a2,a3}, 집합 B={b1,b2,b3}, 집합 C={c1,c2,c3 } 함수 f는 f(a1)=b1, f(a2)= b2, f(a3)= b3,로 정의되고 , 함수 g는 g(b1)=c1, g(b2)= c2, g(b3)= c3로 정의된다면 h=g.f는 다음과 같이 정의된다 . h(a1)=c1, h(a2)= c2, h(a3)= c3  비둘기 집 법칙 (pigeonhole principle) 비둘기 집 법칙은 만일 많은 비둘기가 있고 , 적은 수의 비둘기 집이 있으면 반드시 어떤 비둘기 집은 둘 이상의 비둘기가 들어가야만 한다는 법칙이다 . 수학적으로 표현하면 다음과 같다 . D와 R을 유한 집합이라 하자 . 만일 |D|>|R| 이면 D에서 R로의 모든 함수 f에 대하여 d1, d2.D이고 f(d1)=f(d2)인 d1, d2가 반드시 존재한다 . 예 만일 13명의 사람이 있다면 그 둘 중 적어도 두 명 이상은 같은 달에 태어났을 것이다 . 이 경우 13명의 사람은 비둘기에 해당하고, 12 달은 비둘기 집에 해당한다 .  주요 내용 . 집합 . 집합의 조합 . 유한 집합과 무한 집합 . 수학적 귀납법 . 함수 . 재귀(recursion)  재귀(recursion) 다음의 두 단계에 의해 정의되는 것을 재귀 정의 (recursive definition) 라고 한다 . 기반 단계 : 0일 때의 함수 값을 명시 재귀 단계 : 특정 상수에 대한 함수 값을 더 작은 상수에 대한 함수 값으로부터 얻는 규칙을 명시 예: 다음과 같이 재귀적으로 함수가 정의되어 있다고 하자 . f(0) = 3, f(n+1)=2f(n)+3 f(1)=2f(0)+3=2*3+3=9, f(2)=2*f(1)+3=2*9+3=21, f(3)=2*f(2)+3=2*21+3=45, f(4)=2*f(3)+3=2*45+3=93  예2: factorial 함수 F(n)=n!를 재귀 정의로 보여라 기반 단계 : F(0)=1 재귀 단계 : F(n+1)=(n+1)F(n) 예3: 피보나치 수 (fibonacci numbers) 는 다음과 같이 재귀적으로 정의된다 . 기반 단계 : f0=0, f1=1 재귀 단계 : fn = fn-1 + fn-2  큰문제를작은문제로분해하여문제를해결하는방법의하나로재귀를사용할수있다. 재귀알고리즘큰문제를작은문제로분해하여문제를해결하는방법의하나로재귀를사용할수있다. 재귀알고리즘 예1: factorial 함수 계산 procedure factorial(n: positive integer) if n=1 then factorial(n) :=1 else factorial(n):= n*factorial(n-1)  예2: 파보나치 수 계산 알고리즘 procedure factorial(n: nonnegative integer) if n=0 then fibonacci(0) :=0 else if n=1 then fibonacci(1) := 1 else fibonacci(n):= fibonacci(n-1)+fibonacci(n-2)