今回は、たくさん再帰呼び出しをしても大丈夫なように
合計を求めるプログラムを改良したいと思います。
1 から n までの合計を計算する手続きです。
(define (my-sum n)
(if (<= n 0)
0
(+ n (my-sum (- n 1)))))このプログラムは n をとても大きな値にすると、正しく処理できないことがあります。
例えば n = 10000000000 (100億) にするとプログラムは異常終了してしまいました。
このプログラムを直す前に、「まず何が問題なのか」を、
コンピュータの複雑な内部事情を抜きにして説明したいと思います。
まず以下のような簡単なプログラムを考えます。
(define (func) (+ (func-1) (func-2) (func-3))) (define (func-1) 10) (define (func-2) 100) (define (func-3) 1000)
func 手続きは、func-1, func-2, func-3 手続きを順番に呼び出します。
ちなみに、Scheme では define で定義する関数を「手続き」、
手続きを実行することを「評価する」と言います。
具体例を示すと「func 関数を実行する」は、「func 手続きを評価する」と言います。
さて、func 手続きを評価してみると
gosh> (func) 1110
1110 という値を返します。とくに難しくは無いよね。
ここで、func 手続きの中身に注目してほしいんだけども、
まず足し算をするには、func-1, func-2, func-3 を呼びだして、
返却値が決らないと計算できないのはいいかな?
func-1 を評価し終ったら、次に何をするかというと、
答えは
func-2 を評価する
だね。そんなの当たり前じゃん! て思うかもしれないけど、よく考えてみてね。
あまりにも当たり前の事って、見逃しやすいから注意だよ。
func-1 を評価し終ったらどこに戻れば良いか、覚えておく必要があるよね?
手続きを呼び出す(=評価する)ときは、
・戻る場所を覚える ・覚えた場所に処理を戻す
という仕組みが無いと、func-1 を評価し終ったらプログラム全体が終了してしまう。
そういう動作をしてほしくて func 手続きを 書いたわけじゃないので、
これでは困ったことになってしまうよね?
func-1 手続きの評価が終ったら、一旦 func に戻ってきて、
func-1 の次に書いてある func-2 を評価してほしいわけだ。
func-2 も同様に、func-2 手続きの評価が終ったら、一旦 func に戻ってきて、
func-2 の次に書いてある func-3 を評価してほしいわけだ。
func-3 も同様なんだけど、func-3 手続きの評価が終ったら、一旦 func に戻ってくるけど、
次に評価する手続きは何もないので、戻ってくるだけだね。
ここで、func-1, func-2, func-3 をそれぞれを評価したので、それぞれの戻り値が決まるわけなので、
足し算ができるようになります。
最後に func は足し算の結果を返して終了します。
ここまでいいかな?
手続きを呼び出すときは、手続きの評価が終ったらどこに戻れば良いのか
覚える必要がある。これは再帰呼び出しをするときも変りません。
今の例では手続き呼び出しが入れ子(マトリョーシカのおもちゃみたいな構造)になってなかったけど、
手続きの呼び出しがこんな風に入れ子になっていたらどうだろう。
(define (func) (func-1)) (define (func-1) (+ 10 (func2))) (define (func-2) (+ 100 (func-3))) (define (func-3) (+ 1000 (func-4))) ...中略... (define (func-100) (+ 10000000000 (func-101)))
元の場所に戻ったら、覚えていた戻る場所は忘れても良いけど、
入れ子になっている場合は、入れ子が深くなるほど、戻る場所をたくさん覚えなければいけなくなる。
で、再帰呼び出しも同様で、同じ手続きを何度も何度も呼び出し続ける事になるけど、
戻る場所は毎回覚えなければいけないので、たくさん覚えないといけなくなる。
すると、コンピュータはそのうち「もう覚えられない! 無理!!!」って
なってしまい、そうなるとプログラムは異常終了してしまいます。
これが問題の正体です。まとめると、
・手続きを呼び出すときは、どこに戻るかを覚えなければいけません。 ・戻ったら覚えたものは忘れます。が... ・再帰呼び出しは何度も手続きを呼び出し続けるので、たくさん覚え続ける必要があります。 ・覚えることが出来る量は限界があります。無限に覚えることはできません。 ・もうこれ以上覚えられない!という状態になってしまうとプログラムは異常終了してしまいます。
という事です。
さて、ではこのプログラム、
(define (my-sum n)
(if (<= n 0)
0
(+ n (my-sum (- n 1)))))これをどう直せば良いのか、まず解答を示して説明していきます。
言葉で長々説明するまえにコードを見たほうがわかりやすいからね。
(define (my-sum n)
(define (iter i s)
(if (> i n)
s
(iter (+ i 1) (+ s i))))
(iter 1 0))まず my-sum 手続きの中で iter 手続きを define しています。
iter は my-sum だけが使える自分だけの手続きです。
このように define の中で define すると何が嬉しいかと言うと、
・変更したら他の処理に影響が出ちゃうかも? 手を入れたいんだけど大丈夫かな? ・手続きの名前は iter にしたいんだけど、名前が衝突しないかな?
iter 手続きはよそからは見えないから、そんな事は考えなくても良くなる。
もうちょっと言うと、合計値の初期値 0 を他の処理から隠すことが出来るという利点もあります。
例えば、
gosh> (my-sum 100 0)
こんな風にしてしまうと合計値の初期値を書かないといけなくなるので嫌な感じだよね。
合計値の初期値はいつも 0 でなければ困るのに、引数にしてしまうと 0 以外の値を指定されてしまうかもしれないし、
毎回 0 を引数に指定してもらうのもどうなんだろう...ってなるよね?
合計値の初期値をチェックして、
エラー : 合計値の初期値は 0 を指定してください。
なんてエラーメッセージを出すのもなんか変だよね?w
そういう理由から合計値の初期値は「隠したい」わけだね。
gosh> (my-sum 100)
こういう風に呼び出せばいいよね。これのほうがスマートでしょう?
内部で、合計値の初期値はいつも 0 を指定すればいいわけ。
my-sum 手続きは、iter 手続きを呼び出しているだけです。
引数 i には 1 を、引数 s には 0 を指定して呼び出すだけ。
my-sum 手続きは iter 手続きの評価が終ったら、
iter 手続きの戻り値をそのまま返します。
次に iter 手続きの中を見ていくよ
引数 i は 1 から n まで変化します。
s は i までの合計値を持ちます。なので s の初期値は必ず 0 だね。
i が n まで増えると、s は 1 から n までの合計値になっているはず。
中身の処理を詳しく見ていくと、i と n を if 文で比較していて、
i が n より大きくなったら s を返して処理を終了します。
i が n 以下のときは、iter 手続きを呼び出します。
自分自身を呼び出す「再帰呼び出し」です。
このとき、iter 手続きには
i に 1 を足したものを渡します。これは次の準備をしているわけだね。
s は s と i を足したものを渡すことで、s の価を更新します。
i は 1 から n まで変化するので、s には 1 から n までの合計が求まるよね?
さて、これだけでは問題は解決していませんw
iter 手続きをよく見てください。
手続きの最後は、iter 手続きを呼び出す書き方になっているのが、わかるかな?
これをちょっと難しい言葉なんだけれども「末尾再帰」って言います。
実は Scheme 言語では手続きを「末尾再帰」で書くと、
なんと!
再帰呼び出しする度に戻る場所を覚える必要が無くなるのです!!*1
これは Scheme 言語の仕様として決められていて、これをちゃんと満足していないと
Scheme 言語の仲間に入れてもらえません!
末尾再帰で再帰呼び出しする手続きを書いておけば、
プログラムが「戻り場所がもう覚えられないよ! 無理!!!」となって
異常終了することはありません。
Scheme 言語はそのようにならない事を言語仕様として保証しています。*2
末尾再帰の仕方なんだけども、難しく考える事は何も無くて、
ポイントを言うと、
再帰手続きの引数に結果を持つようにする
これだけ気をつければ、自然と末尾再帰の書き方になってしまいます。
今回の例で言うと、
引数 s (合計値)
のことだね。簡単!
今回のまとめ
・再帰呼び出しする手続きは「末尾再帰」を使おう。 ・末尾再帰するには、再帰手続きの引数に結果を持つようにすること
これだけ覚えてね。
つづく!
