「末尾再帰最適化」の版間の差分
imported>GamerBook (→C#) |
|||
(3人の利用者による、間の6版が非表示) | |||
1行目: | 1行目: | ||
'''末尾再帰最適化'''(まつびさいきさいてきか)とは、賢い[[コンパイラ]]が[[末尾再帰]]を検出すると、[[最適化]]時に[[再帰]]を展開し、消し去ってくれる機能のことである。 | '''末尾再帰最適化'''(まつびさいきさいてきか)とは、賢い[[コンパイラ]]が[[末尾再帰]]を検出すると、[[最適化]]時に[[再帰]]を展開し、消し去ってくれる機能のことである。 | ||
− | [[ | + | == 概要 == |
+ | [[末尾呼び出し最適化]]([[Tail Call Optimization]]、[[TCO]])の一種で、[[再帰]]だとその効果が絶大だという話であり、やっていることは同じである。 | ||
− | + | [[末尾再帰]]([[末尾呼び出し]])であれば後に続く処理はないので、その関数内で使われている変数などは破棄でき(末尾呼び出しされる関数の引数は除く)、途中経過を保持する[[変数]]を用意することで、[[プログラマー]]が手で書くとボロクソに言われる[[goto文]]や[[アセンブリ言語]]のjmp命令などを用いて[[再帰]](関数呼び出し)を無くす(展開する)ことができる。 | |
− | + | 末尾再帰最適化はこの[[末尾再帰]]([[末尾呼び出し]])の特性を利用し、[[再帰]](関数呼び出し)は[[リソース]]馬鹿食いで[[スタックオーバーフロー]]の危険性があり、何よりクソ重い、かといって[[プログラマー]]が手動で[[再帰]](関数)を展開しておくと9割方[[ソースコード]]がクソ読みにくくなり、[[偉いプログラマー]]にボロクソ言われる、という問題を[[ソースコード]]の書き方を気を付けておくことで[[コンパイラ]]が[[最適化]]時に半自動で解決してくれる優れものである。 | |
+ | |||
+ | == 末尾再帰最適化に対応した主なプログラミング言語 == | ||
+ | [[末尾再帰最適化]]([[末尾呼び出し最適化]])が行われるかは[[コンパイラ]]の気分次第であり、どうなるかわからない諸刃の剣。実際に末尾呼び出し最適化をサポートしている[[コンパイラ]]であっても100%発動するとは限らない場合もあるので過信しすぎには注意する必要がある。 | ||
+ | |||
+ | === C# === | ||
+ | [[C Sharp|C#]]では、[[マイクロソフト]]製の[[コンパイラ]]で、ターゲットが[[x64]]、かつリリースビルド(最適化が有効な状態)でのみ末尾再帰最適化が行われる。つまりデフォルトで最適化が無効となっているデバッグビルド時には末尾最適化が行われないという。 | ||
+ | |||
+ | [[Mono]]での結果については未調査。 | ||
+ | |||
+ | === Python === | ||
+ | [[Python]]ではPython 2.4から導入された[[デコレーター]]を用いて[[メタプログラミング]]を実現した人がおり<ref>http://d.hatena.ne.jp/wasabiz/20110118/1295335821</ref>、それを使えば[[関数]]の頭に「@tail_recursive」と書くことで末尾再帰最適化を明示することができる。 | ||
+ | なお、同様ものを[[クラス]]ではなく[[クロージャー]]で書き直した人もいる<ref>http://d.hatena.ne.jp/tanihito/20110119/1295459297</ref>。 | ||
+ | |||
+ | [[階乗]](factorial)の記述例。 | ||
+ | <source lang="python"> | ||
+ | @tail_recursive | ||
+ | def fact(n, acc = 1): | ||
+ | return acc if n == 0 else fact(n - 1, n * acc) | ||
+ | </source> | ||
+ | |||
+ | [[フィボナッチ数]](fibonacci)の記述例。 | ||
+ | <source lang="python"> | ||
+ | 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) | ||
+ | </source> | ||
== 関連項目 == | == 関連項目 == | ||
+ | * [[再帰]] | ||
* [[末尾再帰]] | * [[末尾再帰]] | ||
− | |||
* [[最適化]] | * [[最適化]] | ||
+ | * [[末尾呼び出し最適化]] | ||
== 参考文献 == | == 参考文献 == |
2012年12月6日 (木) 04:40時点における最新版
末尾再帰最適化(まつびさいきさいてきか)とは、賢いコンパイラが末尾再帰を検出すると、最適化時に再帰を展開し、消し去ってくれる機能のことである。
概要[編集 | ソースを編集]
末尾呼び出し最適化(Tail Call Optimization、TCO)の一種で、再帰だとその効果が絶大だという話であり、やっていることは同じである。
末尾再帰(末尾呼び出し)であれば後に続く処理はないので、その関数内で使われている変数などは破棄でき(末尾呼び出しされる関数の引数は除く)、途中経過を保持する変数を用意することで、プログラマーが手で書くとボロクソに言われるgoto文やアセンブリ言語のjmp命令などを用いて再帰(関数呼び出し)を無くす(展開する)ことができる。
末尾再帰最適化はこの末尾再帰(末尾呼び出し)の特性を利用し、再帰(関数呼び出し)はリソース馬鹿食いでスタックオーバーフローの危険性があり、何よりクソ重い、かといってプログラマーが手動で再帰(関数)を展開しておくと9割方ソースコードがクソ読みにくくなり、偉いプログラマーにボロクソ言われる、という問題をソースコードの書き方を気を付けておくことでコンパイラが最適化時に半自動で解決してくれる優れものである。
末尾再帰最適化に対応した主なプログラミング言語[編集 | ソースを編集]
末尾再帰最適化(末尾呼び出し最適化)が行われるかはコンパイラの気分次第であり、どうなるかわからない諸刃の剣。実際に末尾呼び出し最適化をサポートしているコンパイラであっても100%発動するとは限らない場合もあるので過信しすぎには注意する必要がある。
C#[編集 | ソースを編集]
C#では、マイクロソフト製のコンパイラで、ターゲットがx64、かつリリースビルド(最適化が有効な状態)でのみ末尾再帰最適化が行われる。つまりデフォルトで最適化が無効となっているデバッグビルド時には末尾最適化が行われないという。
Monoでの結果については未調査。
Python[編集 | ソースを編集]
PythonではPython 2.4から導入されたデコレーターを用いてメタプログラミングを実現した人がおり[1]、それを使えば関数の頭に「@tail_recursive」と書くことで末尾再帰最適化を明示することができる。 なお、同様ものをクラスではなくクロージャーで書き直した人もいる[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)