SICP Exercise 1.11

연습문제 1.11: n < 3 일 때 f(n) = n 이고, n >= 3 일 때

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

으로 정의한 함수 f가 있다.
f의 프로시저를 되도는 프로세스recursive process가 나오도록 짜라.
아울러, 반복 프로세스를 만들어 내는 프로시저도 만들어 보라.

(sol) 먼저, 다음과 같이 scheme으로 재귀함수를 작성할 수 있다.

(define (f-recur n)
  (cond ((= n 0) 0)
        ((< n 3)  (+ 1  (f-recur  (- n 1))))
        (else  (+
                (f-recur  (- n 1))
                (* 2  (f-recur  (- n 2)))
                (* 3  (f-recur  (- n 3)))))))
(define (f n)
  (f-recur n))

clojure로는 다음과 같이 1:1로 변환할 수 있다.

(defn f-recur  [n]
  (cond
    (= n 0) 0
    (< n 3)  (+ 1  (f-recur  (- n 1)))
    :else  (+
            (f-recur  (- n 1))
            (* 2  (f-recur  (- n 2)))
            (* 3  (f-recur  (- n 3))))))

(defn f  [n]
  (f-recur n))

다음은 반복 버전... 인데, 재귀 방식보다 더 성능이 안좋은 버전이다.

(define (f-iter result cnt max-cnt)
  (if (> cnt max-cnt)
    result
    (f-iter (cond
              ((= cnt 0) 0)
              ((< cnt 3) (+ 1 (f-iter 0 0 (- cnt 1))))
              (else (+
                      (f-iter 0 0 (- cnt 1))
                      (* 2 (f-iter 0 0 (- cnt 2)))
                      (* 3 (f-iter 0 0 (- cnt 3)))))) ; result
            (+ cnt 1)
            max-cnt)))

(define (f n)
  (f-iter 0 0 n))

다음은 clojure로 변환한 반복 버전. 역시 느리다.

(defn f-iter [result cnt max-cnt]
  (if (> cnt max-cnt)
    result
    (f-iter
      (cond
        (= cnt 0) 0
        (< cnt 3) (+ 1 (f-iter 0 0 (- cnt 1)))
        :else  (+
                (f-iter 0 0 (- cnt 1))
                (* 2 (f-iter 0 0 (- cnt 2)))
                (* 3 (f-iter 0 0 (- cnt 3))))) ; result
      (inc cnt)
      max-cnt)))

(defn f [n]
  (f-iter 0 0 n))

일단 이렇게 작성해놓고 나서 다른 사람들은 어떻게 작성했나 검색을 해봤더니,
n < 3인 경우에는 대부분 그냥 간단하게 처리해버렸다. 내 경우에는 재귀로
처리할 수 있는 부분은 가급적 재귀로 처리하도록 했는데,
문제에서의 함수의 정의를 고려하면 다른 사람들이 작성한 것 처럼
간단하게 처리하는 쪽이 f(n) = n이라는 정의와
1:1 연관이 되어 좀더 알아보기 쉬우면서 같은 동작을 하는 함수를 작성할 수 있을 것 같다.

iteration 버전의 경우, 함수가 총 3개의 항으로 되어 있는데 반복할 때마다 각 항 별로 계산 값을 넘겨주어야 함수의 코드가 간단해지는 것 같다.

다음은 수정한 함수들이다. 먼저 재귀 버전.

(defn f-recur [n]
  (if (< n 3)
    n
    (+ (f-recur (- n 1))
       (* 2 (f-recur (- n 2)))
        (* 3 (f-recur (- n 3))))))

(defn f [n]
  (f-recur n))

다음은 반복 버전. 훨씬 간단해졌다. 실행해보니 overflow 날 때까지는 지연 없이
거뜬히 연산을 해낸다.

(defn f-iter [s1 s2 s3 cnt]
  (if (< cnt 3)
    s1
    (f-iter (+ s1 (* 2 s2) (* 3 s3)) s1 s2 (dec cnt))))

(defn f [n]
  (if (< n 3)
    n
    (f-iter 2 1 0 n)))

PS. 바로 위 반복 버전의 경우에는 인수를 다섯 개로 하거나 분량이
더 늘어나거나 하는 수정 삽질을 거치고 나니 코드를 수정하기 전에 잠깐 본
stackoverflow의 솔루션
똑같아졌다.
몇초 잠깐 봤을 뿐인 내용이 만만치 않게 뇌리에 박혀서
무의식 중에 이 쪽으로 유도를 해내는 것일까.