6.md

再帰ドリル(6)：再帰のこころ

再帰のこころとは

• 一歩手前ができているとすると次はどうする？

だ。

階乗を思い出そう。

my_fact 1 = 1
my_fact 2 = 1 * 2
my_fact 3 = 1 * 2 * 3
my_fact 4 = 1 * 2 * 3 * 4
my_fact 5 = 1 * 2 * 3 * 4 * 5

一歩手前ができているとすると次はどうする？

my_fact 1 = 1
my_fact 2 = my_fact 1 * 2
my_fact 3 = my_fact 2 * 3
my_fact 4 = my_fact 3 * 4
my_fact 5 = my_fact 4 * 5

これを一般化するとどうなる？

my_fact :: Integer -> Integer
my_fact 1 = 1
my_fact n = my_fact (n - 1) * n

気を付けたいのは、基底部と再帰部との関係である。再帰を止めるには、再帰の際に基底部(終了条件)に向かうようにしなければならない。階乗の再帰部では、n は 2 以上であり、終了条件は n == 1 であるから、再帰する際に n を小さくして行く必要がある。

再帰のこころを追加しておこう。

• 基底部：もっとも簡単なケースを考察して、終了条件を書く
• 再帰部：再帰の際は、引数が終了条件に向かうようにする

ここで例として、再帰的かつ高速な冪乗の実装を思い出そう。

my_power_fast :: Integer -> Integer -> Integer
my_power_fast _ 0 = 1
my_power_fast m n
  | odd n     = my_power_fast (m*m) (n `div` 2) * m
  | otherwise = my_power_fast (m*m) (n `div` 2)

終了条件は、第二引数が 0 のときである。再帰の際は、第二引数が n `div` 2 のように小さくなっていることが分かる。逆に終了に関係ない第一引数は、自由に使われている(大きくなって行く)。

ループに対する再帰の利点

再帰がループに比べてよい点は以下の通り。

• 制御が木構造に制限されているので、理解しやすい。入り口が一つで、枝分かれして行き、末端の葉の部分で終了するか、自分か他の関数へジャンプする
• ジャンプの際に、引数がどう変化するのか明示的に示される
• 型検査のある言語では、末端の葉の部分で型検査の洗礼を受ける。これで多くの間違いが発見できる

ループを超えた再帰

これまでに出てきた再帰は、簡単に末尾再帰の形に直せた。つまり、ループと同等であった。

簡単には末尾再帰の形に直せないとき、我々はループを超えた再帰の力に頼ることになる。ループを超えた再帰の力とは、スタックの自動管理である。正格評価では、戻って来る場所をスタックに積んで、関数を呼び出す。再帰は、関数呼び出しで使われるこのスタックの自動管理を存分に活用していると言える。

もちろん、ループでも自分でスタックを管理すれば、ループを超えた再帰と同じことはできる。しかし、それは煩雑で間違いを起こしやすい。

以下ではループを超えた再帰を使う問題を紹介する。これらの問題は、これまでの問題に比べると難しい。なぜなら、ループでは簡単には実装できないからだ。最初分からなくても、がっかりしないていただきたい。ただ、ソフトウェアに力を入れている会社の面接で出題されることもあるので、何度も挑戦して理解して欲しい。

経路の数

n 掛ける n の升目状の道があって、左下の角(S)から右上の角(D)へ向かうとする。ただし、進めるのは右か上で、しかも対角線を横切ってはいけない。また、通ってよいのは右下の半分である。経路の総数はいくつあるか？

以下の図から分かるように n が 3 の場合、経路の総数は 5 である。

ここでしばらく問題を考えること！

では、解き方を説明する。

右方向に進んだ数を m、上方向に進んだ数を n とし、その地点への経路の総数を cat m n で表すとする。ここで最初は右にしか進めないので、m は n 以上であることに注意しよう。

上の図から分かるように以下の二つに場合分けできる。

• m == n のとき：対角線上の地点では、下からの経路しかない
• m > n のとき：左からと下からの経路がある

この考察に基づいて、経路の総数を計算する関数 my_catalan を完成させよ。

my_catalan :: Integer -> Integer
my_catalan x = my_cat x x

my_cat :: Integer -> Integer -> Integer
my_cat _ 0 = 1
my_cat m n
  | m == n    = undefined
  | otherwise = undefined

二分木の数

ノードの数を n としたとき、二分木の形の総数(Nn で表す)はいくつあるか？

問題を理解するために、n が 1、2、3 のときを図示する。

この図から分かるように

• N1 = 1
• N2 = 2
• N3 = 5

である。

ここでしばらく問題を考えること！

では、解き方を説明する。

n 個のノードを持つ木において、根のノードから見る。左の部分木の総数を Nl で表し、右の総数を Nr で表すと、r + l == n - 1 の関係が成り立つ。この考察から、組み合わせを考えて、その総和を取ればよい。

以下のコードを変更して、二分木の数を計算する関数 my_catalan2 を実装せよ。

my_catalan2 :: Integer -> Integer
my_catalan2 0 = 1
my_catalan2 n = sum (zipWith (*) xs ys)
  where
    xs = undefined
    ys = undefined

実は、「経路の数」と「二分木の数」は、カタラン数という同じ問題である。今回は、カタラン数を 2 種類の方法で解いたことになる。以下に、カタラン数が根底にある問題の一例を示す。

• 一泊 5,000 円のホテルがある。ここに 5,000 円を持った客 n 人と 10,000円を持った客 n 人を泊まらせたい。ホテルには受付開始時におつりが用意されてない。おつりが不足しないような客の来方は、何通りあるか？

コインの両替

ある金額を日本のコインを使って両替するとする。両替の仕方は、何通りあるか？

たとえば、10円玉を一枚持っているとすると、両替の仕方は

• 10円 x 1
• 5円 x 2
• 5円 x 1 + 1円 x 5
• 1円 x 10

の4通り。

ここでしばらく問題を考えること！

では、解き方を説明する。

使えるコインがある順番(例えば小さい順)に並んでいるとする。以下の2つで場合分けをする。

• 先頭のコインを含む全部のコインを使える
• 先頭のコインを除いた残りのコインが使える

使えるコインの先頭で金額を減らして行く。こうやって、すべての両替のパターンを網羅する。

終了条件は以下のようになる。

• 金額が 0 になったら、両替ができたことになるので、そのやり方は1通り。
• 金額がマイナスになったら、両替えできないことになるので、そのやり方は0通り。
• 使えるコインが亡くなったら、両替えできないことになるので、そのやり方は0通り。

金額15円をコイン 1,5,10 で両替する場合を以下に図示する。両替の方法を網羅的に探しているのが分かるだろうか？

以下のコードを変更して、両替の総数を計算する関数 my_coin を実装せよ。

my_coin :: Integer -> [Integer] -> Integer
my_coin 0 _   = 1
my_coin _ []  = 0
my_coin n (c:cs)
  | n < 0     = 0
  | otherwise = undefined

ヒント：多分木を直接表すのは難しいので、以下のように二分木で実装するとよい。

[目次] [演習6]