SICPで反復が理解できてなかったので、有名なお二人のブログでの例を利用してプロセスを視覚化してみた
参考サイト
- 関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・ - Higepon’s blog
- 404 Blog Not Found:Recursion vs. Iteration
フィボナッチ数を計算する関数を、繰り返し(iteration)をつかって定義しなさい。再帰版は次の通り。
(define (fib n)
http://blog.livedoor.jp/dankogai/archives/50459008.html
(cond
*1(fib (- n 2))))))
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)
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
(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
- (- 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