SICP 연습문제 1.11 친절한 풀이

문제

$n<3$일 때 $f(n)=n$이고, $n≥3$일 때 $f(n)=f(n-1)+2f(n-2)+3f(n-3)$으로 정의한 함수 $f$가 있다. f의 프로시저를 되도는 프로세스가 나오도록 짜라. 아울러 반복 프로세스를 만들어내는 프로시저도 만들어 보라.

문제로 부터 얻은 것

반복하는 프로세스를 구성할 때에는 (프로세스가 반복하는 로직, 베이스 케이스에서의 동작 확인) 이 두가지를 신경써서 구성해야 합니다. 또한 iter 내부의 인수를 조작하는 것으로 프로시저를 더 아름답게 만들 수 있습니다.

문제풀이

우선 두 프로시저에서 모두 사용할 계산 프로시저 calc를 만들었습니다.

$x+2y+3z$

(define (calc x y z)
  (+ x (* 2 y) (* 3 z)))

첫번째 문제인 되도는 프로세스는 문제를 읽는 것만으로도 쉽게 구상할 수 있을 것입니다.

(define (f n)
  (if (< n 3)
      n
      (calc (f (- n 1)) (f (- n 2)) (f (- n 3)))))

하지만 두번째 문제인 반복 프로세스를 만들 때에는 조금 고민을 할 필요가 있습니다.
프로시저를 구상하면서 떠올린 저의 아이디어는 이렇습니다.

• $f(n-1)$, $f(n-2)$, $f(n-3)$을 인자로 계속 물려주는 프로시저를 구상하면 되겠다.
• 또 index를 인자로 주어 index가 0부터 n까지 자라나도록 하면, $f(0)$부터 순서대로 계산하겠구나.
• 그러다가 index = n 인 시점에서 계산한 결과를 반환하면 되겠구나.

그리곤 프로시저를 짜보았습니다. 미리 말씀드리지만 아래의 프로시저는 틀린 프로시저입니다. 왜 틀렸는지를 한번 생각해 보시길 바랍니다.

(define (f-iter n i temp1 temp2 temp3)
  (cond ((< n 3) n)
        ((= n i) (calc temp1 temp2 temp3))
        (else (f-iter n (+ i 1) (calc temp1 temp2 temp3) temp1 temp2))))

위 프로시저가 틀린 이유는 $n≥3$ 일때 temp1 temp2 temp3의 값이 0부터 시작한다는 것입니다. 원래대로라면 $n≥3$이면서 $i<3$인 구간에도 temp에 0이 아닌 i를 넘겨줘야 합니다. 이해가 안가신다면 아래의 수정된 코드를 잘 생각해 보시기 바랍니다.

(define (f n)
  (define (f-iter n i temp1 temp2 temp3)
    (cond ((< n 3) n)
          ((= n i) (calc temp1 temp2 temp3))
          (else (if (< i 3)
                    (f-iter n (+ i 1) i temp1 temp2)
                    (f-iter n (+ i 1) (calc temp1 temp2 temp3) temp1 temp2)))))
  (f-iter n 0 0 0 0))

위의 코드대로 실행해 보았더니 두 함수 모두 같은 결과를 도출하며 잘 작동하는 것을 확인할 수 있습니다.

그런데 문득 한번 더 코드를 고칠 수 있겠다는 생각이 들었습니다. $n≥3$인 상황에서 굳이 if문을 한번 더 써서 $i<3$을 검사하는 것 보다는, 처음부터 i는 $n≥3$인 상황에서만 쓴다고 생각하고 i를 3으로 놓고 f-iter의 다른 인자들을 수정하면 더 효율적으로 프로시저를 짤 수 있을 것 같았습니다.

(define (f n)
  (define (f-iter n i temp1 temp2 temp3)
    (cond ((< n 3) n)
          ((= n i) (calc temp1 temp2 temp3))
          (else (f-iter n (+ i 1) (calc temp1 temp2 temp3) temp1 temp2))))
  (f-iter n 3 2 1 0))

이번 문제로 얻은 교훈은 반복하는 프로세스를 구성할 때, 베이스 케이스에서의 동작에 좀 더 신경을 써야한다는 것입니다. 다음부터 반복하는 프로세스를 구성할 때에는 (프로세스가 반복하는 로직, 베이스 케이스에서의 동작 확인) 이 두가지를 신경써서 구성하도록 하겠습니다. 또한 내부의 iter프로시저의 인수를 조작하는 것으로 좀 더 아름다운 코딩을 할 수 있다는 것도 마음에 담아가겠습니다.

읽어주셔서 감사합니다.