末尾再帰最適化

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

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

末尾再帰であれば後に続く処理はないので、途中経過を保持する変数と、プログラマーが手で書くとボロクソに言われるgoto文やアセンブリ言語のjmp命令などを用いて、再帰を無くす（展開する）ことができる。

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

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

末尾再帰最適化が行われるかはコンパイラの気分次第であり、どうなるかわからない諸刃の剣。

C#

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

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

Python

PythonではPython 2.4から導入されたデコレーターを用いてメタプログラミングを実現した人がおり、それを使えば関数の頭に「@tail_recursive」と書くことで末尾再帰最適化を明示することができる。 なお、同じくものをクラスではなくクロージャーで書き直した人もいる。

階乗（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)

関連項目

• 再帰
• 末尾再帰
• 最適化
• 末尾呼び出し最適化