関数型言語の勉強にSICPを読もう - (7) 1章 - 反復をマスターしたいけど・・・
「SICPを読もう - (3) 1章 - 手続きによる抽象の構築(1-30ページ)」で反復が分からないと書いたのですが、trace を使えば視覚的に関数の呼び出しが理解できるのでこれを利用してみました。
題材としては一番単純な factorial を取り上げます。
まずは再帰版
(define (factorial n)
(if (= 0 n)
1
(* n (factorial (- n 1)))))trace を行うためのおまじないをしてから実行してみます。
gosh> (use slib)
gosh> (require 'trace)
gosh> (factorial 5)
gosh> CALL factorial 5
CALL factorial 4
CALL factorial 3
CALL factorial 2
CALL factorial 1
RETN factorial 1
RETN factorial 2
RETN factorial 6
RETN factorial 24
RETN factorial 120
120関数の呼び出し(CALL)と戻り値(RETN)が視覚的に展開されました。
関数が再帰的に呼ばれてその戻り値に1つずつそのときの引数がかけられていく様子が分かります。
ここの理解は問題ないです。
次に反復版です。
(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)))まだ理解できていないので1.2.1のコードそのままです。
factorial, iter両方をtraceするように指定します。
(trace factorial) (trace iter)
実行結果
gosh> CALL factorial 5
CALL iter 1 1 5
CALL iter 1 2 5
CALL iter 2 3 5
CALL iter 6 4 5
CALL iter 24 5 5
RETN iter 120
RETN iter 120
RETN iter 120
RETN iter 120
RETN iter 120
RETN factorial 120
120もちろん反復でも関数は再帰的に呼ばれています。
注目すべきはiterの第1第2引数のようです。
結果が第1引数、現在のカウンタが第2引数です。
これで以前よりも大分、視覚的なイメージが頭の中に広がるようになりました。
では実際に自分だけで書けるかをやってみよう。
1からnまでの数を足し合わせる場合。
(define (sum n)
(define (iter product counter max-count)
(if (> counter max-count)
product
(iter (+ product counter) (+ 1 counter) max-count)))
(iter 0 1 n))できました。最初(iter 1 1 n)と書いていて(sum 10) = 56 となってしまいびっくり。
少しだけ反復にも親しみがわいてきました。
では難易度を上げましょう。
問題1.11
一度挫折したこの問題に戻ってきました。
以前は解答を見ても、さっぱり分からなかったで答えを覚えていません、真っ白な頭で再チャレンジ。
まずは再帰版
(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
(trace f)
(f 4)とても直感的に書くことが出来ます。
次に問題の反復版。
やっぱり頭をどうひねっても答えが出てきません。
答えとtrace。
(define (iter a b c count)
(cond ((= count 0) c)
((= count 1) b)
(else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
(define (f-iter n)
(iter 2 1 0 n))
(trace f-iter)
(trace iter)
gosh> (f-iter 4)
gosh> CALL f-iter 4
CALL iter 2 1 0 4
CALL iter 4 2 1 3
CALL iter 11 4 2 2
CALL iter 25 11 4 1
RETN iter 11
RETN iter 11
RETN iter 11
RETN iter 11
RETN f-iter 11修行が足りないようです。
実は他の解答方法があってその答えはもっと簡単という可能性があるので帰ったら調べてみよう。
(今は外でこの記事を書いています。)
→調べてみたけど良いのがなかった。
問題はこういう解答が思いつくかどうかなのですが、、反復の練習問題がもっとたくさんあればパターンが見えてきそうです。
簡単なものから少しずつ難しいものへと。算数ドリルみたいなものですね。
どこかにそのような都合の良いものがないだろうか。
追記
404 Blog Not Found:Recursion vs. Iteration。
dan kogaiさんから、またまたトラックバックを頂いた。
まずはいろいろとご助言いただいたことに感謝いたします。
フィボナッチ数を計算する関数を、繰り返し(iteration)をつかって定義しなさい。再帰版は次の通り。
(define (fib n)
(cond
*1(fib (- n 2))))))SICPの問題より良問だと思う。
取り組んでみました。
(define (fib-iter a b count)
(cond ((= count 1) b)
((= count 2) a)
(else (fib-iter (+ a b) a (- count 1)))))
(define (fib n)
(fib-iter 1 1 n))このような感じでしょうか。（traceのためにiterはfact-iterとして束縛していません。)
良い問題だと思いました。
factorial と例の挫折した問題のちょうど中間地点にありそうな難易度です。
ただ正直に自分がこれをどうやって解いたかといわれると、例の難題との類似性から類推したという形で、まだ完全理解にはたどり着いていない気がします。
ちなみにSICPを読んだことがある方や、Schemeを勉強された方は、どんな些細な感想でもかまいませんのでコメントをいただけるとうれしいです。
例えば「こんな簡単なことで躓くのは駄目だ!」と言われれば自分が甘えていることが分かりますし、「自分も同じところではまりました」であれば多少気持ちが楽になったりと、先人の声を聞いてみたいなと思っています。
追記(その2)
id:nobsunからとても分かりやすいコメントを頂いたので追記。
下から積み上げるというのはかなり分かりやすいですね。
でもまだ頭の中に回路ができてないです。習うより慣れろ系。
気分としては，
再帰プロセスの場合，
「一歩手前までできた」として
そいつにちょこっと手を加えると欲しいものが手にはいる．反復プロセスの場合，
下から順に成果を積上げて，積み上げたものを次に渡して
ある条件がなりたった時点でおしまい．という感じでしょうか．この場合，「下からどう道筋を網羅して上へ登るか」と
「つぎに渡す積み上げた成果」を考えるといいかもしれません．fibonacciや問題1.11のようなシンプルなものの場合，下から順にならべるこ
とができます．このような列を1ステップ分ずらしてならべて，組にして眺める
となにか閃くかもしれませんね．
- A------B-----
fib(0)
fib(1) fib(0) ←
fib(2) fib(1) ←
fib(3) fib(2) ←
fib(4) fib(3) ←
...... fib(4)
- A----B---C---
f(0)
f(1) f(0)
f(2) f(1) f(0) ←
f(3) f(2) f(1) ←
f(4) f(3) f(2) ←
f(5) f(4) f(3) ←
.... f(5) f(4)
.... .... f(5)SICPの本文にもあるように，再帰プロセスのプログラムを反復プロセスに
変更するのは必ずしも自明ではありません．反復プロセスはCなどでは
ループに相当します．つまり，ループは再帰よりも難しいとも言えそうですね．たとえば，count-change を再帰プロセスではなく反復プロセスで書くのは
結構むずかしいと思いますよ．
計算機プログラムの構造と解釈
posted with amazlet on 06.04.15
Gerald Jay Sussman Julie Sussman Harold Abelson 和田 英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404
*1:= n 1) 1) ((= n 2) 1) (else (+ (fib (- n 1
