Pythonで末尾再帰する

2013-06-08 19:16

再帰っていいよね。なんか楽だ。

楽なんだけど、メモリとか時間とか食うのよね。そこで末尾再帰・・・なんだけど、末尾再帰で書いても最適化されないんだよね、python。

それならば、と最適化するのをデコレータで実装しちゃった人が居るらしい。メタプログラミングってやつだね。すごい。

New Tail Recursion Decorator (Python recipe) - ActiveState Code
Pythonのクロージャで末尾再帰最適化をする。 - tanihitoの日記

だんだん綺麗になってくのがいいっすね、素敵。

でもさ、まだ行けると思うんだ。という訳で、更に手を入れてみました。

def tail_recursive(func):
	from functools import wraps

	@wraps(func)
	def _tail(*args, **kwd):
		_tail.__args = args
		_tail.__kwd = kwd

		if _tail.__firstcall:
			_tail.__firstcall = False

			result = func
			try:
				while result is func:
					result = func(*_tail.__args, **_tail.__kwd)
			finally:
				_tail.__firstcall = True

			return result
		else:
			return func
	_tail.__firstcall = True

	return _tail

関数のメンバ変数なんて変なものを使っているから、これはこれでなんか微妙だけどね。ま、それでもかなりシンプルになっている、はず。

ちなみに、これを使ってもほとんど速度は向上しません。ま、関数呼び出しの回数は変わってないどころか増えてるから、仕方ないね。

メモリ消費量は減る、かな？

そんな事より大事なのは、再帰回数の制限を超えられること。何千回回そうとも止まらずに動いてくれる。素晴らしい。

言語仕様そのものに組み込まれたりすると、処理速度も向上したりするんだろうけれどねー。どうっすか、偉い人？