「末尾再帰」の版間の差分
ナビゲーションに移動
検索に移動
imported>GamerBook 細 |
imported>Administrator |
||
1行目: | 1行目: | ||
− | + | '''末尾再帰'''(読み:まつびさいき、[[英語]]:tail recursive)とは、[[再帰]]のうち、[[関数]]の末尾にのみ[[再帰]]を記述する[[プログラミング]]のテクニックである。 | |
+ | |||
+ | == 概要 == | ||
+ | 末尾再帰は再帰呼び出しが関数の末尾にのみ登場することをいう。 | ||
そんな小難しくて面倒なことをして何が嬉しいかというと、賢い[[コンパイラ]]だと[[最適化]]時に末尾再帰を検出すると自動的に[[再帰]]を[[再帰]]ではなく展開してくれる。これを[[末尾再帰最適化]]といい、[[スタック]]を食いつぶすなどの[[再帰]]のデメリットを[[プログラマ]]と[[コンパイラ]]の[[コラボレーション]]で解決してくれる。 | そんな小難しくて面倒なことをして何が嬉しいかというと、賢い[[コンパイラ]]だと[[最適化]]時に末尾再帰を検出すると自動的に[[再帰]]を[[再帰]]ではなく展開してくれる。これを[[末尾再帰最適化]]といい、[[スタック]]を食いつぶすなどの[[再帰]]のデメリットを[[プログラマ]]と[[コンパイラ]]の[[コラボレーション]]で解決してくれる。 | ||
− | + | === 例 === | |
− | [[C Sharp|C#]] | + | [[C Sharp|C#]]での例。なお、[[C Sharp|C#]]では「マイクロソフト製のコンパイラ」で、「ターゲットをx64を指定」し、かつ「Releaseビルド(最適化を有効にした状態でビルド)」を行った場合のみ[[末尾再帰最適化]]が行われる。[[Mono]]のコンパイラ(msc)でどうなるかは未調査。 |
− | |||
<source lang="csharp"> | <source lang="csharp"> | ||
class TailRecursive | class TailRecursive | ||
25行目: | 27行目: | ||
} | } | ||
</source> | </source> | ||
− | |||
== 末尾再帰の例としてよく上がる処理 == | == 末尾再帰の例としてよく上がる処理 == | ||
38行目: | 39行目: | ||
== 参考文献 == | == 参考文献 == | ||
− | + | {{reflist}} | |
− | |||
− | |||
{{stub}} | {{stub}} |
2016年3月2日 (水) 04:49時点における版
末尾再帰(読み:まつびさいき、英語:tail recursive)とは、再帰のうち、関数の末尾にのみ再帰を記述するプログラミングのテクニックである。
概要
末尾再帰は再帰呼び出しが関数の末尾にのみ登場することをいう。
そんな小難しくて面倒なことをして何が嬉しいかというと、賢いコンパイラだと最適化時に末尾再帰を検出すると自動的に再帰を再帰ではなく展開してくれる。これを末尾再帰最適化といい、スタックを食いつぶすなどの再帰のデメリットをプログラマとコンパイラのコラボレーションで解決してくれる。
例
C#での例。なお、C#では「マイクロソフト製のコンパイラ」で、「ターゲットをx64を指定」し、かつ「Releaseビルド(最適化を有効にした状態でビルド)」を行った場合のみ末尾再帰最適化が行われる。Monoのコンパイラ(msc)でどうなるかは未調査。
class TailRecursive
{
public int Sum(int n)
{
return SumTailRecursive(n, 0);
}
private int SumTailRecursive(int n, int a)
{
if (n < 1)
{
return a;
}
// 末尾(関数内で最後に出現するreturn文)
return SumTailRecursive(n - 1, a + n);
}
}
末尾再帰の例としてよく上がる処理
末尾再帰の記述例は以下を参照。