Pythonで末尾再帰最適化

末尾再帰最適化

Pythonでは本来, 末尾再帰最適化は行われないのですが デコレータを使うことによって一発で末尾再帰化を行ってくれるようになります.

今日は，そんな末尾再帰最適化について紹介します.

末尾再帰

そもそも末尾再帰ってなんだろう ってことですが, 末尾再帰とはそのままでは 関数の末尾(関数の値を返す部分)が再帰呼出しとなるような関数 のことです 末尾再帰だと機械的に最適化しやすいので，このように呼ばれるわけです.

再帰はプログラムが簡潔にかけ，見た目には非常に良いのですが 関数の再帰的に呼び出すたびに，関数の呼び出し元情報を記録するスタックが積まれる, 処理的に効率が良くなかったりします.

例えば, 以下のようなn番目のフィボナッチ数列の値を求める関数は 再帰を利用した関数です.(末尾再帰ではありません；足し算を行っています)

def (n):
    return fib(n-2) + fib(n-1)
fib(100)

を書いた時, 以下のような例外が投げられます

RuntimeError: maximum recursion depth exceeded

再帰が深くなりすぎて，スタックが溢れて
このような例外が発生するわけです.

さてこれを末尾再帰な形に書き換えてみましょう

def fib(n, val=1):
    return fib(n-1, val + n) if n > 0 else val
fib(100)

結果を保存するようの変数valを設け, 再帰呼出しでそれを渡しています. ただし，これでも上記と同じ例外が投げられます.

関数の流れを自分で一回追ってみて欲しいのですが, この関数の形では, fib(n, val) → fib(n-1, val →… fib(1, val) という形で呼び出されるのですが

再帰を呼び出した時点で, 必要な計算(valに結果が含まれている)は全て終えているため その関数は再帰呼び出しした関数の値を返すだけ, というほぼ何もしない処理なんですね

展開してやると return (return (return (return val))) みたいな形になるわけです. 無駄ですね.

この無駄を無くすように(コンパイラ等で)最適化してやるのが末尾最適化です.

Decoratorによる末尾最適化

New Tail Recursion Decorator (Python recipe) Tail call optimization in Python Pythonのクロージャで末尾再帰最適化をする。

基本はこちらのレシピに乗っているとおりです

使い方:

末尾最適化してやりたい, 関数にDecoratorをつけるだけ

@tail_recursive
def fib(n, p, val=1):
    return fib(n-1, val, val + p) if n > 0 else val
fib(100) #>>> 573147844013817084101

仕組み解説:

デコレータによって関数中の再帰呼出しもラップされていることに 気をつければ後は簡単 func → wrapper → func →… という形で呼び出されることになります.

この時, wrapperは再帰的にfuncを呼ぶだすのではなく 再帰呼出しされた引数だけを, 記録してfuncを
新たに呼ぶことで再帰を避けています.

わかれば見事という他ないですね.

ただ書きなおしたほうが早い

結局のところ末尾再帰最適化の一番の方法は 以下のようにループで書きなおしてやることです

def fib(n):
    val, prev = 1, 1
    for _ in xrange(n-1):
        val, prev = val + prev, val
    else:  
        return val
fib(100) #>>> 573147844013817084101