読者です 読者をやめる 読者になる 読者になる

牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

SICPでやっぱり反復を理解できてなかったのでプロセスを視覚化してみた

SICP

SICPで反復が理解できてなかったので、有名なお二人のブログでの例を利用してプロセスを視覚化してみた

参考サイト

フィボナッチ数を計算する関数を、繰り返し(iteration)をつかって定義しなさい。再帰版は次の通り。

(define (fib n)
(cond
*1(fib (- n 2))))))

http://blog.livedoor.jp/dankogai/archives/50459008.html
iterationで書き換えたもの
(define (fib-iter n)
    (f 1 1 n))
(define (f a b count)
 (cond  ((= count 1) b)
        ((= count 2) a)
       (else (f (+ a b) a (- count 1)))))
で、これのプロセスを視覚化


理解できてるか確認

理解できてるか確認するため SICP 1.2.1 Linear Recursion and Iteration の Figure 1.4のコードを上の例題の様に カウントを1つづつ減らしていくものに書き換えてみた。

(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) ;720

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
  • (- count 1)で書き換えたもの
(define (factorial n)
 (fact-iter 1 n))
(define (fact-iter a count)
 (cond ((= count 1) a)
       (else (fact-iter (* a count)  (- count 1)))))
(factorial 6)
;;
CALL fact-iter 1 6
 CALL fact-iter 6 5
 CALL fact-iter 30 4
  CALL fact-iter 120 3
   CALL fact-iter 360 2
   RETN fact-iter 720
  RETN fact-iter 720
 RETN fact-iter 720
 RETN fact-iter 720
RETN fact-iter 720
720
;;

こんな感じでいいのかしらん?

*1:= n 1) 1) ((= n 2) 1) (else (+ (fib (- n 1