再帰を用いる際の注意点

予め、再帰の回数が膨大になる（10万以上とか？）と分かっている場合は、while文などで代用した方が無難なのでしょうか。
割と簡単にオーバーフローするイメージがありますが。

しかし、代用したらしたでコードが煩雑になるし、処理時間もかかってしまうのでもどかしい感じもします。

行動規範の内容に同意します

回答5件

ベストアンサー

通常、再帰関数を使った場合、関数の呼び出しの度にスタックが消費され、あまりにも深くなるとスタックオーバーフローでプログラムが停止します。確保されているスタックの大きさや、関数の引数等によりますが、10万以上となるとかなりきついでしょう。では、そういうときはループに書き換えれば…と安易に考える前に、再帰関数でもスタックが消費されない場合があると言うことに留意すべきです。

###末尾再帰
参考: 末尾再帰 - Wikipedia

末尾再帰が単純なループに機械的に置き換えられることが知られています。もし、末尾再帰になっているとき、自動的にループに変換してくれるのであれば、呼び出しの度にスタックは消費されず、スタックオーバーフローが発生する恐れが無くなります。これが末尾呼び出し最適化です。

C
1#include <inttypes.h>
2#include <stdint.h>
3#include <stdio.h>
4
5int64_t sum_r(int64_t a, int64_t b, int64_t r)
6{
7	if (a > b) return r;
8	return sum_r(a + 1, b, r + a);
9}
10
11int64_t sum(int64_t a, int64_t b)
12{
13	return sum_r(a, b, 0);
14}
15
16int main(void)
17{
18	int64_t x = sum(1, 1000000000);
19	printf("%" PRId64 "\n", x);
20	return 0;
21}

上のコードは一(1)から百万(1,000,000,000)を全て足すというものです。sum()と一緒にsum_r()というわかりやすい末尾再帰関数を作っています。このコードをgccで-O2付きでコンパイルし、実行した場合、スタックオーバーフローを起こすことなく実行できます。これは、コンパイル時に、再帰関数がループに変換され、スタックを消費しない形になるためです。最適化オプションを-O0に変更した場合は、SIGSEGVで落ちます。また、コンパイラによっては上記のような単純な末尾再帰意外にも、二つの関数を行き来するような複雑な再帰関数であっても、うまくループに変換してくれる場合もあります。

末尾再帰呼び出し最適化に対応しているかどうかは、言語およびコンパイラ・インタプリンタによって異なります。(言語の仕様や環境は常に変わってきており、リストに間違いあるかもしれません。間違いがある場合はコメント等でご指摘下さい)

【対応、または、部分的に対応】

C/C++: GCCとVisualC++共に最適化オプションがあります。適度に最適化を行うリリースビルドは問題ありませんが、デバッグビルドのために最適化無しにしている場合は有効にならない事に注意してください。どこまで対応するかも、コンパイラおよびバージョンによって異なります。
Scala: 対応しています。tailrecアノテーションでチェックまで可能なようです。
JavaScript: ECMAScript 2015から末尾再帰の最適化が言語仕様に追加されましたが、2016年9月10日現在、対応しているブラウザはほんのわずかのようです。
Ruby: CRubyのインタプリタエンジンに最適化の機能があるのですが、スタックトレースができなくなってしまうため、デフォルトでは無効になっています。使用するにはインタプリンタエンジンそのものを切り替える必要があり、少し面倒です。
Python: 言語やインタプリタの標準ではありませんが、デコレータを使って対応する方法があります。
C#: 64bit環境のみ対応しているようです。

【未対応】

Java: 対応していません。
PHP: 対応していません。
Go: 対応していません。

もし、末尾再帰呼び出し最適化に対応しているのであれば、最適化が行われるような形で再帰関数を作成しても問題ないと考えられます。ただ、末尾再帰の条件を正しく理解していないと、最適化がされない場合もよくあることです。ユニットテスト等で限界値テストを実施し、最適化の有無の確認は必須かと思います。

###関数型言語
主に関数型言語と称される言語(Haskell、F#、Eralng、Schemeなど)のほとんどは何らかの形で末尾再帰呼び出し最適化に対応しています。

そもそも、Haskellのような純粋関数型言語では、逆にループが存在しないため、再帰関数を使うしかありません。これらの言語では、最適化と遅延評価によって、だいたいうまく行くようになっています。ただ、foldlの例のように問題が起きる場合もありますので、末尾再帰だから大丈夫と言うことではありません。命令型言語とは違った見方で、再帰関数を注意して作る必要があります。

投稿2016/09/10 13:09