こちらの記事の続きです。
Pythonで末尾再帰的な何か
末尾再帰最適化ではありませんが。
再帰関数の中で、自分自身を呼び出すのに、self(引数) で呼び出せるようにする方法を考えてみました。
(Javascriptや、ActionScriptにおける arguments.callee的な。)
今回はデコレータを使いますー
Pythonにおける関数名は、あくまで参照として保持されています。
たとえば、こんな再帰関数を書いたとして、
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)
実行結果
f(5)= 15 # 1+2+3+4+5 g(5)= 120 # 1*2*3*4*5
さて、ここで、
f2=f f=g
としてしまうと、おかしな答えが返ってきます *1
f2(5)= 29
で、これを回避する方法はいろいろあると思うのですが、ふと、変な方法を思いついたのでメモ。
*1
修正しました
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)
自分自身を呼び出すのに 「self(～)」 を使えるようにしてみました。
例外を投げて、大域脱出してるだけですけれども。オマケで、再帰の深さを気にしなくてもよくなってるかも。
例外を投げてる関係で、実行速度は微妙に犠牲になってるんじゃないかと思います。（測ってません）
実行例
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)
実行結果
>>> f(10) 55
バグの温床になりそうな気がするし、それほど使い道が無いと思います、、、が、ちょっと面白かったのでメモしてみました。
- ググる:Yコンビネータ
selfで関数への参照を渡す代わりに、lambdaで書かれた関数自身を渡しちゃう、というもの。ややこしや。
余談
いっそのこと、クラスのメソッドとして書けばいいじゃない、って気がしてきました。
（普通はwhile文使えば充分という気も）
呼び出し側 (caller)を調べるには、スタックを調べればいいと思うのですが、、、、 というわけで、tracebackモジュールを今度調べてみるかも。 (時間のあるときに)
余談２
自分自身というものを、名前や職業、年齢、性別などによらず、鼻の先を指差すのでもなく指し示し説明せよ、などと、形而上学的なことを言われると、結構こまります、よね？ （でもない？）
関数の中から、その関数自身を指し示すのに、ワンクッションおいて、別の関数を使ってやる、ってのは、なんだかコンピュータプログラムのくせに、人間臭い気がします。 （変
（使う必要は必ずしも無いのですけれども）
Related posts
タグ: Python