前回のつづき
手続きの書き方について深堀りして、合計を求める手続き sum と、積を求める手続き product について説明しました。
今回は？
再帰処理を使うと便利な場面、再帰する意義を考えてみましょう。その「先」に待っている「ある重要な気づき」についても触れていきます。
リスト処理の拡張
いままでは単純なリストについてだけ考えてきました。
'(1 2 3 4 5 6 7)
このように単に要素が並んでいるだけのリストを考えました。
が、実はリストの中にもリストを含むことができ、さらにリストを含むことも出来ます。
'(1 (2 3) 4 ((5 6 7) 8 9))
このようなリストの場合に要素をすべて合計する手続きを考えたいと思います。
元のプログラム
リストの要素を合計する sum を再掲しておきます。
(define (sum items)
(if (null? items)
0
(+ (car items)
(sum (cdr items)))))
まずはこのて手続きにリストを要素に含むリストを引数に渡して評価してみます。
gosh> (sum '(1 (2 3) 4 ((5 6 7) 8 9)))
*** ERROR: operation + is not defined between ((5 6 7) 8 9) and 0
Stack Trace:
(以下省略)
要素にリストが現れるためエラーとなり正しく処理できません。
＋ 手続きは、リスト「((5 6 7) 8 9)」と 0 を足し算できないと言っています。
gosh> (+ 3 '(1 2 3))
*** ERROR: operation + is not defined between 3 and (1 2 3)
Stack Trace:
(以下省略)
確かに同じエラーになります。
リストの中のリストを処理する方法
ポイントとしては、
・リスト内の要素がリストか否かを判断する必要があります。
・リストでないならば、今まで通り + 手続きで計算できます。
・リストならば、sum 手続きを呼び出して、リスト内の要素の合計を計算し、数値になってくれたら + 手続きで計算できます。
sum 手続きを修正してみましょう。リストか否かを判断するには list? 手続きを使います。
gosh> (list? (cons 1 (cons 2 '())))
#t
gosh> (list? (cons 1 2))
#f
gosh> (list? 2)
#f
ここで１つ注意して欲しいのは、(要素 . 要素) のコンスセルはリストではないので偽値を返します。
蛇足ですがコンスセルかを判断するには pair? 手続きを使います。前にリストは「(要素 . リスト) 形式のコンスセルの再帰的構造である」と説明しました。リストもコンスセルの仲間ですので pair? は真値を返します。
gosh> (pair? (cons 1 (cons 2 '())))
#t
gosh> (pair? (cons 1 2))
#t
gosh> (pair? 2)
#f
pair? と list? の真偽値の返し方の違いが理解できたでしょうか？
sum 手続きを修正する
では実際に修正してみます。
(define (sum items)
(if (null? items)
0
(+ (if (list? (car items))
(sum (car items))
(car items))
(sum (cdr items)))))
ちょっと処理の見た目が複雑になってきましたが、よく見ればそんなに難しくはありません。
今までは
(+ 最初の要素 (sum 最初以外の要素))
このようになっていましたが、最初の要素がリストか否かによって処理を変えています。
・最初の要素がリストのとき・・・ sum 手続きに最初の要素（リストです）を与えて合計を計算してもらいます。
・最初の要素がリストでないとき・・・いままで通り＋手続きに最初の要素（リストではありません）を渡します。
実行
gosh> (sum '(1 (2 3) 4 ((5 6 7) 8 9)))
45
リストの中にリストが現れても、すべての要素を合計することが出来ました。
再帰的な構造を処理する
リストの中にリストが現れる構造（＝入れ子）を再帰的構造といいます。マトリョーシカも再帰的構造です。再帰処理は再帰的な構造を処理するのに適しています。特に入れ子の数が決まっていないときに威力を発揮します。マトリョーシカの人形は開けていかないと人形がいくつ出てくるかわかりませんが、再帰処理では「人形がいくつ出てくるのか」は知る必要がありません。
他の再帰構造としては、
・二分木などのツリー構造
・ディレクトリ階層
・json形式ファイルの解析（パース）
などです。さらに、
・Lisp プログラムコードの解析（パース)
も可能です。
Lisp(Scheme)言語は、プログラムコード自体の構造がリストに基づいており、書式が一貫しているため、プログラムコードさえも再帰的なリスト構造として処理することが出来ます。
このことを踏まえてもう一度 Lisp(Scheme) で書かれた手続きをよく眺めてみてください。
(define (sum items)
(if (null? items)
0
(+ (if (list? (car items))
(sum (car items))
(car items))
(sum (cdr items)))))
プログラムコードの中に何か構造が見えてきませんか？
そうです。Lisp(Scheme) のコードは実はリストの形式になっているのです。
Lisp(Scheme) においてはプログラムコードもリストです。そして Lisp(Scheme) はリストという構造に基づくパラダイムを処理するプログラミング言語です。つまりプログラムコードをデータとして扱うことも簡単です。これが Lisp(Scheme)言語の柔軟さであり強みです。