【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))))
参考
- 作者: ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田英一
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/02
- メディア: 単行本
- 購入: 35人 クリック: 1,149回
- この商品を含むブログ (493件) を見る