SICP Exercise 1.12

연습문제 1.12: 다음은 파스칼의 세모꼴Pascal's triangle이다.
파스칼의 세모꼴 수를 만드는 프로시저를 짜되, 되도는 프로세스가 나오도록 하라.

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
       ...

지금까지 본 다른 예제는 n번째의 특정 값을 구하는 것이었는데, 이번 예제는
n번째 수열을 구해야 한다. scheme으로는 (찾으려면 찾을 수도 있지만) 리스트를 만들어 반환하는 함수는 아직 배우지 못했으므로, 바로 clojure로 작성하기로 했다.

어떻게 재귀 함수의 형태로 작성할 것인지 이리저리 궁리한 후, 다음과 같이
정리할 수 있었다.
위키피디아
내용을 참고하면, n번째 수열의 k번째 값 P_nk는 다음과 같이 정의할 수 있다.

    P_nk = P_(n-1)(k-1) + P_(n-1)k,
    P_n1 = P_nn = 1
      where n >= 1, 1 <= k <= n

이에 따라 먼저, 1부터 n 번째까지 각 항의 파스칼의 삼각형 수를 구해
리스트에 더하는 함수를 짜고, 1과 n 사이의 k 번째 항의 파스칼의 삼각형
수를 구하는 함수는 재귀 함수로 작성을 했다. 작성한 코드는 다음과 같다.

(defn pascal-triangle-recur [n k]
  (cond
    (= k n) 1
    (= k 1) 1
    :else (+
            (pascal-triangle-recur (dec n) (dec k))
            (pascal-triangle-recur (dec n) k))))

(defn pascal-triangle [n]
  (loop [result [] k n]
    (if (zero? k)
      result
      (recur (cons (pascal-triangle-recur n k) result) (dec k)))))

실행 결과는 다음과 같다.

=> (pascal-triangle 1)
(1)
=> (pascal-triangle 2)
(1 1)
=> (pascal-triangle 3)
(1 2 1)
=> (pascal-triangle 4)
(1 3 3 1)
=> (pascal-triangle 5)
(1 4 6 4 1)
=> (pascal-triangle 6)
(1 5 10 10 5 1)
=> (pascal-triangle 7)
(1 6 15 20 15 6 1)
=> (pascal-triangle 8)
(1 7 21 35 35 21 7 1)
=> (pascal-triangle 9)
(1 8 28 56 70 56 28 8 1)
=> (pascal-triangle 10)
(1 9 36 84 126 126 84 36 9 1)

PS. scheme으로는 어떻게 작성했는지 웹 검색으로 좀 컨닝을 해봤더니, 대부분 n번째 행 k번째의 파스칼의 삼각형 값을 구하거나 (즉, (pascal-triangle-recur n k)까지만 작성), 아니면 아예 1열부터 n열까지 구해서 삼각형 모양으로 출력하는 등 둘 중 하나를 따라서 했더군요.

그런데 후자의 경우에는 display나 몇 가지 배우지 않았던 함수를
알아야 작성할 수 있겠더군요. SICP의 진도를 따라가는 관점에서라면
부적절한 것이고, 이미 scheme에 익숙한 사람의 입장에서는 적절한
솔루션이라 할 수 있겠지요 :)

PPS. 그러고 보니 저도 consloop, recur 등을 사용했군요 :D