「末尾再帰」の版間の差分
Administrator (トーク | 投稿記録) |
Administrator (トーク | 投稿記録) |
||
(同じ利用者による、間の1版が非表示) | |||
1行目: | 1行目: | ||
'''末尾再帰'''(読み:まつびさいき、[[英語]]:tail recursive)とは、ある[[関数]]の最後の1行(return直前)に[[再帰]]を記述する[[プログラミング]]のテクニックである。 | '''末尾再帰'''(読み:まつびさいき、[[英語]]:tail recursive)とは、ある[[関数]]の最後の1行(return直前)に[[再帰]]を記述する[[プログラミング]]のテクニックである。 | ||
− | |||
− | |||
「関数の終わりの一行」ではなく「return直前の再帰処理」が末尾再帰である。ifとelseで分岐しても両方がreturnで終わるなら末尾再帰に該当する。 | 「関数の終わりの一行」ではなく「return直前の再帰処理」が末尾再帰である。ifとelseで分岐しても両方がreturnで終わるなら末尾再帰に該当する。 | ||
13行目: | 11行目: | ||
</source> | </source> | ||
+ | 賢い[[コンパイラ]]だと[[最適化]]の際にこの末尾再帰を検出すると自動的に「[[再帰]]を[[再帰]]ではない形式に展開」してくれる。これを[[末尾再帰最適化]]といい、[[スタック]]を食いつぶすなどの[[再帰]]のデメリットを[[プログラマ]]と[[コンパイラ]]の[[コラボレーション]]で解決することができる。 | ||
=== 例 === | === 例 === | ||
45行目: | 44行目: | ||
* [[真正末尾再帰]] | * [[真正末尾再帰]] | ||
* [[再帰]] | * [[再帰]] | ||
− | |||
− | |||
− | |||
− | |||
− |
2021年2月9日 (火) 07:41時点における最新版
末尾再帰(読み:まつびさいき、英語:tail recursive)とは、ある関数の最後の1行(return直前)に再帰を記述するプログラミングのテクニックである。
「関数の終わりの一行」ではなく「return直前の再帰処理」が末尾再帰である。ifとelseで分岐しても両方がreturnで終わるなら末尾再帰に該当する。
int func() {
if (x)
return recursive1();
else
return recursive2();
}
賢いコンパイラだと最適化の際にこの末尾再帰を検出すると自動的に「再帰を再帰ではない形式に展開」してくれる。これを末尾再帰最適化といい、スタックを食いつぶすなどの再帰のデメリットをプログラマとコンパイラのコラボレーションで解決することができる。
例編集
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);
}
}