末尾再帰最適化

提供: MonoBook
移動: 案内検索

末尾再帰最適化(まつびさいきさいてきか)とは、賢いコンパイラ末尾再帰を検出すると、最適化時に再帰を展開し、消し去ってくれる機能のことである。

概要[編集]

末尾呼び出し最適化Tail Call OptimizationTCO)の一種で、再帰だとその効果が絶大だという話であり、やっていることは同じである。

末尾再帰末尾呼び出し)であれば後に続く処理はないので、その関数内で使われている変数などは破棄でき(末尾呼び出しされる関数の引数は除く)、途中経過を保持する変数を用意することで、プログラマーが手で書くとボロクソに言われるgoto文アセンブリ言語のjmp命令などを用いて再帰(関数呼び出し)を無くす(展開する)ことができる。

末尾再帰最適化はこの末尾再帰末尾呼び出し)の特性を利用し、再帰(関数呼び出し)はリソース馬鹿食いでスタックオーバーフローの危険性があり、何よりクソ重い、かといってプログラマーが手動で再帰(関数)を展開しておくと9割方ソースコードがクソ読みにくくなり、偉いプログラマーにボロクソ言われる、という問題をソースコードの書き方を気を付けておくことでコンパイラ最適化時に半自動で解決してくれる優れものである。

末尾再帰最適化に対応した主なプログラミング言語[編集]

末尾再帰最適化末尾呼び出し最適化)が行われるかはコンパイラの気分次第であり、どうなるかわからない諸刃の剣。実際に末尾呼び出し最適化をサポートしているコンパイラであっても100%発動するとは限らない場合もあるので過信しすぎには注意する必要がある。

C#[編集]

C#では、マイクロソフト製のコンパイラで、ターゲットがx64、かつリリースビルド(最適化が有効な状態)でのみ末尾再帰最適化が行われる。つまりデフォルトで最適化が無効となっているデバッグビルド時には末尾最適化が行われないという。

Monoでの結果については未調査。

Python[編集]

PythonではPython 2.4から導入されたデコレーターを用いてメタプログラミングを実現した人がおり[1]、それを使えば関数[email protected][email protected]ことができる。 なお、同様ものをクラスではなくクロージャーで書き直した人もいる[2]

階乗(factorial)の記述例。

@tail_recursive 
def fact(n, acc = 1):
    return acc if n == 0 else fact(n - 1, n * acc)

フィボナッチ数(fibonacci)の記述例。

def fib(n):
    @tail_recursive
    def fib_iter(a, b, m):
        return a if m == 0 else fib_iter(b, a + b, m - 1)
    return fib_iter(0, 1, n)

関連項目[編集]

参考文献[編集]

  1. http://d.hatena.ne.jp/wasabiz/20110118/1295335821
  2. http://d.hatena.ne.jp/tanihito/20110119/1295459297

外部リンク[編集]