C言語 再帰処理のメリットとデメリット

質問

最近、C言語の関数にも再帰定義ができるということを初めて知りました。
そこで聞きたいのですが、再帰処理のメリット・デメリットは何でしょうか？
思いついたものとしては

メリット … 簡単に表記できる
デメリット … 無限ループが発生する可能性あり

でしょうか。
また、全計算が終わるまでに、途中の演算結果を保持しなければならないので、
メモリを無駄遣いしそうな気もします。

回答No.2

chirubou · ベストアンサー

「メリット … 簡単に表記できる」

これはケースバイケースなのではないでしょうか。例えば配列の要素の和を求めるなんてのは、普通にループで書いた方が簡単です。一方、フィボナッチ数列を求めるなんてのは（教科書的な例で恐縮です。私が書いた中では、ある種の文法解析）再帰で書いた方が簡単でキレイですよね。

「デメリット … 無限ループが発生する可能性」

これは単に、繰り返しの終了条件の書き方の問題ではないでしょうか。普通の for などのループでも終了条件を間違えれば、同じだと思います。ただ再帰処理だと、終了条件が普通の if 文だったりするので、見た目が少し分かり難いという程度でしょう。

一部のプログラミング言語、例えば lisp とか prolog、では再帰処理をコンパイラが普通にループの繰り返しに変換して処理速度を上げています（ただし可能な場合のみ、全ての再帰処理をループに変換できない）。まあ prolog だと for のような繰り返しがなかったりする、という事情もあるのですが。

しかし、C ではそれをやらない約束になっているようです。ということで、再帰処理だとスタックが繰り返しの回数に比例して延びてしまいますので、無限ループは書く事ができませんし、繰り返し回数が多いとスタックが溢れたりします。もちろん、for などの普通の繰り返しの方が、再帰呼び出しよりも速いです（だから一部の言語では再帰をループに変換する）。

ということで、デメリットとしては、「遅い、メモリを喰う」という事になるかと思います。

No.1 さんのご回答にあるように、スレッドを細かい粒度にして並列度を上げるために、ループの繰り返しの単位で並列に処理しようとする、つまり、再帰呼び出しの関数レベルでスレッドにしたくなる気持ちは分かりますし、そういう研究は昔から多くあります。

しかしながら、実際問題、こうして並列度を上げてもなかなか速くならないようです。それよりも大きな配列を分割して並列化する方が、今の段階だと、ずっと簡単に速くなるようです。ただし、近い（？）将来、マルチコアが 100 とかいうレベルになると状況が変わるかもしれません。

お礼

回答ありがとうございます。
今後はループと再帰処理をうまく使い分けていこうと思います。

回答No.3

noname#29459

メリットは、指摘とおり、簡潔な表記が出来る場合がある。あと、　ANo1にあるように、環境によっては、パラレリズムで、処理速度を上げれる可能性がすこしある。

デメリットは、一般にスタックを多用するので、メモリ制約がきつい環境では、再帰処理では、まずい場合がある。
　無限ループは、再帰だろうと、ループだろうと、条件がいいかげんなら、おきるので、関係ないです。

なお、多くのコンパイラでは、自分自身を、尻で呼ぶような、tail recursionの場合は、ループ処理のコードが生成されます。

お礼

回答ありがとうございます。
今後、膨大な量のデータを扱うことになるかもしれないので、
メモリの制約には気をつけたいと思います。

回答No.1

Dxak

私的な意見かも・・・
再帰処理の最大のメリットは、処理を単純化および高速化することが最大のメリットだと思います
１つの処理を小さくし、細分化することによって、マルチプロセス向きとも言われてたような気がします
過去のＰＣのようにシングルプロセスであれば、あまり重要視する必要も無い話なのですが、マルチプロセス、マルチコア化が進む現状では、必須とも思える処理だと思います
しかし、質問者様が言う様に、資源（メモリ）を消費が膨大に増えると言うのは確かにあります

お礼

回答ありがとうございます。
参考になりました。