【SICP】1.2.1~1.2.2

1.2.1 線形再帰と反復

• 線形再帰プロセス：プロセスを実行するごとに、実行する演算が線形に成長する再帰プロセスのこと

• 線形反復的プロセス：プロセスに必要なステップ数が線形に成長していく反復的プロセスのこと

6!の線形再帰プロセスの例

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)

6!の線形反復的プロセスの例

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

(factorial 6)

1.2.2木構造再帰

フィボナッチ数列

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2))))))

パスカルの三角形

   1
  1 1
 1 2 1
1 3 3 1

n行目k個目の数を(n, k)とすると、 (n, k) = (n-1, k-1) + (n-1, k) さらに、 k=1, k=nのとき、(n, k)=1

(define (pascal n k)
        (if (or (= k 1) (= k n))
            1
            (+ (pascal (- n 1) (- k 1))
               (pascal (- n 1) k))))

参考

計算機プログラムの構造と解釈