前回のつづき
前回は my-map 手続きを使って Scheme の手続きの基本的な書き方を紹介しました。
今回はどんな時に再帰処理が便利なのかを説明していきますが、その前にもう少しだけ手続きの書き方について慣れておきましょう。
リストで与えられた数列を合計する
今回は数字の要素を持つリストを引数に受け取って、その要素をぜんぶ合計した値を返す手続き sum を考えます。
つまり
gosh> (sum '(1 2 3))
6
このような動作をする手続き sum を作ってみます。
考え方は my-map と同じです。
(define (sum items)
(if (null? items)
??
(+ (car items)
(sum (cdr items)))))
lst が空リストの場合は、まだよくわからないので ?? としてあります。
プログラムを書く場合に、「よくわからない部分」を「よくわからないまま」にして、他の部分を先に書くのはとても良いことです。わからない部分で立ち止まってしまうより、わからない部分は一旦置いて先に進んでみることのほうが大切です。立ち止まらずにとりあえず先に進んでみると、今まで見えなかった事に気づいたりします。
他方、空リストでない場合は簡単です。my-map 手続きの時と同じように、
・car を使って先頭の要素を取り出す
・cdr を使って sum 手続きに先頭の要素以外を引数にして評価する（再帰呼び出し)
・上記２つを + 手続きで足し算する
とすれば良いでしょう。
残った ?? の部分を考えてみます。
1 つ目の考え方としては、sum 手続きに空リストを渡したときにどんな値を返せば良いか考えてみるとすぐにわかります。
gosh> (sum '())
0
空リストが与えられた場合は、足し算する数は何もないので 0 を返せば良さそうです。
2 つ目の考え方としては、sum 手続きがどのような式に置き換えられるかを考える方法です。
sum 手続きの定義から次のような式に置き換えられることがわかるでしょうか？
(sum '(1 2 3)) ===> (+ 1 (sum '(2 3)))
(sum '(2 3)) ===> (+ 2 (sum '(3)))
(sum '(3)) ===> (+ 3 (sum '()))
リストを何度も cdr していくと、やがて空リスト「'()」が現れますから、sum 手続きの引数に空リストが渡されます。空リストの場合は 0 を返せば良さそうです。
(sum '()) ===> 0
どんな数に 0 を加えても、値は変化しません。
x + 0 = x
以上の式をまとめて書くと
(sum '(1 2 3)) ===> (+ 1 (+ 2 (+ 3 0)))
こうなることがわかります。
わからなかった ?? の部分は 0 にするのが正解です。
(define (sum items)
(if (null? items)
0
(+ (car items)
(sum (cdr items)))))
sum 手続きで合計を求めてみます。
gosh> (sum '(1 2 3 4 5))
15
このように正しく合計を求めることができました。
リストで与えられた数列の積を求める
では掛け算する場合はどうすれば良いでしょうか？
(define (product items)
(if (null? items)
??
(* (car items)
(product (cdr items)))))
＋ 手続きを ＊ 手続きに変えれば簡単です！
と言いたいところですが、ここで１つ困った問題が発生します。
product 手続きは最終的に次のように式に変換されるので、
(product '(1 2 3)) ===> (* 1 (* 2 (* 3 ??)))
リストの最後に現れる空リストは 1 にすればよさそうです。?? を 1 に修正しました
どんな数に 1 を掛けても値は変化しません。
x \times 1 = x
(define (product items)
(if (null? items)
1
(* (car items)
(product (cdr items)))))
実行してみます。
gosh> (product '(1 2 3 4 5))
120
結果はあっています。ですが、product 手続きに空リストを与えたらどうなるでしょうか。
gosh> (product '())
1
返却値が 1 になってしまいました。空リストの場合は、掛け算する数が無いわけなので 0 を返したほうが良いでしょう。1 を返してしまうのはおかしいです。
これを解決するにはどうすればよいでしょうか？
product 手続きに単に空リストが与えられた場合は 0 にしなければいけませんが、普通に要素があるリストが与えられた場合については、リストの最後に現れる空リストの値は 0 ではなく 1 にしたいわけです。空リストの値を 0 にしたい場合と、1 にしたい場合があって、この違いが問題です。手続きを修正してこれに対応しなければなりません。
次のように product 手続きを書き直します。
(define (product items)
(define (iter l)
(if (null? l)
1
(* (car l)
(iter (cdr l)))))
(if (null? items)
0
(iter items)))
いままでの product 手続きを、iter 手続き（名前は product 以外なら何でもいいです) にそのまま移して、prodect 手続きは、items のチェックを行い、空リストなら 0 を返し、空リストでないなら iter 手続きに items を渡して評価します。
また、この iter 手続きを「内部手続き」と言います。iter 手続きは product 手続き内でのみ使用できる手続きで、他の手続きから隠されます。具体的に言えば sum 手続きからは見えませんし、呼び出すこともできません。つまり、
・他の手続きと名前が衝突しないかな？
・手続きを修正すると他の手続きに影響がでないかな？バグになったりしないかな？
などの心配をする必要が無くなります。
最後に、修正した product 手続きを実行してみます。
gosh> (product '(1 2 3 4 5))
120
gosh> (product '())
0
これならば問題ないでしょう。
まとめ
今回は、Scheme の手続きの書き方についてさらに深堀りしました。次回は、いよいよ再帰処理がどんな場面で役に立つのかについて説明したいと思います。
つづく！（たぶん）