SICP解答メモ＆解説 (問題1.14〜問題1.28）

ここの問題は、「手続きによる抽象の構築」というより、「アルゴリズムの設計と解析」と言う感じなので、1.3の「高階手続きによる抽象」まで飛ばすことにします。

反復プロセス練習！！練習！！練習！！

コツとしては「再帰式を積み上げる」感じで書くとうまくいくことが多いみたいです。問題はSICPとか数学の有名な漸化式の問題から拝借しました。

階乗計算

階乗を計算する手続きを、反復プロセスで定義せよ。再帰プロセス版は以下の通り。

(define (fact-recur n)
  (if (= n 1)
	  1
	  (* n (fact-recur (- n 1)))))

ハノイの塔

ハノイの塔問題を最小手数で解く漸化式を反復プロセスで定義せよ。再帰プロセスは以下の通り。

(define (hanoi n)
  (if (= n 0)
	  0
	  (+ (* 2 (hanoi (- n 1))) 1)))

フィボナッチ数を求める問題

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

(define (fib n)
  (cond
   ((= n 1) 1)
   ((= n 2) 1)
   (else (+ (fib (- n 1))(fib (- n 2))))))

404 Blog Not Found:Recursion vs. Iteration

参考

404 Blog Not Found:Recursion vs. Iteration
関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・ - higepon blog
SICP（1.2 手続きとその生成するプロセス） - selflearn @ ウィキ - アットウィキ
SICPでやっぱり反復を理解できてなかったのでプロセスを視覚化してみた - 牌語備忘録 -pygo
http://uprush.net/book/4/269/3.html
http://torus.jp/memo/x200605/tailcall.rd.html

以下、解答。