[SICP] 問題 1.12 : Pascal三角形

次の数のパターンをPascal三角形(Pascal's triangle)という.

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

三角形の辺上の数はすべて1, 三角形の内部の数はその上の二つの数の和である. 再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け.

Pascal三角形を計算する手続きを定義します. 結果の確認を容易にするための手続きも定義します.

(define (pascal x y)
  (cond ((= x 0) 1)
        ((= y 0) 1)
        ((= x y) 1)
        (else (+ (pascal (- x 1) (- y 1))
                 (pascal (- x 1) y)))))

;; 1からnまでの整数のリストを求める.
(define (int-list n)
  (define (loop result counter)
    (if (< counter 0)
        result
        (loop (cons counter result) (- counter 1))))
  (loop '() n))

;; 9行分のPascal三角形を求める.
(map (lambda (x)
       (map (lambda (y) (pascal x y)) (int-list x)))
     (int-list 8))

実行した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
((1)
 (1 1)
 (1 2 1)
 (1 3 3 1)
 (1 4 6 4 1)
 (1 5 10 10 5 1)
 (1 6 15 20 15 6 1)
 (1 7 21 35 35 21 7 1)
 (1 8 28 56 70 56 28 8 1))
> 

Pascal三角形を計算できていることを確認できます.