パスワードを忘れた？ アカウント作成
Close
11914203 story
教育

再帰呼び出し、よく使う？使わない？ 141

ストーリー by headless
道具 部門より
本家/.「AP Test's Recursion Examples: An Exercise In Awkwardness」より

FacebookのAP Computer Sicence(大学先修課程のコンピューターサイエンス科目)グループ(非公開)に投稿された、再帰呼び出しを使って0から6の数字を出力するコード例について、「APの試験で粗末なコーディング技術が使われていることを示す例がまた現れた」とAlfred Thompson氏が皮肉った。Thompson氏は「我々はしばしば、コード例に理想的ではないコーディング技術を使わざるを得ないこともある」と指摘。「通常は使うことのないコードを例にするのは、物事を明確にし、特定の概念を説明するためだ。特に再帰呼び出しを必要とする例はかなり複雑になる傾向があるので、このようなコード例は再帰呼び出しの解説で多く使われているようだ。」という。「0123456」を出力するためにループではなく再帰呼び出しを使用しているのは再帰呼び出しの処理を教えるためではあるのだが、Thompson氏はこれも粗末なコーディング技術の例であると主張する。

ただし、「再帰呼び出しで反復処理を行うのが一般的な関数型プログラミングを学んできた人は、当然これに同意しないだろう。」と付け加える。「金槌しか持っていなければ、すべての問題が釘に見えるなどと言われるが、再帰呼び出しとループの問題も同様だ。反復処理のために最初に選んだ(または最初に学んだ)のがループであれば、再帰呼び出しを解決方法だとは思わない傾向がある。同様に(関数型プログラミングで一般的な)再帰呼び出しから始めたのであれば、再帰呼び出しが反復処理のためのものだと考えるだろう。」とのことだ。皆さんの場合、再帰呼び出しをよく使う傾向があるだろうか。それとも避ける傾向があるだろうか。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

再帰呼び出し、よく使う？使わない？ More

  • どっちで考えるかだけ (スコア:2, 興味深い)

    by Anonymous Coward on 2015年02月11日 18時49分 (#2759489)

    ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するし
    ロジックを設計した段階で単純ループになってればループ構造で実装する。

    そのように考える方が分かりやすいからそういうロジック設計になっているのだし
    リソースが潤沢な時代だからどっちでもいい。

    • Re:どっちで考えるかだけ (スコア:2)

      by plauda (46850) on 2015年02月11日 21時12分 (#2759582)

      趣味では使うが、仕事では積極的に使わない。
      ハイエンドのマシンを使う顧客とか、ピーク時でギリギリ扱えるぐらいの余力だったりする。
      やはり、リソースが潤沢という前提が成り立つかどうかかが、業務などの環境依存なので環境依存のコードを入れるのは避けたいところ。

      色んな顧客がいて、負荷がかかるコンポーネントも少しずつ違うし、負荷特性の違う顧客にそれぞれの顧客に対して、
      再起呼び出しで使うスタックサイズが十分であることを保証し続けることが面倒。

      顧客のシステムが運用中にスタックオーバフローで落ちるとか目も当てられないので、
      まずは、見積もり式が必要になるが、これを作成し、メンテナンスし続けるのが手間。
      再起関数を修正すると、必要なスタックサイズも変更になるし、その度に再見積もりさせる訳にもいかない。
      というより、再起呼び出しを使わなくても、スタックに置くデータサイズには気を使う。
      ヒープ見積もりも、見積もりしやすいようにデータ構造の管理方法とか工夫しているくらい。

      シェア
      親コメント

    • Re:どっちで考えるかだけ (スコア:1)

      by Anonymous Coward on 2015年02月11日 19時24分 (#2759511)

      とはいえスタックサイズを過信しないほうがよいと思う。

      シェア
      親コメント

  • /* どうちがうのか、自分には全くわからない。gotoは0引数の自分への再帰でしょう? */
    /* 末尾最適化できないのはコンパイラかプログラマがタコなだけ。 */

    #include <stdio.h>
    int x=0;
    int main(){
    main:
      x++;
      printf("%d\n",x);
      if(x<100){
        goto main;
      }else{
        exit 0;
      }
    }

    #include <stdio.h>
    int x=0;
    int main(){
      x++;
      printf("%d\n",x);
      if(x<100){
        main();
      }else{
        exit 0;
      }
    }

    --
    新人。プログラマレベルをポケモンで言うと、コラッタぐらい

  • 再帰的なデータ構造を扱うとき（ツリーをトラバースするときなど）は、再帰呼び出しを直接使うことがあります。

    その他、末尾呼び出しがスタックフレームを消費しない言語を使うときは、継続条件が繰り返しの途中に現れるようなループを書く際に、再帰呼び出しを直接使います。

    より抽象化された高階関数などが使える時は、当然ながらそちらを使うべきだと思います。

    • Re:使うこともある (スコア:1)

      by Anonymous Coward on 2015年02月11日 20時13分 (#2759542)

      ＞再帰的なデータ構造を扱うとき（ツリーをトラバースするときなど）は、再帰呼び出しを直接使うことがあります。
      これは再帰を使わないほうが難しいね

      シェア
      親コメント

    • Re: (スコア:0)

      by Anonymous Coward

      > より抽象化された高階関数などが使える時は、当然ながらそちらを使うべきだと思います。

      関数型言語のコミュニティでも、再帰呼び出しを直接書くのは好ましくないスタイルとされているはずです
      ケースバイケースですけども、mapやfoldrが使えるのにオレ再帰は歓迎されません

      • Re: (スコア:0)

        by Anonymous Coward

        個人的な印象だと、動作や検証などフローに着眼するものは高階関数より再帰の書き下しのほうが理解しやすい気がします
        値を生成するものは高階関数が読み書きのどちらも具合がいい

        あくまで個人的な印象です

  • 技術的な問題がある (スコア:1)

    by Anonymous Coward on 2015年02月11日 18時49分 (#2759487)

    末尾呼び出しの最適化が仕様で保証された言語以外でループ代わりに使うと、あっという間にスタックを使い切る。(再帰的定義で繰り返しを表す発想の起源である)数学ではスタックの深さは無限だから問題にならないだろうけど(ただし停止することの証明が必要)。

    • Re: (スコア:0)

      by Anonymous Coward

      数学的帰納法は停止しないよね！…するのか？どっちだろ。

    • Re: (スコア:0)

      by Anonymous Coward

      最初にプログラムを作った時は問題なくても、
      繰り返し何度も修正をしたりすると（他人がコードを直すとかあったりすると）スタックオーバーフローとかよくありそうw

    • Re: (スコア:0)

      by Anonymous Coward

      やはりスタックがどんどん積み上がるのをイメージしてしまい躊躇しますよね。実際はほとんど実害ないのでしょうけど

  • ソートで教えればいいやん (スコア:1)

    by Anonymous Coward on 2015年02月11日 19時21分 (#2759508)

    クイックソート等で再帰呼出使えば、両方教えられて一石二鳥だと思う

  • あるいは一定の深さで再帰を中断するコードを仕込むなら。でも最近の言語は、イテレーターや無名関数が充実してるのであえて書くことも無い。

  • Cのポインタとかもそうなんだけど、「便利だしその機能であるほうが自然で有利」っていうのはある(なので使う時は使う)

    ただ、他コメントから引用すれば「プログラマがタコ」が悪をもたらすなら、できれば利用しないですむようにするのがいいよなぁ。とは思う。

    # むろん言語の実装によって、スタックはそもそも使わないとか害がないタイプもあるだろうけど
    # ちゃんとしないと末尾再帰が最適化されないとか、ただのトラップにしかならんときもある。

    まあ、ケースバイケース、なんですが。

    --
    M-FalconSky (暑いか寒い)

  • 再帰が必要なら再帰にする。
    必要かどうかがわからないなら、まだケツが青いってこった。

  • どうしても必要になってきますね。
    階層が浅ければ階層分の関数を用意すればいいような気がしますがそれだとコピーコードになるのでだめですね

  • 再帰呼び出しを必要とする例 (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時37分 (#2759479)

    public void listRecurse(File directory) {
            for (File file: directory.listFiles()) {
                    System.out.println(file.getPath());
                    if (file.isDirectory()) listRecurse(file);
            }
    }

  • 日常的に使っている (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時41分 (#2759482)

    Javascriptでajaxだして、その結果をみてまたajaxだして、．．．
    というプログラムは再帰にせざるを得ない。
    エディタが一畳分くらいの面積で全部を見渡せるほどの注意力があれば非同期ハンドラを入れ子にすればいいのかもしれないが。

    それ以外にもDOMトラバースとか、再帰でやる方がコードが見やすい。

    みんなもそうだよね？

    • Re: (スコア:0)

      by Anonymous Coward

      つ[Promise]

      • Re: (スコア:0)

        by Anonymous Coward

        だから、$.ajax()のdone()の中で$.ajaxが必要なら再帰になる。と言っているわけですが。

  • 中断や再開 (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時50分 (#2759492)

    中断や再開といった処理が必要になった場合困るので
    自分的には避けられるならば避ける。
    具体的には例えばGUIのある場合、
    再起ループだとマウスへの応答に支障が出る。

    その場合、自前でスタック構造を組んでループ。
    場合によってはさらにインタープリターを組んでVMを構成する。

  • 使うかな (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時51分 (#2759493)

    スタックが十分にあれば

  • 読みやすくなるかどうか、が第一でしょう (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時53分 (#2759494)

    再帰で書いたほうが読みやすくなるなら使うし、そうでないなら使いませんよね。

    ただし、後世メンテナンスする人間の質が期待できない場合は
    再帰を使ったほうがすっきりするケースでもあえてループで書く場合もあります。

  • 再帰呼び出しで反復処理を行うのが一般的？ (スコア:0)

    by Anonymous Coward on 2015年02月11日 18時57分 (#2759496)

    プログラミング言語としては関数型であろうとも、ループの機能を持っていないものは無いのでは？
    関数型プログラミングの原理／スタイルを学ぶ時には再帰で反復処理を記述したとしても、現実のアプリケーション開発ではループを使わないはずが無いでしょう
    （そもそも再帰的なアルゴリズムを実装したり、再帰の方が簡明に記述できる処理をするのなら話は別だが）

  • できるだけ避けるが (スコア:0)

    by Anonymous Coward on 2015年02月11日 19時15分 (#2759505)

    できるだけ避ける。あまりスタックを無駄遣いしたくない。
    しかし、goto文などと同様に適切と思うときは使う。まあ、当然のことね。

  • 好きか嫌いかと言われましても。 (スコア:0)

    by Anonymous Coward on 2015年02月11日 19時32分 (#2759515)

    A → 関連データがない
    ├B → 関連データがある
    │└C → 関連データがある
    └D → 関連データがない
        └E→ 関連データがある

    こんな時に、 BとEを演算して、Aの結果のように振る舞うような処理とかあるし……。
    必要な時に使うってだけじゃないかな。合理的な理由があるかどうかなだけで。好きも嫌いもない。

    あ。でも再起の中でアレコレごちゃごちゃ処理入れてくるのは嫌い。
    可能な限り探査だけで済ませたい。

typodupeerror

※ただしPHPを除く -- あるAdmin