やりたいこと
「再帰関数の再帰呼び出しが一定数になったら終了」したい。
例えば、呼び出し回数が500回になったら、そこで処理を終了するみたいな、
この記事では
とする。
ただし。たらいまわし関数は以下のような関数で、大した処理をしないのに再帰呼び出しをめちゃめちゃ行うのでプログラミング言語処理系のベンチマークとして使われたりするらしい。
Pythonで書くとこんな感じ。
1
2
3
4
5
6
7
| def tarai(x, y, z):
if x <= y:
return y
else:
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y))
|
わかりやすいようにtarai(10, 5, 0)と引数を固定して呼び出す。期待される再帰呼び出し回数は343073回である。
実装1_globalに持つ
竹内関数の再帰回数の求め方
ここで回答されている一番かんたんなやり方。再帰関数の外部に回数をカウントする変数を持っておいて、それを再帰関数内で使用する。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # globalにおいてやる
count = 0
def tarai(x, y, z):
global count
count += 1
if x <= y:
return y
else:
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y))
tarai(10, 5, 0)
print(count)
|
実装自体はかんたんだが、global変数を使うのは気が向かない。使用用途がたらいまわし関数の再帰呼び出し回数を数えるだけなのだから、スコープをもっと狭くしないと、予期せぬcountの使い方をされかねない。
実装2_クロージャ
次はたらいまわし関数を別の関数の中に定義するやり方をする。これでcountは、global1ではなくnonlocalとなりスコープもcount_taraiで制限されるようになった。countの初期化も必ず実行されるし、外部から見えないのでずいぶんよくなった。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| def count_tarai(x, y, z) -> int:
count = 0
def tarai(x, y, z):
nonlocal count
count += 1
if x <= y:
return y
else:
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y))
tarai(x, y, z)
return count
print(count_tarai(10, 5, 0))
|
実装3_クロージャ+class
実装2でとりあえずよいが、もう少し色々試してみる。
今は再帰呼び出し回数だけを求めているが、引数zが0になった回数やx=yとなった回数もほしいとなるとかなりきもい実装になる。状態をclassに切り出した実装を書いてみた。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Count(object):
def __init__(self):
self.added = 0
def addCount(self):
self.added += 1
def count_tarai(x, y, z) -> int:
c = Count()
def tarai(x, y, z):
nonlocal c
c.addCount()
if x <= y:
return y
else:
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y))
tarai(x, y, z)
return c.added
print(count_tarai(10, 5, 0))
|
これで保持する変数が増えても扱いやすくる気がする。
実装4_クロージャ+callable
なんかもうここまでする意味がわからないが、Pythonのクラスの特殊メソッド__call__を使用して簡略化する。__call__を定義することで、クラスのインスタンスを関数のように呼び出すことができる。つまりc.addCount()とメソッドを呼ばなくても、c()だけでよい。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Count(object):
def __init__(self):
self.added = 0
def __call__(self):
self.added += 1
def count_tarai(x, y, z) -> int:
c = Count()
def tarai(x, y, z):
nonlocal c
c()
if x <= y:
return y
else:
return tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y))
tarai(x, y, z)
return c.added
print(count_tarai(10, 5, 0))
|
結論
特殊メソッド__call__ は、状態を保持したい関数の代わりに実装すると便利。
参考↓
Effective Python――Pythonプログラムを改良する59項目
