Pythonで(変な)末尾再帰の書き方

[pukiwiki]
こちらの記事の続きです。
[[Pythonで末尾再帰的な何か:http://boxheadroom.com/2009/04/29/py_tro_lip_reading]]

末尾再帰”最適化”ではありませんが。
再帰関数の中で、自分自身を呼び出すのに、self(引数) で呼び出せるようにする方法を考えてみました。
(Javascriptや、ActionScriptにおける arguments.callee的な。)

[/pukiwiki]

[pukiwiki]

今回はデコレータを使いますー
-[[ググる:Python デコレータ]]

Pythonにおける関数名は、あくまで参照として保持されています。
たとえば、こんな再帰関数を書いたとして、
[/pukiwiki]

def f(x):
    u"1からxの総和"
    if x<=1:
        return 1
    else :
        return x+f(x-1)

def g(x):
    "1*2*3*... x"
    if x==1:
        return 1
    else :
        return x*g(x-1)

[pukiwiki]
実行結果
f(5)= 15 # 1+2+3+4+5
g(5)= 120 # 1*2*3*4*5

さて、ここで、
f2=f
f=g

としてしまうと、おかしな答えが返ってきます ((修正しました))

f2(5)= 29

で、これを回避する方法はいろいろあると思うのですが、ふと、変な方法を思いついたのでメモ。
[/pukiwiki]

class Self(Exception):
    pass

def self(*args,**kwargs):
    raise Self(args,kwargs)

def rec(callee):
    def _(*args,**kwargs):
        while True :
            try :
                return callee(*args,**kwargs)
            except Self,ret:
                args,kwargs=ret          
    return _

@rec
def f(x,y=0):
    #print x
    if x<=0:
        return y
    else :
        return self(x-1,y=y+x)

[pukiwiki]
自分自身を呼び出すのに 「self(~)」 を使えるようにしてみました。

例外を投げて、大域脱出してるだけですけれども。オマケで、再帰の深さを気にしなくてもよくなってるかも。

例外を投げてる関係で、実行速度は微妙に犠牲になってるんじゃないかと思います。(測ってません)

実行例
[/pukiwiki]

f(10)= 55

ただし、大きな難点がありまして

def f(x,y=0):
    if x<=1:
        return 1
    else :
        return x+self(x-1)

これは動きそうで動きません。やってみるまで、動かないことに気が付きませんでした。なんてこったい。

もうちょっと、シンプルなほうが使いやすいかも。ただし、こちらは、スタックを消費します。
(ホントは、こちらを先に思いつきました)

def rec(callee):
    def _(*args,**kwargs):
            return callee(_,*args,**kwargs)
    return _

@rec
def f(self,x):
    if x<=0:
        return 0
    else :
        return x+self(x-1)

[pukiwiki]
実行結果
>>> f(10)
55

バグの温床になりそうな気がするし、それほど使い道が無いと思います、、、が、ちょっと面白かったのでメモしてみました。

-[[ググる:Yコンビネータ]]
selfで関数への参照を渡す代わりに、lambdaで書かれた関数自身を渡しちゃう、というもの。ややこしや。
*余談
いっそのこと、クラスのメソッドとして書けばいいじゃない、って気がしてきました。
(普通はwhile文使えば充分という気も)
呼び出し側 (caller)を調べるには、スタックを調べればいいと思うのですが、、、、 というわけで、tracebackモジュールを今度調べてみるかも。 (時間のあるときに)

*余談2
自分自身というものを、名前や職業、年齢、性別などによらず、鼻の先を指差すのでもなく指し示し説明せよ、などと、形而上学的なことを言われると、結構こまります、よね? (でもない?)

関数の中から、その関数自身を指し示すのに、ワンクッションおいて、別の関数を使ってやる、ってのは、なんだかコンピュータプログラムのくせに、人間臭い気がします。 (変

(使う必要は必ずしも無いのですけれども)

[[http://ecx.images-amazon.com/images/I/51P0V0KVC3L._SL160_.jpg:http://www.amazon.co.jp/exec/obidos/ASIN/4101206317/tamac-22/ref=nosim/]]
[/pukiwiki]

コメントを残す

メールアドレスが公開されることはありません。