귀납과 재귀 (Induction and Recursion) 이산수학(Discrete Mathematics) 귀납과 재귀 (Induction and Recursion) 2016년 봄학기 강원대학교 컴퓨터과학전공 문양세

수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 강의 내용 Induction and Recursion 수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 재귀 알고리즘(Recursive Algorithms)

Introduction Mathematical Induction A powerful technique for proving that a predicate P(n) is true for every natural number n, no matter how large. (모든 자연수 n에 대해서 P(n)이 true임을 보일 수 있는 매우 유용한 방법임) Essentially a “domino effect” principle. (앞에 것이 성립하면(넘어지면), 바로 다음 것도 성립한다(넘어진다.) Based on a predicate-logic inference rule: P(0) n0 (P(n)P(n+1)) n0 P(n) P(0)가 true이고, P(n)이 true라 가정했을 때 P(n+1)이 true이면, 모든 n에 대해 P(n)이 true이다.

Intuitively, we can prove that induction is correct. Validity of Induction Mathematical Induction Intuitively, we can prove that induction is correct. P(1) = T since (P(0) = T)  (P(0)P(1) = T) P(2) = T since (P(1) = T)  (P(1)P(2) = T) P(3) = T since (P(2) = T)  (P(2)P(3) = T) … P(n) = T since (P(n-1) = T)  (P(n-1)P(n) = T)

Outline of an Inductive Proof Mathematical Induction Want to prove n P(n)… Induction basis (or base case): Prove P(0). (기본 단계) Induction step: Prove n P(n)P(n+1). (귀납적 단계) E.g. use a direct proof: Let nN, assume P(n). (induction hypothesis) Under this assumption, prove P(n+1). Inductive inference rule then gives n P(n). Can also be used to prove nc P(n) for a given constant cZ, where maybe c0. (Base로 0이 아닌 상수 c를 사용할 수 있다.) In this circumstance, the base case is to prove P(c) rather than P(0), and the inductive step is to prove nc (P(n)P(n+1)).

By induction hypothesis P(n) Induction Examples (1/4) Mathematical Induction Prove that the sum of the first n odd positive integers is n2. That is, prove: (처음 n개 홀수의 합은 n2와 동일하다.) Proof by Induction Induction basis: Let n=1. Since 1 = 12, P(1) is true. Induction step: Let n1, assume P(n), and prove P(n+1). P(n) By induction hypothesis P(n)

Induction Examples (2/4) Mathematical Induction Prove that n>0, n<2n. Let P(n)=(n<2n) : Induction basis: P(1) = (1 < 21) = (1 < 2) = T. Induction step: For n>0, prove P(n)P(n+1). Assuming n<2n, prove n+1 < 2n+1. Note n + 1 < 2n + 1 (by inductive hypothesis) < 2n + 2n (because 1 < 2=2∙20  2∙2n-1= 2n) = 2n+1 So n + 1 < 2n+1, and we’re done.

Induction Examples (3/4) Mathematical Induction Prove that the sum of the first n positive integers is n(n+1)/2. Let P(n) = Induction basis: Let P(1) = Induction step: Let n1, assume P(n), and prove P(n+1).

Induction Examples (4/4) Mathematical Induction Prove when n2. Induction basis: n = 2, Induction step: Assume P(n), and prove P(n+1).

Second Principle of Induction (강 귀납법) Mathematical Induction Characterized by another inference rule: P(0) n0: (0kn P(k))  P(n+1) n0: P(n) Difference with 1st principle is that the inductive step uses the fact that P(k) is true for all smaller k<n+1, not just for k=n. (Induction step에서 k=n인 경우 대신에, k<n+1인 모든 k에 대해 P(k)가 true라 가정한다.) P(0)가 true이고, P(0),…,P(n)이 모두 true라 가정했을 때 P(n+1)이 true이면, 모든 n에 대해 P(n)이 true이다.

Example of Second Principle Mathematical Induction Show that every n>1 can be written as a product p1p2…ps of some series of s prime numbers. Let P(n)=“n has that property” (모든 양의 정수는 소수의 곱으로 나타낼 수 있다.) Induction basis: n=2, let s=1, p1=2. Thus, P(2) = T. Induction step: Let n2. Assume 2kn: P(k). Consider n+1. If prime, let s=1, p1=n+1. Done. Else n+1=ab, where 1<an and 1<bn. Then a=p1p2…pt and b=q1q2…qu. Then n+1= p1p2…pt q1q2…qu, a product of s=t+u primes.

수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 강의 내용 Induction and Recursion 수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 재귀 알고리즘(Recursive Algorithms)

Recursive Definitions (재귀의 정의) Recursion In induction, we prove all members of an infinite set have some property P by proving the truth for larger members in terms of that of smaller members. (귀납적 정의에서는, “무한 집합의 모든 멤버가 어떠한 성질 P를 가짐”을 보이기 위하여, “작은 멤버들을 사용하여 큰 멤버들이 참(P의 성질을 가짐)임”을 증명하는 방법을 사용하였다.) In recursive definitions, we similarly define a function, a predicate or a set over an infinite number of elements by defining the function or predicate value or set-membership of larger elements in terms of that of smaller ones. (재귀적 정의에서는, “작은 멤버들에 함수/술어/집합을 적용(정의)하여 모든 멤버들을 정의”하는 방법을 사용한다.)

Recursion (재귀) Recursion Recursion is a general term for the practice of defining an object in terms of itself (or of part of itself). (재귀란 객체를 정의하는데 있어서 해당 객체 자신을 사용하는 것을 의미한다.) An inductive proof establishes the truth of P(n+1) recursively in terms of P(n). (귀납적 증명은 P(n+1)이 참임을 증명하기 위하여 재귀적으로 P(n)을 사용하는 것으로 해석할 수 있다.) There are also recursive algorithms, definitions, functions, sequences, and sets.

Recursively Defined Functions Recursion Simplest case: One way to define a function f:NS (for any set S) or series an=f(n) is to: Define f(0). For n>0, define f(n) in terms of f(0),…,f(n−1). E.g.: Define the series an :≡ 2n recursively: Let a0 :≡ 1. For n>0, let an :≡ 2an-1.

Suppose we define f(n) for all nN recursively by: Another Example Recursion Suppose we define f(n) for all nN recursively by: Let f(0)=3 For all nN, let f(n+1)=2f(n)+3 What are the values of the following? f(1)= f(2)= f(3)= f(4)= 9 21 45 93

Recursive Definition of Factorial Recursion Given an inductive definition of the factorial function F(n) :≡ n! :≡ 23…n. Base case: F(0) :≡ 1 Recursive part: F(n) :≡ n  F(n-1). F(1)=1 F(2)=2 F(3)=6

The Fibonacci Series Recursion The Fibonacci series fn≥0 is a famous series defined by: f0 :≡ 0, f1 :≡ 1, fn≥2 :≡ fn−1 + fn−2 1 1 2 3 5 8 13

Inductive Proof about Fibonacci Series Recursion Theorem: fn < 2n. Proof: By induction. Base cases: f0 = 0 < 20 = 1 f1 = 1 < 21 = 2 Inductive step: Use 2nd principle of induction (strong induction). Assume k<n, fk < 2k. Then fn = fn−1 + fn−2 is < 2n−1 + 2n−2 < 2n−1 + 2n−1 = 2n. 

Recursively Defined Sets Recursion An infinite set S may be defined recursively, by giving: A small finite set of base elements of S. (유한 개수의 기본 원소를 제시) A rule for constructing new elements of S from previously-established elements. (새로운 원소를 만드는 방법을 제시) Example: Let 3S, and let x+yS if x,yS. What is S? (= {3, 6, 9, 12, 15, …})

수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 강의 내용 Induction and Recursion 수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 재귀 알고리즘(Recursive Algorithms)

예제: A procedure to compute an. procedure power(a≠0: real, nN) Introduction Recursive Algorithms Recursive definitions can be used to describe algorithms as well as functions and sets. (재귀적 정의를 수행한 경우, 손쉽게 알고리즘의 함수/집합으로 기술할 수 있다.) 예제: A procedure to compute an. procedure power(a≠0: real, nN) if n = 0 then return 1 else return a · power(a, n−1)

Efficiency of Recursive Algorithms The time complexity of a recursive algorithm may depend critically on the number of recursive calls it makes. (재귀 호출에서의 시간 복잡도는 재귀 호출 횟수에 크게 의존적이다.) 예제: Modular exponentiation to a power n can take log(n) time if done right, but linear time if done slightly differently. (잘하면 O(log(n))이나, 조금만 잘못하면 O(n)이 된다.) Task: Compute bn mod m, where m≥2, n≥0, and 1≤b<m.

Modular Exponentiation Algorithm #1 Recursive Algorithms Uses the fact that bn = b·bn−1 and that x·y mod m = x·(y mod m) mod m. procedure mpower(b≥1,n≥0,m>b N) {Returns bn mod m.} if n=0 then return 1; else return (b·mpower(b,n−1,m)) mod m; Note this algorithm takes (n) steps!

(log n) steps Modular Exponentiation Algorithm #2 Uses the fact that Recursive Algorithms Uses the fact that b2k = bk·2 = (bk)2, x·y mod m = x·(y mod m) mod m, and x·x mod m = (x mod m)2 mod m. procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return mpower(b,n/2,m)2 mod m else return (mpower(b,n−1,m)·b) mod m (첫 번째 mpower()는 한번 call되고, 그 값을 제곱하는 것임) What is its time complexity? (log n) steps

A Slight Variation of Algorithm #2 Recursive Algorithms Nearly identical but takes (n) time instead! procedure mpower(b,n,m) {same signature} if n=0 then return 1 else if 2|n then return (mpower(b,n/2,m)·mpower(b,n/2,m)) mod m else return (mpower(b,n−1,m)·b) mod m The number of recursive calls made is critical.

Recursive Euclid’s Algorithm (예제) Recursive Algorithms procedure gcd(a, b: positive integer) while b  0 begin r := a mod b {r = a % b} a := b b := r end return a procedure gcd(a,bN) if a = 0 then return b else return gcd(b mod a, a) Note recursive algorithms are often simpler to code than iterative ones… (Recursion이 코드를 보다 간단하게 하지만…) However, they can consume more stack space, if your compiler is not smart enough. (일반적으로, recursion은 보다 많은 stack space를 차지한다.)

Recursion vs. Iteration (1/3) Recursive Algorithms Factorial – Recursion procedure factorial(nN) if n = 1 then return 1 else return n factorial(n – 1) Factorial – Iteration procedure factorial(nN) x := 1 for i := 1 to n x := i  x return x

Recursion vs. Iteration (2/3) Recursive Algorithms Fibonacci – Recursion procedure fibonacci(n: nonnegative integer) if (n = 0 or n = 1) then return n else return (fibonacci(n–1) + fibonacci(n–2)) Fibonacci – Iteration procedure fibonacci(n: nonnegative integer) if n = 0 then return 0 else x := 0, y := 1 for i := 1 to n – 1 z := x + y, x := y, y := z return z

Recursion vs. Iteration (3/3) Recursive Algorithms 재귀(recursion)는 프로그램을 간단히 하고, 이해하기가 쉬운 장점이 있는 반면에, 각 호출이 스택을 사용하므로, depth가 너무 깊어지지 않도록 조심스럽게 프로그래밍해야 함 컴퓨터에게 보다 적합한 방법은 반복(iteration)을 사용한 프로그래밍이나, 적당한 범위에서 재귀를 사용하는 것이 바람직함

The merge takes (n) steps, and merge-sort takes (n log n). Recursive Algorithms procedure sort(L = 1,…, n) if n>1 then m := n/2 {this is rough ½-way point} L := merge(sort(1,…, m), sort(m+1,…, n)) return L The merge takes (n) steps, and merge-sort takes (n log n).

Merge Sort (예제) (2/2) – skip Recursive Algorithms The Merge Routine procedure merge(A, B: sorted lists) L = empty list i:=0, j:=0, k:=0 while i<|A|  j<|B| {|A| is length of A} if i=|A| then Lk := Bj; j := j + 1 else if j=|B| then Lk := Ai; i := i + 1 else if Ai < Bj then Lk := Ai; i := i + 1 else Lk := Bj; j := j + 1 k := k+1 return L

수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 강의 내용 Induction and Recursion 수학적 귀납법(Mathematical Inductions) 재귀(Recursion) 재귀 알고리즘(Recursive Algorithms)

Homework #5 Recursive Algorithms