3일차 - 1.2 - 요약

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)))))
;