1.2 프로시저와 프로세스
;
;; 어떤 문제를 풀기 위해 어떤 식으로 프로그래밍 언어를 써야 하는지 모르는 상태다.
;; 어떤 프로시저를 정의해야 하는데 프로시저를 돌릴 때 어떤 결과가 나오는지 미리 그려낼 줄 아는 경험 부족한 상태.
;; 프로시저: 한 컴퓨터 프로세스가 어떻게 나아가는지 밝힌 것.
;; 프로시저가 만들어내는 프로세스의 몇가지 꼴(shape)의 보기를 들것이다.
;
1.2.1 되돌거나 반복하는 프로세스
;
;; 되도는 프로세스 recursion
;; - 연산을 바로 수행하지 못하고 뒤로 미루는(deferred operation) 모양
;; 반복하는 프로세스 iterative
;; - 상태변수 존재. 계산의 크기가 늘어나지 않는다.
;; 되도는 프로세스와 되도는 프로시저
;; - 프로시저는 되도는 모양이더라도(자신을 다시 호출) 프로세스는 그렇지 않을 수 있다. - linera iterative process
;; tail recursion : 꼬리에서 자기 자신을 다시 호출하면서 recursive process가 안되도록 하는 것.
;; - http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Tail-recursive_functions
;; fact(n) = n * (n -1) * (n-2) * ... * 2 * 1
(define (fact1 n)
(if (= n 1)
1
(* n (fact1 (- n 1)))))
;; recursive process
;; (fact1 4)
;; (* 4 (fact 3))
;; (* 4 (* 3 (fact 2)))
;; (* 4 (* 3 (* 2 (fact 1))))
;; (* 4 (* 3 (* 2 1)))
;; (* 4 (* 3 2))
;; (* 4 6)
;; 24
;; iterative process
;; product < counter * product
;; counter < counter - 1
(define (fact2 n)
(define (iter p c)
(if (= c 1)
p
(iter (* p c) (- c 1))))
(iter 1 n))
;; (fact2 4)
;; (iter 1 4)
;; (iter 4 3)
;; (iter 12 2)
;; (iter 24 1)
;; 24
;; ex 1.9
;; (+ 4 5)
;; (inc (+ 3 5))
;; (inc (inc (+ 2 5)))
;; (inc (inc (inc (+ 1 5))))
;; (inc (inc (inc (inc (+ 0 5)))))
;; (inc (inc (inc (inc 5)))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9
(define (inc a)
(+ a 1))
(define (dec a)
(- a 1))
(define (plus-1 a b)
(if (= a 0)
b
(inc (plus-1 (dec a) b))))
;; (plus-1 2 3)
;; (inc (plus-1 1 3))
;; (inc (inc (plus-1 0 3)))
;; (inc (inc 3))
;; (inc 4)
;; 5
(define (plus-2 a b)
(if (= a 0)
b
(plus-2 (dec a) (inc b))))
;; (plus-2 2 3)
;; (plus-2 1 4)
;; (plus-2 0 5)
;; 5
;; ex 1.10
;; 애커만 함수 http://en.wikipedia.org/wiki/Ackermann_function
;; primitive recursive function은 아니지만 total computable function
;; primitive recursive function은 항상 total computable function이다.
;; A(x, y)
;; 0 if y = 0
;; 2 * y if x = 0
;; 2 if y = 2
;; A(x - 1, A(x, y - 1))
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
;; (A 0 n) : (* 2 n)
;; (A 1 n) : (exp 2 n)
;; (A 2 n) : n = 1 이면 1
;; n > 1 이면 (exp 2 (exp 2 (exp 2 ... 2))) -> n번 반복
;; (A 3 n) : n = 1 이면 1
;; n > 1 이면 ???
;
1.2.2 여러 갈래로 되도는 프로세스
;
;; 피보나치 수열 f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1
;;
;; 0 -> 0
;; 1 -> 1
;; recursive process
(define (fib1 n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib1 (- n 1)) (fib1 (- n 2))))))
;; fib1 -> n -> pi^n / root(5)
;; f(n) = f(n-1) + f(n-2)
;; iterative process
(define (fib2 n)
(define (iter a b c)
(if (= c 0)
b
(iter (+ a b) a (- c 1))))
(iter 1 0 n))
;; (fib 4)
;; (iter 1 0 4)
;; (iter 1 1 3)
;; (iter 2 1 2)
;; (iter 3 2 1)
;; (iter 5 3 0)
;; 3
;; 돈 바꾸는 방법 ??? - review 할 때 다시 얘기해 봅시다.
;; 받은 돈을 동전으로 바꾸는 방법
;; 10 센트
;; 1 센트 * 10
;; 5 센트 * 2
;; 5 센트 + 1 센트 * 5
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount (- kinds-of-coins 1))
(cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))
(define (first-denomination kinds)
(cond ((= kinds 1) 1)
((= kinds 2) 5)
((= kinds 3) 10)
((= kinds 4) 25)
((= kinds 5) 50)))
;; ex 1.11
(define (F1 n)
(if (< n 3)
n
(+ (F1 (- n 1)) (* (F1 (- n 2)) 2) (* (F1 (- n 3)) 3))))
;; a < a + 2*b + 3c
;; b < a
;; c < b
(define (F2 n)
(define (iter x y z count)
(if (< count 3)
x
(iter (+ x (* y 2) (* z 3)) x y (- count 1))))
(iter 2 1 0 n))
;; f(0) = 0
;; f(1) = 1
;; f(2) = 2
;; f(3) = f(2) + 2f(1) + 3f(0) = 4
;; ex 1.12
;; pascal's triangle,
;; p(r, c) = p(r-1, c-1) + p(r-1, c)
;; p(r, 1) = 1, p(r, r) = 1
(define (pt r c)
(cond ((or (= c 1) (= r c)) 1)
((or (< c 0) (< r 0) (> c r)) 0)
(else (+ (pt (- r 1) (- c 1))
(pt (- r 1) c)))))
;
