SICPを読む(11) 1.2.2 再帰脳を作ろう。

Scheme

段々再帰な人たちの言っていることが判りはじめた気がする。

再帰脳を作ろう。

僕等が1から10まで足すとしたら、

「あ、1から10までねハイハイ。」

1 + 2 + 3 + 4 + ... + 10 = 55

1から計算する。

再帰な人たちは、

「10の前は9だ。1まで足せば良い。」

10 + 9 + 8 + 7 + ..... + 1 = 55

後ろから数える。

1まで足せば良いと考えると、終端を考えなくて良い。

面倒そうだが、慣れると断然楽かもしれない。

ってことで、フィボナッチ数列

お馴染みのフィボナッチ数列。

0 1 1 2 3 5 8 13 21

頭から数えると、

0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
...

これが僕等的考え。反復。メリットは計算回数が少ない。

再帰な人は、

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)

1個前と2個前の状態を見る。終端を考える。メリットは、数式をそのまま当てはめるだけ。

それを踏まえて、再帰と反復を書く。

; 再帰
(define (fib n)
 (cond ((= n 0) 0)
       ((= n 1) 1)
       (else (+ (fib (- n 1))
                (fib (- n 2))))))
; 反復
(define (fib n)
 (define (iter a b count)
  (if (= n count)
      a
      (iter b (+ a b) (+ count 1))))
 (iter 0 1 0))
(fib 8)

反復はやたら複雑になった。

サンプルは0まで計算していたけど、反復の練習の為、nまでに書き直してみた。

段々、Schemerの言う、「再帰で書いた方が楽じゃん」的な考え方がわかってきた気がする。

両替問題

1,5,10,25,50セントのコインがある。1ドルの両替に何パターンあるのか。

1ドルの両替をちょっと考える。

50 50
50 25 25
50 25 10 10 5
...
50 1 1 1 1 1 ...
25 25 25 25
25 25 25 10 10 5
...
1 1 1 1 1 1 ...

あぁぁぁ・・・となってしまったらアウト。再帰脳が出来ていない証拠。

両替問題では、再帰のポイントが違う。

  • コインの種類を減らす(5種類あるものを4種類に)
  • 金額を減らす(50セント引く)
  • 金額が0になったらパターンを1個追加して、再帰終了。

理解するのに随分時間がかかった。とにかくシンプルなパターンを見つけ出すことが重要。

(define (count-change amount)
 (cc amount 5))
; return 合計パターン
(define (cc amount kinds-of-coins)
 (cond ((= amount 0) 1) ; 丁度両替出来た
       ((< amount 0) 0) ; 出来なかった。
       ((= kinds-of-coins 0) 0) ; 最後までテストが完了した
       (else (+ (cc amount (- kinds-of-coins 1)) ; コインを減らす
                (cc (- amount (first-denomination kinds-of-coins)) ; 金額を減らしてテストする。
                 kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

実は、同じパターンを何度も繰り返している。この本を読んでいくうちに、改善の方向に向かうんじゃないかなぁと思う。

追記

実はまだリスト脳が無かったりする。