Books by Example/SICP2007.11.10 09:50

이 문제는 되도는 프로시저를 사용해 되도는 프로세스와 반복 프로세스를 구현해 보는 문제입니다. 되도는 프로세스는 흔히 "재귀적 프로세스"라고 부르는 것이고, 반복 프로세스는 "iterative process"입니다. (프로시저와 프로세스는 다른 개념인데, 프로시저는 코드라고 생각하면 되고, 프로세스는 그 코드에 의해 만들어지는 실행 궤적이라고 생각하면 됩니다. 따라서 프로시저는 재귀적으로 구현되더라도, 그 실행 궤적 자체는 반복적이 되는 일이 Scheme같은 언어에서는 발생할 수 있습니다. C에서라면 좀 곤란하지만요.)

C와 같은 언어에서 전자는 흔히 '함수의 재귀적 호출'에 의해 구현되고 반복 프로세스는 for나 while과 같은 별도의 문법에 의해 구현됩니다만, lisp는 for와 같은 문법을 지원하지 않기 때문에 재귀적 프로세스나 반복 프로세스나 전부 재귀적인 프로시저에 의해 구현해야 합니다. 처음에는 이것이 이해가 잘 되지 않을 수 있습니다. 책에서는 재귀적 프로세스와 반복 프로세스의 차이를 다음과 같이 언급하고 있습니다.

반복하는 프로세스에서는 프로그램 변수가 프로세스 단계마다 어떤 상태에 있는지 정확하게 나타내기 때문에, 계산을 잠시 멈추더라도 각각의 변수의 값만 알면 실행기가 곧바로 계산을 이어갈 수 있다. 하지만 되도는 프로세스는 그렇지 않다. 프로세스 안에 상태변수도 없을 뿐더러, 뒤로 미뤄 둔 연산의 끈을 이어가면서 '어디까지 계산했는지' 알아내려면, 실행기 속에 숨은 정보가 더 있어야 한다. 끈이 길 수록 그런 정보는 더 많아진다.



1.11번 문제는 함수 f(n) = (n-1) + 2f(n-2) + 3f(n-3) (n < 3일때는 f(n) = n)을 재귀적 프로세스와 반복 프로세스 두 가지 다른 버전으로 구현해 보는 것입니다. 통상 재귀적 프로세스는 하향적으로 문제 풀이가 전개되는 반면, 반복 프로세스는 상향적으로 문제 풀이가 전개됩니다. 전자는 좀 연역적인 성격이 있고, 후자는 좀 귀납적인 성격이 있다, 이렇게도 볼 수 있겠습니다. 그 점을 염두에 두면 문제풀이가 쉬워지는 것 같습니다.

답은 아래에 있습니다.

(define (func n)
  (if (< n 3) n
      (+ (- n 1) (* 2 (func (- n 2))) (* 3 (func (- n 3))))))

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count n) (+ (- count 1) (* 2 b) (* 3 c))
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))

(func 8)

(func-iter 8)

이렇게 할 수도 있습니다.

(define (func-iter n)
  (define (func-iter-part a b c count)
    (if (= count (+ n 1)) a
        (func-iter-part (+ (- count 1) (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3) n
      (func-iter-part 2 1 0 3)))


거의 같은데 루프를 한 번 더 도는 것만 다르죠. ㅋㅋ 그런데 이 문제에 대한 인터넷 해답을 보니, 인터넷에서의 해답이 제 답과 조금 다르군요. 왜 그런가 잠시 생각해봤는데... 책에 오타가 있습니다 ㅎㅎ

To English Readers: There's typo in the exercise 1.11 of korean version of SICP. So. ignore the above answer - the answer for the 'wrong' question. Correct answer is given below (only the iterative version of the answer. I didn't give the recursive version of the answer, because it's too easy).

오타가 있어도 문제가 안풀리는 건 아닙니다만, 아무튼 답은 조금 달라집니다. 원서에 실린 문제 공식은 f(n) = (n-1) + 2f(n-2) + 3f(n-3)이 아니라 f(n) = f(n-1) + 2f(n-2) + 3f(n-3) 입니다. (한글판에는 f가 빠졌습니다.) f가 있을 경우의 해답은 다음과 같습니다. 역시 반복 프로세스의 경우만 싣습니다. 재귀적 프로세스의 경우에는 답이 뻔해서...

(define (f-b n)
  (define (f-b-iter a b c count n)
    (if (= count n) a
        (f-b-iter (+ a b c) (* 2 a) (* 3 (/ b 2)) (+ 1 count) n)))
  (f-b-iter 2 2 0 2 n))




사용자 삽입 이미지


이제 조금 익숙해지긴 했습니다만, 그래도 어렵긴 어렵군요. ㅋㅋ

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 어쩐지 이상하다 했습니다.OTL....
    저는 n 파라메터를 따로 만들었는데, 앞에서 배운 블록구조 안에 숨겨서 변수를 그대로 쓸 수 있다는 것을 깜박했습니다.
    좋은 정보 고맙습니다.^^

    2008.01.04 10:54 신고 [ ADDR : EDIT/ DEL : REPLY ]