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

SICP

コツとしては「再帰式を積み上げる」感じで書くとうまくいくことが多いみたいです。問題は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

以下、解答。

階乗計算の解答

(define (iter product count)
	(if (= count 1)
		product
		(iter (* count product) (- count 1))))
(define (fact-iter n)
  (iter 1 n))

SICPの解答より一つ引数を減らして書いてみました。たぶん漸化式の問題としては一番簡単かと。

ハノイの塔問題の解答

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

初期値を0として、そこからコツコツ積み上げていく感じで書いてみました。

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

(define (fib-iter a b count)
  (if (= count 0)
	  b
	  (fib-iter (+ a b) a (- count 1))))
(define (fib-imp n)
  (fib-iter 1 0 n))

ここまで解いてきて、わかったことは

  • 自明な時の値（fib(0) = 0など)
  • 再帰の深さ（fib(n - 1), fib(n - 2))

を意識することが大事みたい。