재귀 혹은 귀납
Recursive or Inductive Definition
집합을 정의하는 방법
집합 S 를 정의하는 방법 :
• 0 은 S 의 원소이다 .
• 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 는 위의 두가지 방법으로만 만들어진다 .
S ::= 0 | S+1
A(0) = 1
A(n+1) = (n+1)*A(n)
<expr> ::= <cont>
| <name>
| (<expr> <expr>)
재귀 혹은 귀납
Recursive or Inductive Definition
반복되는 계산을 정의하는 방법
A
0= 1 S
0= 0
A
n= n*A
n-1S
n= n+S
n-1재귀함수 = 반복되는 계산을 하는 함수
재귀함수의 정의
(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!
재귀함수의 실행
(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
(define (fac n)
(cond ((= n 0) 1)
((> n 0) (* n (fac (- n 1)))) ))
재귀함수가 모든 입력에 대해서 정 의되었는가 ? 확인 방법
• 모든 입력에 대해서 정의되었는가 ?
– 모든 가능한 입력값들은 대게 무한히 많다 – 그렇다면 어떻게 “확인”할 수 있는가 ?
• Use the power of induction
– 입력값들의 집합이 귀납적으로 정의된 경우 : 대부분 – 귀납적인 정의에서는 , 집합의 모든 원소를 만들 수 있
는 방법은 유한가지가 있다 .
– 함수는 각각의 귀납규칙으로 만들어지는 입력에 대해 서 하나의 경우씩 정의하면 된다 .
(cond ((= n 0) 1) nat ::= 0
((> n 0) (* n (fac (- n 1)))) | nat+1
(define (fac n)
(cond ((= n 0) 1)
((> n 0) (* n (fac (- n 1)))) (else 1)))
자연수가 아닌 수가 입력으로 올 수 있으면 .
재귀함수의 계산이 항상 끝나는가 ? 확인 방법
• 함수가 자기자신 안에서 다시 불려질 때 , 원래의 인자보다 항상 더 작은 인자로 불리 는가 ?
• 그리고 그 인자들이 작아지면서 항상 끝장 이 나는가 ?
(define (fac n)
(cond ((= n 0) 1)
((> n 0) (* n (fac (- n 1))))
(else 1)))
끝나는 재귀함수인지 확인하는 일반적인 방법
• 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)) ))
왜 함수값만
재귀적인 정의를 허용하는가 ?
다음과 같은 정의가 불가능 할 이유가 뭐람 ? (define x (+ x 1))
(define I-love-u (more-than I-love-u)) 그 x 와 I-love-u 는 무슨 값인가 ?
무한수와 무한사랑 .
컴퓨터에 표현할 방안이 있다면 OK. ( 어떻게 ?)
Scheme 에서는 허용안한다 . 허용하는 언어도 있다 . ( 왜 ?)
한편 , 재귀적인 함수는 무슨 값인가 ?
일반 함수값과 같다 .
그 함수가 적용될 때 , 할 일 안에 자기 함수가 있는것 뿐 .
재귀함수의 정의는 letrec 의 설탕이란다 , 거의
(define (fac n) …fac… ) <expr’>
=
(letrec ((fac (lambda (n) … fac …))) <expr’>)
서로가 서로를 부르는 재귀 함수들의 정의 : (letrec ( (even (lambda (n) ... odd …)) (odd (lambda (n) … even …)) )
<expr>)
자기자신을 부르는 일이 하는 일의 맨 마지막인 경우
tail-recursive call
(define (fac n)
(cond ((= n 0) 1)
((> n 0) (* n (fac (- n 1)))) (else 1)))
(define (fac n)
(define (fac-aux n r) (cond ((= n 0) r)
((> n 0) (fac-aux (- n 1) (* n r))) (else 1)))
(fac-aux n 1) )
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
함수가 함수의 인자로
• 함수 / 프로시져는 값
• integer, boolean 등의 값과 다르지 않다 .
• 함수 / 프로시져는 함수 / 프로시져의 인자로 보낼 수 있다 .
• 그래왔었었다 :
010x2 for 02 + 12 + … + 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
덕택에 일반화된 프로시져 / 함수를 정의할 수 있다
(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 (sigma l u f op comp) (define (iter n)
(if (comp n u) 0 (op (f n) (iter (+ n 1))) ))
(iter l))
함수가 함수의 결과로
• 함수 / 프로시져는 값
• integer, boolean 등의 값과 다르지 않다 .
• 함수 / 프로시져는 함수 / 프로서져의 결과가 될 수 있다 .
• 그래왔었었다 :
(define delta 0.0001) (define (deriv f)
(lambda (x) (/ (- (f (+ x delta)) (f x)) delta) ))
Type of deriv is
deriv: (num -> num) -> (num -> num)
덕택에 일반화된 프로시져 / 함수를 정의할 수 있다
(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)))
