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

再帰呼び出し、よく使う?使わない? 94

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

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

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

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

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

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

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

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

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

    • by Anonymous Coward

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

    • by Anonymous Coward

      計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。リソースが膨大でも実際にスタックとして確保されるメモリは多くない。たかだか1〜10MB
      末尾再帰以外の再帰呼出しは関数型言語でも基本的にスタックを消費する。


  • /* どうちがうのか、自分には全くわからない。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;
      }
    }

    --
    新人。プログラマレベルをポケモンで言うと、コラッタぐらい
    ここに返信
    • by Anonymous Coward

      同じ結果になるように実装しているのだから、どう違うのかといえば違いませんな。

      コードについて言えば...
      int x を (static な生存期間をもつ現在位置ではなくて) auto な生存期間のものにするともうちょっと違う鴨。
      C (なのかな、exit がそう書けるかどうか...?)だと main の引数は変更できないから(※1)別の関数名にする必要があり、
      さらに脱出に exit 以外のものを使用する必要がありますが。

      コンパイラがそう最適化するはず/べきだ、という話であれば、
      極端に話「学生に数字を列挙せよ」というところからプログラミングといってるのと同じで話してるレベルがちょいと違う。
      (学生が理解できないのは学生がタコなだけ、ですし)

      ※1 あーフリースタンディング環境がどうとかいう話は別でお願いね ^_-☆

    • by Anonymous Coward

      その例だったら前者の方がマシだと思います。
      まぁ、コンパイル通らないけど。

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

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

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

    ここに返信
    • by Anonymous Coward

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

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

      • by Anonymous Coward

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

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

    • by Anonymous Coward

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

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

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

    ここに返信
  • あるいは一定の深さで再帰を中断するコードを仕込むなら。でも最近の言語は、イテレーターや無名関数が充実してるのであえて書くことも無い。
    ここに返信
  • Cのポインタとかもそうなんだけど、「便利だしその機能であるほうが自然で有利」っていうのはある(なので使う時は使う)

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

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

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

    --
    M-FalconSky (暑いか寒い)
    ここに返信
  • 再帰が必要なら再帰にする。
    必要かどうかがわからないなら、まだケツが青いってこった。

    ここに返信
  • 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);
            }
    }

    ここに返信
    • by Anonymous Coward on 2015年02月11日 19時09分 (#2759501)

      キューを使う方法も知っておくと、今後の人生とメモリ使用量が豊かになるでしょう。

      • by Anonymous Coward

        まて。スタックを使うのではなく?

        • by Anonymous Coward

          あ、いや、FILOなコレクションを使うのではなく?という意味で。

        • by Anonymous Coward

          幅優先探索のこと言ってるんじゃね?
          キューのメモリはヒープに取る希ガス。

    • by Anonymous Coward

      ああ、俺もフォルダ階層潜る時にしかつかってないかも。。

    • by Anonymous Coward

      データ構造が再帰的なんだから
      アルゴリズムが再帰的になるのは当たり前

      元の主張は,意訳すると,反復処理をわざわざ再帰で書き直すことに意味が無いと言ってる.

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

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

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

    みんなもそうだよね?

    ここに返信
    • by Anonymous Coward

      つ[Promise]

      • by Anonymous Coward

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

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

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

    ここに返信
    • by Anonymous Coward

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

    • by Anonymous Coward

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

    • by Anonymous Coward

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

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

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

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

    ここに返信
    • by Anonymous Coward

      VBですらDoEvents()があるのに?それに今どきUIスレッドで処理すんなや。

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

    スタックが十分にあれば

    ここに返信
  • by Anonymous Coward on 2015年02月11日 18時53分 (#2759494)

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

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

    ここに返信
    • by Anonymous Coward

      SQLだと見やすいので使っちゃいますね
      再帰が必要になるような設計にしたやつが悪いってことで

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

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

    ここに返信
    • 再帰は深さが不定なツリーを舐めるような処理、つまり文字通り「再帰的」な処理に適してる。
      ループじゃキツイでしょう?

    • by Anonymous Coward

      HaskellにはForもWhileもありません。
      機械的にコーディングすればいいだけの会社なら命令型以外のパラダイムなんて知る必要もないのでしょうが。

      • by Anonymous Coward

        whileはあるぞ…

      • by Anonymous Coward

        機械的にコーディングするのがプログラミングの全てだと思い込んでる人が多い気がする、ここを見てると。

        • by Anonymous Coward

          さすがにそれは酷い思い込みだと言わざるを得ない

          # 思い込んでる人が多い、という思い込みのことだぞ

    • by Anonymous Coward

      反復はともかく、再帰が必要なデータ構造が増えている。

      たとえば、
      製品AにはオプションA1,A2,A3があって、オプションA1にはサブオプションA11、A12、A13があって、A12にはサブサブオプションA121が..
      なんて階層になった選択画面を作ってくれといった話はどこにでもあると思うんだけど。
      もちろん、結果がどう残るのかはともかく、表示上はA1とA2は排他。

      で、何階層まであるんですか?と聞けば決まってない、でも簡単でしょ?と言い返される。

      簡単にサクっとつくってやろうじゃないか。
      #でも、後々ちゃんと保守できる技術者確保しなければどうなっても知らないよ。

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

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

    ここに返信
  • by Anonymous Coward on 2015年02月11日 19時32分 (#2759515)

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

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

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

    ここに返信
    • by Anonymous Coward

      左右の探索結果を掛け合わせればいいだけじゃん。

  • by Anonymous Coward on 2015年02月11日 19時50分 (#2759524)

    そもそもIntelはコールスタックを一部ハード実装して高速化する仕組みが入っている。
    というよりコールスタックが深すぎるとキャッシュアウトして、メインメモリに行きかねない。
    つまり深すぎる再帰プログラムを書くと、実行速度がスピンダウンする上に、オーバーフローのリスクが有る。

    したがって、デバッグ版や作り捨てでは 再帰で実装するけど
    リリース版(商用実装)では、それをループなどに展開して、自前のコールスタックに入れてオーバーフローしそうになったらスローする実装にする。

    ここに返信
typodupeerror

あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall

読み込み中...