たまたま見つけた記事、関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・が面白そうなのでやってみた。
取り敢えず factorial から。
再帰プロセス
(define (factorial n)
(if (= 0 n)
1
(* n (factorial (- n 1)))))
反復プロセス
(define (f n)
(define (f-iter a n)
(if (= n 0) a
(fa-iter (* a n) (- n 1))))
(fa-iter 1 n))
または
(define (factorial n)
(iter 1 1 n))
(define (iter product counter max-count)
(if (> counter max-count)
product
(iter (* counter product)
(+ counter 1)
max-count)))
反復の場合、カウントを上げていく場合と下げていく場合の2種類で書くことができた。個人的には上がっていくほうが感覚的には分かりやすいが、スッキリ書くなら下がっていく方なのでちょっともどかしい。
次に1からnまでの数を足し合わせる場合。
再帰プロセス
(define (sum n)
(cond ((= n 0) 0)
(else (+ n (sum-r (- n 1))))))
反復プロセス
(define (sum n)
(define (sum-iter a n)
(if (= n 0) a
(sum-iter (+ a n) (- n 1))))
(sum-iter 0 n))
反復プロセス(カウントUPver.)
(define (sum-2 n)
(define (sum-2-iter a count max)
(if (> count max) a
(sum-2-iter (+ a count) (+ count 1) max)))
(sum-2-iter 0 1 n))
ここまではそんなに難しくない。次の問題はたしかにちょっと難しかった。
(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
取り敢えずこれを反復プロセスで書けばいいようだ。コツとしては(- n x)の分を引数で渡してあげる事で関数を膨張させずにすむのだがそこまで気づくのに手間取ってしまった。
反復プロセス
(define (f n)
(f-iter 2 1 0 n))
(define (f-iter a b c n)
(cond ((= n 0) c)
((= n 1) b)
((= n 2) a)
(else (f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1)))))
これをカウントUPにしていくのは骨が折れそうだったので断念。
次に、順番が逆になってしまったが小飼さんからの問題。fibonacciを反復で書けばいいみたいだ。
再帰プロセス
(define (fib n)
(cond
((= n 1) 1)
((= n 2) 1)
(else (+ (fib (- n 1))
(fib (- n 2))
))))
反復プロセス
(define (fib-i n)
(fib-iter 1 1 n))
(define (fib-iter a b n)
(cond ((= n 1) b)
((= n 2) a)
(else (fib-iter (+ a b) a (- n 1)))))
反復プロセス(カウントUPver.)
(define (fib-i-2 n)
(fib-iter-2 1 1 0 n))
(define (fib-iter-2 a b count max)
(if (> count max) a
(cond ((or (= count 1) (= count 2))
(fib-iter-2 1 1 (+ count 1) max))
(else
(fib-iter-2 (+ a b) a (+ count 1) max)))))
とまあ、問題は全部でこんな感じ。普段使わない頭のを使ったような気がする。
最後にRubyプログラマらしくRubyで解いて終わりにしよう。(全部は面倒くさいのでfibonacciだけ :p)
# -*- coding: utf-8 -*-
#再帰プロセス
def fib n
n <= 2 ? 1 : fib(n - 1) + fib(n - 2)
end
#反復プロセス1
def fib_i n
fib_iter(1, 1, n)
end
def fib_iter(a, b, n)
case n
when 1 then b
when 2 then a
else
fib_iter (a + b), a, (n - 1)
end
end
#反復プロセス2
def fib_i_2 n
fib_iter_2(1, 1, 0, n)
end
def fib_iter_2 a, b, count, max
return a if count > max
case count
when 1, 2
fib_iter_2(1, 1, (count += 1), max)
else
fib_iter_2((a + b), a, (count += 1), max)
end
end
puts "再帰プロセス:", fib(10)
puts "反復プロセス1:", fib_i(10)
puts "反復プロセス2:", fib_i_2(10)