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

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

参考サイト

• 関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・ - Higepon’s blog
• 404 Blog Not Found:Recursion vs. Iteration

フィボナッチ数を計算する関数を、繰り返し(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