差分
末尾再帰
,末尾再帰(まつびさいき、tail recursive)とは、[[再帰]]のうち、[[関数]]の末尾にのみ[[再帰]]を記述する[[プログラミング]]のテクニックである。
そんな小難しく面倒なことをして何が嬉しいかというと、賢い[[コンパイラ]]だと、[[最適化]]時に末尾再帰を検出すると、自動的に[[再帰]]ではなくしてくれる。これを[[末尾再帰最適化]]という。
<!--
[[C Sharp|C#]]での例。
なお、[[C Sharp|C#]]では、マイクロソフト製のコンパイラで、ターゲットにx64を指定し、かつReleaseビルド(最適化を有効にした状態でビルド)を行った場合のみ末尾再帰最適化が行われる。Monoのコンパイラ(msc)でどうなるかは未調査。
<source lang="csharp">
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);
}
}
</source>
-->
== 末尾再帰の例としてよく上がる処理 ==
* [[フィボナッチ数]]
* [[階乗]]
== 関連項目 ==
* [[末尾再帰最適化]]
* [[真正末尾再帰]]
* [[再帰]]
== 参考文献 ==
<references/>
== 外部リンク ==
{{stub}}
そんな小難しく面倒なことをして何が嬉しいかというと、賢い[[コンパイラ]]だと、[[最適化]]時に末尾再帰を検出すると、自動的に[[再帰]]ではなくしてくれる。これを[[末尾再帰最適化]]という。
<!--
[[C Sharp|C#]]での例。
なお、[[C Sharp|C#]]では、マイクロソフト製のコンパイラで、ターゲットにx64を指定し、かつReleaseビルド(最適化を有効にした状態でビルド)を行った場合のみ末尾再帰最適化が行われる。Monoのコンパイラ(msc)でどうなるかは未調査。
<source lang="csharp">
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);
}
}
</source>
-->
== 末尾再帰の例としてよく上がる処理 ==
* [[フィボナッチ数]]
* [[階乗]]
== 関連項目 ==
* [[末尾再帰最適化]]
* [[真正末尾再帰]]
* [[再帰]]
== 参考文献 ==
<references/>
== 外部リンク ==
{{stub}}