재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법

Presentation on theme: "재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법"— Presentation transcript:

1 재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법
n이 S의 원소라면 n+1도 S의 원소이다. 집합 S는 위의 두가지 방법으로만 만들어진다. 계산식들의 집합을 정의하는 방법: primitive constants are expressions names are expressions ( followed by two expressions and ) are expressions 계산식들의 집합 <expr>은 위의 세가지 방법으로만 만들어진다. A라는 자연수 짝들의 집합을 정의하는 방법: (0,1)은 A의 원소 (n,m)이 A의 원소라면 (n+1,(n+1)*m)도 A의 원소 집합 A는 위의 두가지 방법으로만 만들어진다. <expr> ::= <cont> | <name> | (<expr> <expr>) A(0) = 1 A(n+1) = (n+1)*A(n)

2 재귀 혹은 귀납 Recursive or Inductive Definition 반복되는 계산을 정의하는 방법
A0 = S0 = 0 An = n*An Sn = n+Sn-1 재귀함수 = 반복되는 계산을 하는 함수

3 재귀함수의 정의 (define (<name> <name>*) <expr>)
(define (fac n) (cond ((= n 0) 1) ((> n 0) (* n (fac (- n 1)))) )) The type of fac fac: nat -> nat 0! = 1 (n+1)! = (n+1)*n!

4 재귀함수의 실행 (fac 4) (* 4 (fac 3)) (* 4 (* 3 (fac 2)))
(define (fac n) (cond ((= n 0) 1) ((> n 0) (* n (fac (- n 1)))) )) (fac 4) (* 4 (fac 3)) (* 4 (* 3 (fac 2))) (* 4 (* 3 (* 2 (fac 1)))) (* 4 (* 3 (* 2 (* 1 (fac 0))))) (* 4 (* 3 (* 2 (* 1 1)))) (* 4 (* 3 (* 2 1))) (* 4 (* 3 2)) (* 4 6) 24

5 재귀함수가 모든 입력에 대해서 정의되었는가? 확인 방법
모든 가능한 입력값들은 대게 무한히 많다 그렇다면 어떻게 “확인”할 수 있는가? Use the power of induction 입력값들의 집합이 귀납적으로 정의된 경우: 대부분 귀납적인 정의에서는, 집합의 모든 원소를 만들 수 있는 방법은 유한가지가 있다. 함수는 각각의 귀납규칙으로 만들어지는 입력에 대해서 하나의 경우씩 정의하면 된다. (cond ((= n 0) 1) nat ::= 0 ((> n 0) (* n (fac (- n 1)))) | nat+1

6 ((> n 0) (* n (fac (- n 1)))) (else 1)))
(define (fac n) (cond ((= n 0) 1) ((> n 0) (* n (fac (- n 1)))) (else 1))) 자연수가 아닌 수가 입력으로 올 수 있으면.

7 재귀함수의 계산이 항상 끝나는가? 확인 방법 함수가 자기자신 안에서 다시 불려질 때, 원래의 인자보다 항상 더 작은 인자로 불리는가? 그리고 그 인자들이 작아지면서 항상 끝장이 나는가? (define (fac n) (cond ((= n 0) 1) ((> n 0) (* n (fac (- n 1)))) (else 1)))

8 끝나는 재귀함수인지 확인하는 일반적인 방법 Given (define (f x) … (f x’) … )
끝나는 재귀함수인지 확인하는 일반적인 방법 Given (define (f x) … (f x’) … ) where x and x’ in X How to prove that (f x) terminates for any input x: Find an order x > x’ such that the order in X is “not infinitely descending.”(가다보면 끝이있는) And show that the argument to every recursive call follows that > order. (define (fac n) (if (= n 0) 1 … (fac (- n 1)) …)) (define (bar a b c) (if (= b 0) c … (bar (+ a 1) (- b 1) (* a b)) ))

9 왜 함수값만 재귀적인 정의를 허용하는가? 다음과 같은 정의가 불가능 할 이유가 뭐람? (define x (+ x 1))
(define I-love-u (more-than I-love-u)) 그 x와 I-love-u는 무슨 값인가? 무한수와 무한사랑. 컴퓨터에 표현할 방안이 있다면 OK. (어떻게?) Scheme에서는 허용안한다. 허용하는 언어도 있다.(왜?) 한편, 재귀적인 함수는 무슨 값인가? 일반 함수값과 같다. 그 함수가 적용될 때, 할 일 안에 자기 함수가 있는것 뿐.

10 재귀함수의 정의는 letrec의 설탕이란다, 거의
(define (fac n) …fac… ) <expr’> = (letrec ((fac (lambda (n) … fac …))) <expr’>) 서로가 서로를 부르는 재귀 함수들의 정의: (letrec ( (even (lambda (n) ... odd …)) (odd (lambda (n) … even …)) ) <expr>)

11 자기자신을 부르는 일이 하는 일의 맨 마지막인 경우 tail-recursive call
(define (fac n) (cond ((= n 0) 1) ((> n 0) (* n (fac (- n 1)))) (else 1))) (define (fac-aux n r) (cond ((= n 0) r) ((> n 0) (fac-aux (- n 1) (* n r))) (fac-aux n 1) )

12 tail-recursive call의 실행
(fac 4) (fac-aux 4 1) (fac-aux 3 (* 4 1)) (fac-aux 3 4) (fac-aux 2 (* 3 4)) (fac-aux 2 12) (fac-aux 1 (* 2 12)) (fac-aux 1 24) (fac-aux 0 (* 1 24)) (fac-aux 0 24) 24

13 함수가 함수의 인자로 함수/프로시져는 값 integer, boolean등의 값과 다르지 않다.
함수/프로시져는 함수/프로시져의 인자로 보낼 수 있다. 그래왔었었다: 010x2 for … + 102 (define (sum lower upper f) (if (> lower upper) 0 (+ (f lower) (sum (+ lower 1) upper f)))) The type of sigma is sigma: num * num * (num -> num) -> num

14 덕택에 일반화된 프로시져/함수를 정의할 수 있다
(define (sum lower upper f) (if (> lower upper) 0 (+ (f lower) (sum (+ lower 1) upper f)) )) (define (sigma l u f op) (if (> l u) 0 (op (f l) (sigma (+ l 1) u f op)) (define (sigma l u f op comp) (if (comp l u) 0 (op (f l) (sigma (+ l 1) u f op comp)) (define (iter n) (if (comp n u) 0 (op (f n) (iter (+ n 1))) (iter l))

15 함수가 함수의 결과로 함수/프로시져는 값 integer, boolean등의 값과 다르지 않다.
함수/프로시져는 함수/프로서져의 결과가 될 수 있다. 그래왔었었다: (define delta ) (define (deriv f) (lambda (x) (/ (- (f (+ x delta)) (f x)) delta) )) Type of deriv is deriv: (num -> num) -> (num -> num)

16 덕택에 일반화된 프로시져/함수를 정의할 수 있다
(define (sum lower upper f) (if (> lower upper) 0 (+ (f lower) (sum (+ lower 1) upper f)) )) (define (sigma lower upper) (lambda (f) (define (iter n) (if (> n upper) 0 (+ (f n) (iter (+ n 1))))) (iter lower) (define one-to-ten (sigma 1 10)) (one-to-ten (lambda (n) (* n n))) (one-to-ten (lambda (n) (* n 2)))

17 덕택에 다양한 정도로 요약된 것들에 이름붙일 수 있다
덕택에 다양한 정도로 요약된 것들에 이름붙일 수 있다 give-fn-bounds give-bounds-fn (define (give-fn-bounds lower upper) …) (define (give-bounds-fn f)

18 고차함수/프로시져 higher-order function/procedure
함수/프로시져를 인자로 받거나 함수/프로시져를 결과로 내놓는 함수/프로시져 Type of such higher-order functions: (int -> int) -> int int * int -> (int -> int) (int -> bool) -> (num -> num) money -> (year -> car list)