質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Q&A

解決済

再帰を用いる際の注意点

uer03108
uer03108

総合スコア192

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

5回答

0グッド

0クリップ

14085閲覧

投稿2016/09/10 04:57

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

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

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答5

4

ベストアンサー

通常、再帰関数を使った場合、関数の呼び出しの度にスタックが消費され、あまりにも深くなるとスタックオーバーフローでプログラムが停止します。確保されているスタックの大きさや、関数の引数等によりますが、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

raccy

総合スコア21689

ykcz, iwamoto_takaaki, mit0223, randr👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

1

まず大前提として、本当にそれだけの再帰が必要なのか、アルゴリズムを考えなおしたほうがいいかもしれません。

探索系だと、再帰で深いレベルへ突き進むより、

  • これからやるべきタスクを保管するスタック or キューを作る
  • 1タスクを消化するときに、次にやるべきタスクをそのスタック or キューに積み込む
  • 空になるまでスタック or キューから取り出し続ける

というような流れでやるのが適切です(この方法だと、マシン自体のスタックはほぼ消費しません)。

投稿2016/09/10 09:17

maisumakun

総合スコア141456

KoichiSugiyama👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

uer03108

2016/09/11 14:00

回答有難うございます。 仰る方法でやると上手くいきました。 例えば、ツリー作成で再起を用いる場合は、ツリー全体がメモリに格納されるので、オーバーフローしやすいと言うことですね。

0

具体的な状況に依存します。

皆さんの仰る通り、たとえばHaskellの場合は代替え案が存在しません。C言語の場合は関数のコールスタック確保のオーバーヘッドだけでメモリを圧迫します(厳密にいうならば言語仕様ではありませんが)。

使用する条件化において代替え案と比較し、可能であれば利点と欠点を数値化して定量比較するなりしないと答えは出ないと思います。

投稿2016/09/10 14:35

HogeAnimalLover

総合スコア4823

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

0

質問者さんの考え方は間違っていないと思います。

LISP系の言語は再帰を多用するらしいですが、他のたいていの言語では再帰処理はループに翻訳できて、パフォーマンスも再帰処理よりループの方がよくなる傾向があるようです(簡単に思いつくのは、再帰は都度関数を呼び出すコストが必要なのに対して、ループはそれがないという点です)。

再帰の考え方は知っておいた方が良いと思いますが、実務でそのまま再帰処理として実装せずに可能な限りループで実現することを考えられた方が良いと思います。

投稿2016/09/10 12:32

KoichiSugiyama

総合スコア3036

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

0

プログラムを組むというのは、その、もどかしい、の連続です。

COBOLで内部ループがなかった時代、
2次元配列の0セットに2つ呼び出し命令を書かなければならないこともありました。

時間についても、テストでは少量のデータしか使わないのであまり考えていないのですが、
本番の夜間バッチで動かしたら2時間かかったなんて翌日聞かされ、
1行いじったら1分で終わることがありました。

テスト環境についてもデータが既に入っている環境でテストして問題ないとして
本番環境に持って行った時、データが入っていなかった。。。
結果、オンラインをすべて止めて15万行のログを吐いて異常終了することがありました。

投稿2016/09/10 05:09

maiko0318

総合スコア874

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

uer03108

2016/09/11 13:55

回答有難うございます。 内部ループの無い時代があったんですね。今だと考えられません。 テストケースを考えるのは、経験がものを言いそうですね。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

同じタグがついた質問を見る

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。