SICP 問題1.12

2017-08-15

1.2.2 木構造再帰 - 計算機プログラムの構造と解釈 第二版

次の数のパターンをPascal三角形(Pascal’s triangle)という.
三角形の辺上の数はすべて1, 三角形の内部の数はその上の二つの数の和である.
再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け.

※リンク先は問題にPascal三角形の画像が貼ってあるが省略。

どうしよう、どんな答えを出せば良いのか全然わからない。行数を渡したらその行数までのリストを返せばいいのかな?
例えば、4を渡したら、[ [1], [1,1], [1,2,1], [1,3,3,1] ]みたいな。ただまだリストを習ってないから違うんだろうな・・・

それとも、行数とインデックスを指定して、その値を返せばいいのかな?
それっぽいからそれで書こう。

(define (pascal l i)
  (cond ((< l i) "out of range")
        ((= i 1) 1)
        ((= l i) 1)
        (else
          (+ (pascal (- l 1) i)
             (pascal (- l 1) (- i 1))))))

再帰的プロセスなら割と簡単。