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

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

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

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

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

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

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