recursion

5. 再帰

Enjoy Gauche の目次

5. 再帰

前章まで覚えれば、プログラミング以前のところは大体おわり。この章からは簡単なプログラミングをしていきましょう。といっても、いきなり本格的なプログラミングというのは、つらいので(誰が？もちろん私)、 toy プログラムを作るところから始めましょう。

5.1. 階乗の計算

階乗(！)の計算を考えてみましょう。まず、

n の階乗とは 1以上n以下の整数を掛け合せたもの。

この計算を考えるとき、自明な場合を先ず考えましょう。

n = 1 のとき、n の階乗は、1

これはいいですよね。じゃ自明じゃないときは、

(n - 1) の階乗がもう計算できていると仮定しましょう。そうすると n の階乗は、(n - 1) の階乗に n を掛けたものに等しいはずですよね。

「nの階乗」と書くかわりに fact(n) と書くことにして、まとめて、数学っぽく

fact(n) = 1, if n = 1
fact(n) = n * fact(n-1)

という定義ができますね。これは、高校の数学の教科書にもでてくる漸化式というものを使った定義ですね。このように、定義の右辺に、定義しようとする関数が現れるような定義方法を、再帰的定義といいます。

これはそのまま Gauche のプログラムで書けます。

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

プログラムで解くべき問題の多くは、再帰的な定義を考えることで、そのままプログラムにすることができます。

5.2. 再帰的なデータ構造

5.2.1. データの合成

2章で書いたプログラムでは、単純な関数を組み合わせて名前をつけるというのをやりましたが、データ表現でも単純なデータを組み合わせてそれに名前をつけることで、いろいろな概念を表現しやすくなります。

Gauche ではデータを組み合わせるには、cons を使います。 cons は 2つのデータを組み合せます。組み合されたデータから、元のデータを取り出すには、car と cdr を使います。

gosh> (define a-combined-data (cons 1 2))
a-combined-data
gosh> (car a-combined-data)
1
gosh> (cdr a-combined-data)
2

5.2.2. リスト

空リスト () または、(cons <要素> <リスト>)で作られた、組み合されたデータのことをリストと呼びます。データがリストであるかどうかは、 list? という述語を使います。

gosh> (list? ())
#t
gosh> (define singleton (cons 1 ()))
singleton
gosh> (list? singleton)
#t
gosh> (car singleton)
1
gosh> (cdr singleton)
()
gosh> (define int-list (cons 1 (cons 2 (cons 3 ()))))
int-list
gosh> (list? int-list)
#t
gosh> int-list
(1 2 3)
gosh> (car int-list)
1
gosh> (cdr int-list)
(2 3)
gosh> (car (cdr int-list))
2
gosh> (cdr (cdr int-list))
(3)
gosh> (car (cdr (cdr int-list)))
3

リストの要素を順番に、cons で繋ぐのが面倒なときには、list という関数を使うと便利です。

gosh> (list 1 2 3 4 5)
(1 2 3 4 5)

5.2.3. リスト構造は再帰構造

このリストの構造は、Gauche では最も良く使う重要なデータ構造です。リストの定義をもう一度みてみると、

<リスト> = 空リスト () または (cons 要素 <リスト>)

これも、定義の右辺に、定義されるものが現れています。ここにも「再帰」がありますね。

5.3. 組合せの列挙

もうひとつ、再帰の問題を考えてみましょう。

与えられたn個の相異る要素を持つリストのから、k (1 <= k <= n)個の要素を取り出すときの組合せ(リストで表現される)のリストを列挙する関数を作れ

関数は、(comb k xs) のように使うものとします。 k は取り出す数、xs は元のリストです。たとえば、 1から5までの数字から二つとりだす組合せは、

gosh> (define sample-list (list 1 2 3 4 5))
sample-list
gosh> (comb 2 sample-list)
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))

のようになることを想定しています。

すなおに考えればいいです。このような組合せは、まず、自明な例を考えましょう。これは、2つ引数について最も単純な例をそれぞれ考えましょう。

もともとのリスト xs が空なら、なにも取り出せませんから、組合せも空。
```
(if (null? xs) 
    ()
    <???>)
```
とりだすのが 1 つだけなら、組合せはそれぞれの要素を一つだけ含むリストのリスト
```
(if (= k 1)
    (map list xs))
    <???>
```

たとえば、(comb 1 sample-list) なら、これは、(map list sample-list) と同じです。

gosh> (map list sample-list)
((1) (2) (3) (4) (5))

ここで、map について、簡単に解説しておきましょう。
map は第一引数である関数を、第二引数のリストのそれぞれの要素に適用したリストを返す関数です(厳密にはもっと拡張されています)。たとえば、
gosh> (define inc (lambda (x) (+ x 1)))
inc
のように、引数に1を加えた数を返す関数 inc を定義しておいて、先程の sample-list に適用してみましょう。
gosh> sample-list
(1 2 3 4 5)
gosh> (map inc sample-text)
(2 3 4 5 6)
のようになります。また、引数を自乗する関数 square を
gosh> (define square (lambda (x) (* x x)))
と定義します。これで、(map square sample-list) を計算すると、どうなるでしょう。実際に gosh に計算させる前に答を予想しましょう。
予想しましたか？では確かめてみましょう。
gosh> (map square sample-list)
(1 4 9 16 25)
あってましたか？

ちょっと脱線しましたが、comb の自明な場合の計算ができましたので、次に、一般の場合を考えてみましょう。一般の場合には、次の二つに分けて考えるのが分りやすいでしょう。

最初の要素を含む組合せのリスト
最初の要素を含まない組合せのリスト

の二つにわけて考えましょう。このふたつを連結すれば、求めるリストが作成できますよね。

1. の方は、

「最初の要素を除いた、n-1 個の要素からなるリスト(cdr xs) から、k - 1 個の要素を取りだすときの組合せ (comb (- k 1) (cdr xs)) のそれぞれに、最初の要素 (car xs) を加えたもの」です。すなわち、

(map (lambda (cs) (cons (car xs) cs))
     (comb (- k 1) (cdr xs)))

となります。

2. の方は簡単で、

「最初の要素を除いた、n-1 個の要素からなるリスト(cdr xs) から k 個の要素を取り出すときの組合せ」です。すなわち、

(comb k (cdr xs))

1. と 2. の二つのリストを連結するには、append という組み込み関数を使います。

(append (map (lambda (cs) (cons (car xs) cs)) (comb (- k 1) (cdr xs)))
        (comb k (cdr xs)))

さて、これら全部をまとめると、

(define (comb k xs)
  (if (null? xs)
      ()
      (if (= k 1)
          (map list xs)
          (append (map (lambda (cs) (cons (car xs) cs)) (comb (- k 1) (cdr xs)))
                  (comb k (cdr xs))))))

となりますね。

gosh> (comb 3 sample-list)
((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
gosh> (comb 4 (sample-list))
((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))

5.4. 練習問題

問題 5.1.

n 以下の非負の整数の和を求める関数を定義しなさい。
n 以下の非負の整数の自乗の和を求める関数を定義しなさい。
n 以下の奇数の和を求める関数を定義しなさい。

問題 5.2.

n個のあいことなるものからk個取りだして、並べると何通りの並べ方があるかを示す関数を定義しなさい。

Kahua

News

Site Info

Kahua開発日記

Enjoy Gauche