前回は関数の基本的な使い方と、モジュール、ファイル入出力について説明しました。今回は再帰定義を中心に Python の関数について詳しく説明します。関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。
関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。Python の関数も再帰呼び出しが可能です。
再帰定義というと、Lisp など「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックのひとつと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 1 に示します。
階乗の定義からわかるように、n の階乗を求めるには n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 1 を見てください。
リスト 1 : 階乗
def fact(n):
if n == 0: return 1
return n * fact(n - 1)
関数 fact() は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact() の定義で fact() 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
それでは、再帰呼び出しのポイントを説明しましょう。図 2 を見てください。
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│Call:1 │->│Call:2 │->│Call:3 │->│Call:4 │->│Call:5 │
│n:4 │ │n:3 │ │n:2 │ │n:1 │ │n:0 │
│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
図 2 : fact の再帰呼び出し（n:引数の値, value:返り値）
図 2 は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact() を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数はローカル変数として扱われます。前回説明したように、ローカル変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。ローカル変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成されたローカル変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると変数 n はひとつしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Python であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
簡単な実行例を示します。
>>> def fact(n): ... if n == 0: return 1 ... return n * fact(n - 1) ... >>> fact(4) 24 >>> fact(10) 3628800 >>> fact(20) 2432902008176640000 >>> fact(50) 30414093201713378043612608166064768844377641568960512000000000000
もうひとつ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。
ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。
ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。
左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。
次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。
右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。
式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。
あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。リスト 2 を見てください。
リスト 2 : 最大公約数
def gcd(a, b):
if b == 0: return a
return gcd(b, a % b)
関数 gcd() は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd() を再帰呼び出しして、b と a % b の最大公約数を求めます。
リスト 2 はユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。それでは実行例を示しましょう。
>>> def gcd(a, b): ... if b == 0: return a ... return gcd(b, a % b) ... >>> gcd(42, 30) 6 >>> gcd(15, 70) 5
最小公倍数は最大公約数を使って簡単に求めることができます。リスト 3 を見てください。
リスト 3 : 最大公倍数
def lcm(a, b):
return a * b // gcd(a, b)
整数 a と b の最小公倍数は a * b // gcd(a, b) で求めることができます。実行例を示します。
>>> def lcm(a, b): ... return a * b // gcd(a, b) ... >>> lcm(5, 7) 35 >>> lcm(14, 35) 70
再帰定義のなかで、最後に再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰ということがあります。末尾再帰は簡単な処理で繰り返しに変換することができます。これを「末尾再帰最適化」といいます。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルするときに、この最適化を行う処理系があります。なかには Scheme [*1] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact() を思い出してください。リスト 1 の fact() は最後に n と fact() の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると、リスト 4 になります。
リスト 4 : 階乗（末尾再帰）
def fact(n, a = 1):
if n == 0: return a
return fact(n - 1, n * a)
最後の再帰呼び出しで、fact() の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば fact(4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算しています。このとき、計算の途中経過を引数 a に記憶しているのです。fact() の呼び出しを図に示すと、図 3 のようになります。
fact(4, 1)
fact(3, 4)
fact(2, 12)
fact(1, 24)
fact(0, 24)
=> a の値 24 を返す
=> 24
=> 24
=> 24
=> 24
図 3 : fact() の動作
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の場合、while 文や for 文などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、最大公約数を求める関数 gcd() は末尾再帰になっています。Python は末尾再帰最適化をサポートしていませんが、繰り返しに変換するのは簡単です。リスト 5 を見てください。
リスト 5 : 最大公約数を求める
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったリスト 2 のプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです
前回は例題として挿入ソートを取り上げました。挿入ソートは簡単なアルゴリズムですが、要素数の 2 乗に比例する遅いソートです。今回は再帰定義の例題として、高速なソートアルゴリズムを取り上げます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でもクイックソート (quick sort) は高速なソートアルゴリズムとして有名です。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。2 つに分けた各々のグループを同様に分割して 2 つのグループに分けます。最後はグループの要素がひとつになってソートが完了します。
9 5 3 7 6 4 2 8 最初の状態
9 5 3 7 6 4 2 8 7 を枢軸にして左側から 7 以上の値を探し、
L R 右側から 7 以下の値を探す。
2 5 3 7 6 4 9 8 交換する
L R
2 5 3 7 6 4 9 8 検索する
L R
2 5 3 4 6 7 9 8 交換する
L R
2 5 3 4 6 7 9 8 検索する。R と L が交差したら分割終了。
R L
[2 5 3 4 6] [7 9 8] この 2 つのグループについて再び
同様な分割を行う
図 4 : クイックソート
基準になる値のことを「枢軸 (pivot)」といいます。枢軸は要素の中から適当な値を選びます。今回は中央にある要素を選ぶことにしましょう。図 4 を見てください。左側から枢軸 7 以上の要素を探し、右側から 7 以下の要素を探します。探索のときは枢軸が番兵の役割を果たすので、ソート範囲外の要素を探索することはありません。見つけたらお互いの要素を交換します。探索位置が交差したら分割は終了です。
あとは同じ手順を分割した 2 つのグループに適用します。これは再帰定義を使えば簡単に実現できます。分割したグループの要素数が 1 になったときが再帰の停止条件になります。プログラムをリスト 6 に示します。
リスト 6 : クイックソート
def quick_sort(buffer, low, high):
pivot = buffer[(low + high) // 2]
i = low
j = high
while True:
while pivot > buffer[i]: i += 1
while pivot < buffer[j]: j -= 1
if i >= j: break
tmp = buffer[i]
buffer[i] = buffer[j]
buffer[j] = tmp
i += 1
j -= 1
if low < i - 1: quick_sort(buffer, low, i - 1)
if high > j + 1: quick_sort(buffer, j + 1, high)
関数 quick_sort() の引数 buffer がソートするリスト、low が区間の下限値、high が区間の上限値です。quick_sort() は buffer の low から high までの区間をソートします。
最初に、区間の中央にあるデータを枢軸として選びます。次の while ループで、左側から枢軸以上の要素を探しています。ここでは枢軸以上という条件を、枢軸より小さい間は探索位置を進める、というように置き換えています。同様に次の while ループで右側から枢軸以下の要素を探します。お互いの探索位置 i, j が交差したら分割は終了です。break 文で while ループから脱出します。そうでなければお互いの要素を交換します。交換したあとは i と j を更新しておくことを忘れないでください。
そして、分割した区間に対して quick_sort() を再帰呼び出しします。このとき要素数をチェックして、2 個以上ある場合に再帰呼び出しを行います。この停止条件を忘れると正常に動作しません。ご注意ください。
それでは実際に実行してみましょう。
>>> a = [5, 9, 1, 8, 2, 7, 3, 6, 4] >>> quick_sort(a, 0, 8) >>> a [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> b = ['foo', 'bar', 'baz', 'abc', 'def'] >>> quick_sort(b, 0, 4) >>> b ['abc', 'bar', 'baz', 'def', 'foo']
このように、quick_sort() は数値だけではなく、比較演算子で大小関係を比較できるデータであればソートすることができます。
クイックソートは、枢軸の選び方で効率が大きく左右されます。区間の中間値を枢軸に選ぶと、区間をほぼ半分に分割することができます。この場合がいちばん効率が良く、データ数を N とすると N * log2 N に比例する時間でソートすることができます。
逆に、区間での最大値または最小値を枢軸に選ぶと、その要素と残りの要素の 2 つに分割にされることになります。これが最悪の場合で、分割のたびに最大値もしくは最小値を選ぶと、実行時間は要素数の 2 乗に比例することになります。つまり、挿入ソートと同じくらい遅いソートになるのです。
この問題は枢軸の選び方を工夫することで、完全ではありませんが回避することができます。区間の中からいくつかの要素を選び、その中で中間の値を持つ要素を枢軸とします。たくさんの要素を選ぶとそれだけ最悪の枢軸を選ぶ危険性は少なくなりますが、値を選ぶのに時間がかかってしまいます。実際には 3 つから 5 つの要素を選んで、その中で中央の値を持つ要素を枢軸とする場合が多いようです。
複雑な問題を厳密に解こうとするときや、条件を満たす解をすべて求める必要があるとき、可能性のあるパターンをすべて生成して、条件を満たしているかチェックするしか方法がない場合があります。このようなとき用いる手法に「バックトラック法 (backtracking)」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。
このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。
簡単な例題として、「順列 (permutation)」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。リスト 7 を見てください。
リスト 7 : 順列の生成（繰り返し版）
def make_perm():
perm = []
# 1 番目の数字を選ぶ
for a in range(1, 5):
perm.append(a)
# 2 番目の数字を選ぶ
for b in range(1, 5):
if b in perm: continue
perm.append(b)
# 3 番目の数字を選ぶ
for c in range(1, 5):
if c in perm: continue
perm.append(c)
# 4 番目の数字を選ぶ
for d in range(1, 5):
if d in perm: continue
perm.append(d)
print(perm)
perm.pop()
perm.pop()
perm.pop()
perm.pop()
>>> make_perm() [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] [1, 4, 3, 2] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 1, 3] [2, 4, 3, 1] [3, 1, 2, 4] [3, 1, 4, 2] [3, 2, 1, 4] [3, 2, 4, 1] [3, 4, 1, 2] [3, 4, 2, 1] [4, 1, 2, 3] [4, 1, 3, 2] [4, 2, 1, 3] [4, 2, 3, 1] [4, 3, 1, 2] [4, 3, 2, 1]
少々長いリストですが、やっていることは簡単です。選んだ数字はリスト perm に append() で追加します。あとは perm に格納されていない数字を選んでいくだけです。数字を 4 つ選んだら print() で perm を出力します。そして、次の順列を発生させるため perm から pop() で数字を削除して、ひとつ前のループに後戻りします。選ぶ数字がなくなったならば、もうひとつ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成させることができます。
このプログラムは 4 重のループですが、けっこうたいへんです。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムすることができます。リスト 8 を見てください。
リスト 8 : 順列の生成 (再帰版)
def make_perm1(perm, n, m = 0):
if n == m: print(perm)
else:
for x in range(1, n + 1):
if x in perm: continue
perm.append(x)
make_perm1(perm, n, m + 1)
perm.pop()
関数 make_perm1() は、1 から n までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで引数のリスト perm に追加します。あとは perm にはない数字を選んでいきます。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。
引数 m は選んだ数字の個数をカウントします。n と m が等しい場合は n 個の数字を選んだので perm を出力します。ここで n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。そのあとは、pop() で選んだ数字を削除して新しい数字を選びます。もしも選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から n までの順列をすべて生成することができます。
今度はバックトラックを使ってパズルを解いてみましょう。簡単な例題として「8 クイーン」を取り上げます。これはコンピュータに解かせるパズルの中でも特に有名な問題です。8 クイーンは、8 行 8 列のチェスの升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を図 5 に示します。
列
0 1 2 3 4 5 6 7
*-----------------*
0 | Q . . . . . . . |
1 | . . . . Q . . . |
2 | . . . . . . . Q |
行 3 | . . . . . Q . . |
4 | . . Q . . . . . |
5 | . . . . . . Q . |
6 | . Q . . . . . . |
7 | . . . Q . . . . |
*-----------------*
図 5 : 8 クイーンの解答例
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 * 63 * ... * 57 = 178462987637760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。図 5 の解答例をリストを使って表すと図 6 のようになります。
0 1 2 3 4 5 6 7 <-- 列の位置
---------------------------
[0, 6, 4, 7, 1, 3, 5, 2] <-- 要素が行の位置を表す
図 6 : リストでの行と列の表現方法
列をリストの位置に、行番号を要素に対応させれば、各要素には 0 から 7 までの数字が重複しないで入ることになります。すなわち、0 から 7 までの順列の総数である 8! = 40320 通りの置き方を調べればよいことになります。パズルを解く場合は、そのパズル固有の性質をうまく使って、生成するパターンの総数を減らすように工夫することが大切です。
順列を生成するプログラムは簡単です。あとは、生成した順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。可能性のあるデータをもれなく作るのにバックトラック法は最適です。ただし、生成するデータ数が多くなると時間がとてもかかるので注意してください。
それでは、プログラムを作りましょう。ポイントは斜めの利き筋のチェックです。図 7 を見てください。
右斜め上の利き筋 左斜め上の利き筋
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*-----------------* *-----------------*
|／／／／／／／／ | 8 -1 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 9 -2 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 10 -3 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 11 -4 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 12 -5 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 13 -6 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 14 -7 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | |＼＼＼＼＼＼＼＼ |
*-----------------* *-----------------*
x + y = constant x - y = constant
例 : (x, y) 例 ; (x , y)
(2, 0) (1, 1) (0, 2) => 2 (5, 0) (6, 1) (7, 1) => 5
図 7 : 斜めの利き筋
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になる、ということを利用すれば簡単にチェックできます。プログラムはリスト 9 のようになります。
リスト 9 : 斜め利き筋のチェック
def check(board, n):
for y in range(1, n):
if conflict(board, board[y], y): return False
return True
盤面を表すリストは引数 board に渡します。関数 check() の引数 n がクイーンの個数、ローカル変数 y が列を表します。check() は y 列のクイーンが 0 から y - 1 列までのクイーンと衝突していないか、関数 conflict() を呼び出してチェックします。
最初は、1 列目のクイーンが 0 列のクイーンと衝突していないかチェックし、次に 2 列目のクイーンと 0, 1 列のクイーンをチェックします。このように、順番にクイーンをチェックしていき、最後に 7 列目のクイーンと 0 - 6 列のクイーンをチェックします。クイーン同士が衝突していたら False を返し、そうでなければ True を返します。
次は関数 conflict() を作りましょう。リスト 10 を見てください。
リスト 10 : 衝突のチェック
def conflict(board, x, y):
for y1 in range(0, y):
x1 = board[y1]
if x1 - y1 == x - y or x1 + y1 == x + y:
return True
return False
関数 conflict() の引数 x がチェックするクイーンの行、y が列を表します。for ループで 0 列から y - 1 列のクイーンを取り出します。変数 x1 に行を、変数 y2 に列をセットします。あとはクイーン (x, y) と (x1, y1) の斜めの利き筋をチェックし、同じであれば衝突しているので True を返します。0 から y - 1 列のクイーンと衝突していなければ、最後に False を返します。
ここまで作ればあとは簡単です。8 クイーンを解くプログラムはリスト 11 のようになります。
リスト 11 : 8 クイーンの解法 (単純版)
def queen(board, n, y = 0):
global cnt
if n == y:
if check(board, n):
print(board)
else:
for x in range(0, n):
if x in board: continue
board.append(x)
queen(board, n, y + 1)
board.pop()
関数 queen() は順列を生成する関数 make_perm() とほとんど同じです。引数 n がクイーンの個数で、y がクイーンを配置する列を表します。y が n と等しくなったならば、クイーンをすべて配置したので、check() を呼び出して斜めの利き筋をチェックします。条件を満たしていれば、print() で board を出力します。実際に実行すると 92 通りの解を出力します。
ところで、このプログラムは順列を生成してからクイーンの衝突をチェックしているので、クイーンの個数を増やすと時間がとてもかかります。M.Hiroi の環境で測定した結果を表 1 に示します。
| 個数 | 8 | 9 | 10 |
|---|---|---|---|
| queen() | 0.14 | 1.44 | 15.45 |
クイーンの個数を増やすと、実行時間は大幅に増加します。時間かかかる理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (0, 0) の位置にクイーンを置くと、次のクイーンは (1, 1) の位置に置くことはできません。したがって、[0, 1, ...] という配置はすべて失敗することがわかるわけですが、順列を生成させてからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムするとリスト 12 のようになります。
リスト 12 : 8 クイーンの高速化
def queen1(board, n, y = 0):
global cnt
if n == y:
# print(board)
cnt += 1 # 解の個数をカウントする
else:
for x in range(0, n):
if x in board or conflict(x, y): continue
board.append(x)
queen1(board, n, y + 1)
board.pop()
追加したクイーン (x, y) が board 内のクイーンと衝突していないか関数 conflict() を呼び出してチェックします。for ループの中で衝突のチェックを行うことで、無駄な順列を生成しないようにするわけです。
このように、できるだけ早い段階でチェックを入れることで無駄なデータをカットすることを「枝刈り」と呼びます。バックトラック法を使って問題を解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。ところが、枝刈りの方法は問題によって違います。問題固有の性質をよく調べて、適切な枝刈りを考えることが重要になります。バックトラック法を使う場合は十分に注意してください。
それでは、実行結果を表 2 に示します。
| 個数 | 8 | 9 | 10 |
|---|---|---|---|
| queen() | 0.14 | 1.44 | 15.45 |
| queen1() | 0.01 | 0.03 | 0.17 |
このように、枝狩りを行うことで実行時間を大幅に短縮することができます。ところで、今回は単純にリストを出力するだけなので、ちょっと面白くありません。興味のある方は、解答例のような図を出力するプログラムを作ってみてください。
Python は手続き型言語ですが、Lisp などの関数型言語のように、関数を変数に代入したり、引数として渡すことができます。また、値として関数を返すこともできるので、関数を作る関数を定義することもできます。関数を引数として受け取る関数を高階関数 (higher order function) と呼びます。
簡単な例として、引数の関数 func() にリストの要素を渡して呼び出し、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。なお、関数に引数を与えて呼び出すことを、関数型言語では「適用」といいます。本稿でも関数呼び出しの意味で適用を使うことにします。プログラムをリスト 13 に示します。
リスト 13 : マッピング
def mapcar(func, ls):
new_list = []
for x in ls:
new_list.append(func(x))
return new_list
Python には関数 map() が定義されているので、関数名は mapcar としました。名前は Common Lisp から拝借しました。受け取った関数を呼び出す場合、Python では特別なことを行う必要はありません。Python は引数 func が関数 func() として使われているので、引数 func の値を関数として呼び出します。関数を渡す場合も簡単です。関数が定義されている変数を渡すだけでいいのです。
それでは実行例を示しましょう。
>>> def square(x): return x * x ... >>> mapcar(square, [1, 2, 3, 4, 5]) [1, 4, 9, 16, 25]
引数を 2 乗する関数 square() を定義します。この関数を mapcar() に渡すと、要素を 2 乗した新しいリストを返します。
Python のマップ関数 map() は、リストだけではなく iterable を受け取って iterable を返します。簡単な使用例を示します。
>>> map(square, [1, 2, 3, 4, 5]) <map object at 0x7fa40f8763d0> >>> for x in map(square, [1, 2, 3, 4, 5]): print(x) ... 1 4 9 16 25 >>> list(map(square, [1, 2, 3, 4, 5])) [1, 4, 9, 16, 25] >>> list(map(square, range(1, 10))) [1, 4, 9, 16, 25, 36, 49, 64, 81]
フィルター (filter) はリストの要素に func() を適用し、func() が真を返す [*2] 要素をリストに格納して返す関数です。ここでは簡単な例題として、関数が真を返す要素を削除する関数 remove_if() を作ってみましょう。関数名は Common Lisp から拝借しました。
リスト 14 : 要素の削除
def remove_if(func, ls):
new_list = []
for x in ls:
if not func(x): new_list.append(x)
return new_list
mapcar() と同様に remove_if() も簡単です。func(x) が偽ならば x をリストに加えるだけです。not で func(x) の真偽を反転していることに注意してください。
簡単な実行例を示します。
>>> def isOdd(x): return x % 2 == 1 ... >>> remove_if(isOdd, [1, 2, 3, 4, 5]) [2, 4]
関数 isOdd() は引数 x が奇数であれば真を返し、そうでなければ偽を返します。isOdd() を remove_if() に渡すと、奇数の要素を削除した新しいリストを返します。
Python のフィルター関数 filter() は、map() と同様に iterable を受け取って iterable を返します。
>>> filter(isOdd, [1, 2, 3, 4, 5, 6]) <filter object at 0x7fa40f8bdd00> >>> list(filter(isOdd, [1, 2, 3, 4, 5, 6])) [1, 3, 5] >>> list(filter(isOdd, range(1, 11))) [1, 3, 5, 7, 9]
次は「畳み込み」について説明します。2 つの引数を取る関数 f() とリストを引数に受け取る関数 reduce() を考えます。そして、reduce() はリストの各要素に対して関数 f を次のように適用します。
(1) [a1, a2, a3, ..., an-1, an] => f( ... f( f( a1, a2 ), a3 ), ...), an-1 ), an )
(2) [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an-1, an ) ... )))
図 8-A : 畳み込みの動作
関数 f を適用する順番で 2 通りの方法があります。たとえば、関数 f が単純な加算関数とすると、reduce() の結果はリストの要素の和になります。
f(x, y) = x + y の場合 : reduce => a1 + a2 + a3 + ... + an-1 + an
このような操作を「縮約」とか「畳み込み」といいます。reduce() は引数に初期値 g を指定する場合があります。この場合は、次のような動作になります。
(1) [a1, a2, a3, ..., an-1, an] => f( ... f( f( g, a1 ), a2 ), ...), an-1 ), an )
(2) [a1, a2, a3, ..., an-1, an] => f( a1, f( a2, f( a3, ..., f( an, g ) ... )))
図 8-B : 畳み込みの動作
ここでは簡単な例題として上図 (1) と同じ動作を行う関数 fold() を作ってみましょう。リスト 15 を見てください。
リスト 15 : 畳み込み
def fold(func, ls, init):
a = init
for x in ls:
a = func(a, x)
return a
fold() の引数 func が適用する関数、ls がリスト、init が初期値です。最初にローカル変数 a を init で初期化します。次に、for ループで ls の要素を一つずつ取り出し、func(a, x) を実行します。fold() は変数 a の値を func() の返り値に更新することで、図 8-B (1) の動作を実現しています。
たとえば、リストが [1, 2, 3] で init が 0 とします。最初は func(0, 1) が実行され、その返り値が a にセットされます。次は func(a, 2) が実行されますが、これは func(func(0, 1), 2) と同じことです。そして、その結果が a にセットされます。最後に func(a, 3) が実行されますが、これは func(func(func(0, 1), 2), 3) となり、図 8-B (1) と同じ動作になります。
それでは実行例を示します。
>>> def add(x, y): return x + y ... >>> fold(add, [1, 2, 3, 4, 5], 0) 15 >>> fold(gcd, [63, 42, 35], 0) 7
fold() に関数 add() を渡すと、リストの要素の合計値を求めることができます。関数 gcd() を渡すと、リストの要素の最大公約数を求めることができます。このように、fold() は 2 引数の関数と組み合わせると、いろいろな処理を実現することができます。
Python の場合、畳み込みを行う関数 reduce() はモジュール functools に定義されています。reduce() も引数に iterable を受け取ることができます。
>>> import functools >>> functools.reduce(add, [1, 2, 3, 4, 5], 0) 15 >>> functools.reduce(add, [1, 2, 3, 4, 5]) 15 >>> functools.reduce(add, range(1, 11)) 55 >>> functools.reduce(add, range(1, 1001)) 500500
Python の reduce() は初期値を省略することができます。その場合、図 8-A (1) の動作になります。
ところで、高階関数を使うようになると、数を 2 乗する square() のような小さな関数を定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。
このような場合、Python では名前のない関数を生成する「ラムダ形式 (lambda form)」[*3] を使うことができます。ラムダはギリシャ文字のλのことです。それでは、理屈はともかくラムダ形式の使用例を見てください。
>>> lambda x, y: x + y <function <lambda> at 0x7f856c1a0310> >>> (lambda x, y: x + y)(1, 2) 3 >>> func = lambda x, y: x + y >>> func(10, 20) 30
ラムダ形式はキーワード lambda で始まります。
lambda 引数, ...: 式 => 関数の実体
そのあと引数を指定し、コロンの後ろに実行する式を定義します。ラムダ形式の場合、式は一つしか定義できず、文も定義できません。
ラムダ形式は関数の実体 [*4] を返します。ラムダ式が返す関数に引数を渡せば、それを呼び出すことができます。また、変数に格納しておいて関数のように呼び出すこともできます。ラムダ形式を呼び出すと、式の評価結果を返します。return がなくても値を返すことに注意してくてください。
さらに、ラムダ形式を使って高階関数に関数を渡すこともできます。たとえば、リストの要素を 2 乗する処理は、次のようにラムダ形式を使って実現できます。
>>> mapcar(lambda x: x * x, [1, 2, 3, 4, 5]) [1, 4, 9, 16, 25]
わざわざ square() を定義しなくてもいいので簡単です。このように、ラムダ形式は高階関数と組み合わせて使うと便利です。
ここで、もう少し詳しくローカル変数の規則を見てみましょう。変数 x を表示する関数 foo() を定義します。
>>> def foo(): ... print(x) ... >>> x = 10 >>> foo() 10
foo() には変数 x を定義していないので、foo() を実行した場合グローバル変数の値を探しにいきます。それでは foo1() という関数から foo() を呼び出す場合を考えてみましょう。foo1() にはローカル変数 x を定義します。この場合、foo() はどちらの値を表示するのでしょうか。実際に試してみましょう。
>>> def foo1(): ... x = 100 ... foo() ... >>> foo1() 10
グローバル変数の値を表示しました。このように、foo1() で定義したローカル変数 x は、foo() からアクセスすることはできません。図 9 を見てください。
┌────── Python system ──────┐
│ │
│ グローバル変数 x ←────┐ │
│ │ │
│ ┌→┌─ 関数 foo ──────┐ │ │
│ │ │ ┌──────┼─┘ │
│ │ │ print x │ │
│ │ └────────────┘ │
│ │ ┌─ 関数 foo1 ─────┐ │
│ │ │ │ │
│ │ │ x = 100 │ │
│ └─┼─ foo() │ │
│ └────────────┘ │
│ │
└────────────────────┘
図 9 : レキシカルスコープ
図 9 では、変数の有効範囲を枠で表しています。foo1() で定義したローカル変数 x は、関数 foo1() の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。この場合、関数定義の枠しかないので、ここで変数が見つからない場合はグローバル変数を調べます。
foo() は関数定義の枠しかありません。そこに変数 x が定義されていないので、グローバル変数を調べることになるのです。このように、foo() から foo1() の枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ (lexical scope)」といいます。レキシカルには文脈上いう意味があり、変数が定義されている範囲内 (枠内) でないと、その変数にアクセスすることはできません。
それでは、ラムダ形式の場合はどうでしょうか。リスト 16 を見てください。
リスト 16 : リストの要素を n 倍する
def times_element(n, ls):
return list(map(lambda x: x * n, ls))
ラムダ形式の仮引数は x だけですから、変数 n はグローバル変数をアクセスすると思われるかもしれません。ところが、変数 n は関数 times_element の引数 n をアクセスするのです。図 10 を見てください。
┌────── Python system ─────┐
│ │
│ ┌─ times_element : n l ─┐ │
│ │ ↑ │ │
│ │ └─┐ │ │
│ │ ┌─ lambda : x ─┐│ │ │
│ │ │ ↑ ││ │ │
│ │ │ ┌──┘ ││ │ │
│ │ │ x * n ││ │ │
│ │ │ └──┼┘ │ │
│ │ └────────┘ │ │
│ └─────────────┘ │
│ │
└───────────────────┘
図 10 : ラムダ形式の変数
ポイントは、ラムダ形式が関数 times_element() 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。ラムダ形式はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義されたラムダ形式は、そのとき有効なローカル変数にアクセスすることができるのです。
もうひとつ簡単な例題を示しましょう。指定した文字 c が先頭にある文字列を、リストから削除する関数を作ってみましょう。最初に実行例を示します。
>>> remove_string('a', ['abc', 'def', 'agh', 'ijk'])
['def', 'ijk']
リストに格納された文字列の中で、a から始まる文字列を削除します。この処理は filter() とラムダ形式を使うと簡単に定義できます。
リスト 17 : 先頭文字が c の文字列を削除
def remove_string(c, ls):
return list(filter(lambda x: c != x[0], ls))
ラムダ形式の中で remove_string() の引数 c をアクセスできるので、このような定義が可能になります。繰り返しを使うと、リスト 18 のようなプログラムになります。
リスト 18 : 先頭文字が c の文字列を削除
def remove_string(c, ls):
result = []
for x in ls:
if c != x[0]:
result.append(x)
return result
繰り返しを使う場合、リストを操作するプログラムを書く必要があります。ラムダ形式と高階関数をうまく組み合わせると、複雑な処理でも簡単にプログラムを作ることができます。
Python は関数の中で別の関数を定義することができます。つまり、関数のネスト (入れ子) ができるわけです。入れ子の関数は局所的な関数として扱われるので、定義された関数の中でのみ有効です。他の関数から呼び出すことはできません。
また、入れ子の関数は、ラムダ形式のように定義された関数のローカル変数にアクセスすることができます。Pascal というプログラミング言語をご存知の方には、お馴染みの機能だと思います。
関数を引数として渡す場合、簡単な処理ならばラムダ形式を使うことができますが、Python のラムダ形式は式を一つしか定義できません。複雑な処理を行いたい場合は、入れ子の関数を使うと便利です。
簡単な例として、入れ子の関数を使ってリスト 16 の times_element() を書き直してみましょう。リスト 19 を見てください。
リスト 19 : リストの要素を n 倍する
def times_element(n, ls):
def timesN(x):
return n * x
return list(map(timesN, ls))
入れ子関数の定義は今までの関数定義と同じで、特別なことはありません。関数定義の中で、別の関数が定義されているだけです。関数 timesN() は times_element() 内で定義されているので、timesN() から times_element() の引数 n を参照することができます。
なお、入れ子の関数から外側の関数のローカル変数を書き換えたい場合は nonlocal 宣言を使います。Python の場合、変数への代入が行われると、その変数はローカル変数として扱われます。入れ子の関数で代入を行うと、その変数は入れ子の関数のローカル変数として扱われるため、外側の関数のローカル変数を隠してしまいます。値を書き換えたい場合は入れ子の関数で nonlocal 宣言してください。
最後に、関数型言語で用いられているテクニックを紹介しましょう。Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。クロージャは評価する関数と参照可能なローカル変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能なローカル変数を保存するところが異なります。参照可能なローカル変数の集合を「環境」と呼ぶことがあります。
Python でクロージャを生成するには「ラムダ形式」を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、ラムダ形式を使うと次のようになります。
>>> def foo(n): ... return lambda x: n * x ... >>> foo10 = foo(10) >>> foo10(100) 1000 >>> foo5 = foo(5) >>> foo5(11) 55
関数 foo() は引数を n 倍する関数を生成します。変数 foo10 に foo(10) の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo(5) の返り値をセットすると、foo5 は引数を 5 倍する関数になります。
ラムダ形式で関数を生成するとき、評価する関数のほかに、そのとき参照可能なローカル変数、つまり「環境」もいっしょに保存されます。この場合、参照可能なローカル変数は foo() の引数 n です。そして、クロージャを実行するときは、保存されているローカル変数を参照することができるのです。
foo(10) を実行して無名関数を生成するとき、定義されているローカル変数は n で、その値は 10 です。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo(5) を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 5 倍した結果を返すのです。
また、局所的な関数を定義して、その関数を返してもクロージャを生成することができます。リスト 20 を見てください。
リスト 20 : カリー化関数
def mapcar(func):
def _mapcar(ls):
result = []
for x in ls:
result.append(func(x))
return result
return _mapcar
リスト 20 は関数 mapcar() を 1 引数の関数に直したものです。mapcar() は関数 func() を受け取り、その func() を呼び出してリストを操作する関数を返します。これでもマッピングの動作ができるのです。簡単な例を示しましょう。
>>> f = mapcar(lambda x: x * x) >>> f([1, 2, 3, 4]) [1, 4, 9, 16] >>> mapcar(lambda x: x * x)([1, 2, 3, 4]) [1, 4, 9, 16]
最初の例は mapcar() で生成した関数を変数 f にセットし、それから f を関数呼び出しします。次の例は、mapcar() の返り値を直接関数呼び出ししています。カッコが多くなりますが、2 引数の mapcar() と同じように呼び出すことができます。これでもリストの要素を 2 乗することができます。
2 番目の例は、最初の引数を受け取って新しい関数を生成して返し、その関数に次の引数を適用して値を求めるという動作になります。このように、関数の引数がひとつでも「関数を返す関数」を使うことで、複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。
関数型言語には、カリー化関数をサポートしているプログラミング言語、たとえば Haskell や ML (SML/NJ, Ocaml) などがあります。これらのプログラミング言語では、高階関数はカリー化関数として定義されています。また、関数を合成して新しい関数を作ることも簡単にできます。
クロージャを使うことで Python でも関数型言語の機能を実現することは可能です。実際、そのようなモジュールも存在します。クロージャはとても強力な機能ですが、関数型言語に馴染みのない方にはちょっと難しいかもしれません。Python は手続き型言語なのでクロージャを使う機会は少ないと思いますが、高階関数や入れ子の関数は便利な機能なのでぜひ使ってみてください。
Python はカリー化関数をサポートしていませんが、モジュール functools の関数 partial() を使うと、関数の「部分適用」を行うことができます。関数の部分適用とは、指定した引数に値を設定して、残りの引数を受け取る関数を生成することです。簡単な例を示しましょう。
>>> import functools >>> f = functools.partial(mapcar, lambda x: x * x) >>> f([1, 2, 3, 4]) [1, 4, 9, 16]
mapcar() はカリー化していないリスト 13 のものです。このように、通常の関数でも partial() を用いることでカリー化関数のような処理を行うことができます。部分適用に興味のある方は functools のマニュアルをお読みください。
再帰定義と高階関数について説明しました。筆者は関数型言語 (Lisp や ML など) に興味があります。M.Hiroi の趣味でクロージャまで説明しましたが、関数型言語の機能をここまでサポートしている Python には大変驚きました。Python で関数プログラミングを試してみるのも面白いと思います。興味のある方は挑戦してみてください。
次回は Python の強力な文字列処理機能である正規表現とジェネレータについて説明します。