b^2 = b * b
b^4 = b^2 * b^2
b^8 = b^4 * b^4

로 부터 아래와 같은 규칙을 얻는다.

b^n = (b^(n/2))^2 if n is even
b^n = b * b^(n-1) if n is odd

이 것을 Big Theta (log n) growth를 갖는 procedure로 …

파스칼의 삼각형 문제이다. 문제 자체는 뭘 계산하라는 건지 좀 모호한데, 그냥 주어진 위치의 값을 결과로 내는 procedure를 만들었다. 위치는 (행, 열) 형식이다.

다른 사람들도 이런 식으로 생각한 것같다.

SICP Exercise 1.12

;; Pascal's triangle
;;
;; notation: (row, column)
;;
;;   1            (1, 1)
;;  1 1       (2, 1)  (2, 2)
;; 1 2 1 …

f(n) = n if n > 3
f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3

f(n)을 recursive process와 iterative process로 작성하는 문제이다.

내가 기억하기로는 (책에서), 조엘 스폴스키는 C와 같은 언어를 이용해서 recursive function을 만드는 사람을 채용하지 않는다고 했는데, stack overflow가 발생할 수 있기 때문이다. 일정한 space만 …

세 제곱근을 구하는 문제다. exercise 1.7의 improve procedure만 바꿔주면 된다.

SICP Exercise 1.8

(define (cuberoot-iter guess prev-guess x)
  (if (good-enough? guess prev-guess)
    guess
    (cuberoot-iter (improve guess x) guess x)))

(define (improve guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

(define (square x)
  (* x x))

(define (cube x)
  (* x …

원래 책에 소개된 코드는 square를 취한 결과를 x와 비교해서 적당한 값이라고 생각되면 값을 반환하게 되어있다. 1.7 문제는 이 코드를 개선하라는 것인데, 너무 작은 값이나 큰 값에 대해서 정확하게 동작하지 않기 때문이다.

floating-point 타입의 정밀도 한계때문에 아주 작은 값에 대해서 정확한 값을 얻지 못하고, 아주 큰 값에 대해서는 비효율적이거나 값을 …

SICP (Structure and Interpretation of Computer Programs)를 공부하는 사람이 꽤 많은 듯 하다. 관련 블로그도 많고, 다 볼 수 있을지 모르겠지만, How To Design Programs 살 때 덤으로 산건데 이걸 먼저 보고 있다..

아무튼 Exercise 1.6 은 cond 를 이용해 if 를 대체하는 procedure를 만들어 사용하면 어떻게 되느냐 …

cond 여러 개를 쭉 늘어 놓았다가, 결국 다음 코드처럼 간결하게..

(define (square x)
  (* x x))

(define (sum-square-2big a b c)
  (cond ((>= a b) (+ (square a) (square (max b c))))
        (else (+ (square b) (square (max a c))))
        ))

;; test
(if (= 0 (sum-square-2big 0 0 0)) #t #f)
(if (= 2 (sum-square-2big -1 -1 …