再帰呼び出し、よく使う?使わない? 94
道具 部門より
FacebookのAP Computer Sicence(大学先修課程のコンピューターサイエンス科目)グループ(非公開)に投稿された、再帰呼び出しを使って0から6の数字を出力するコード例について、「APの試験で粗末なコーディング技術が使われていることを示す例がまた現れた」とAlfred Thompson氏が皮肉った。Thompson氏は「我々はしばしば、コード例に理想的ではないコーディング技術を使わざるを得ないこともある」と指摘。「通常は使うことのないコードを例にするのは、物事を明確にし、特定の概念を説明するためだ。特に再帰呼び出しを必要とする例はかなり複雑になる傾向があるので、このようなコード例は再帰呼び出しの解説で多く使われているようだ。」という。「0123456」を出力するためにループではなく再帰呼び出しを使用しているのは再帰呼び出しの処理を教えるためではあるのだが、Thompson氏はこれも粗末なコーディング技術の例であると主張する。
ただし、「再帰呼び出しで反復処理を行うのが一般的な関数型プログラミングを学んできた人は、当然これに同意しないだろう。」と付け加える。「金槌しか持っていなければ、すべての問題が釘に見えるなどと言われるが、再帰呼び出しとループの問題も同様だ。反復処理のために最初に選んだ(または最初に学んだ)のがループであれば、再帰呼び出しを解決方法だとは思わない傾向がある。同様に(関数型プログラミングで一般的な)再帰呼び出しから始めたのであれば、再帰呼び出しが反復処理のためのものだと考えるだろう。」とのことだ。皆さんの場合、再帰呼び出しをよく使う傾向があるだろうか。それとも避ける傾向があるだろうか。
どっちで考えるかだけ (スコア:2, 興味深い)
ロジックを設計した段階で再帰的になってれば再帰呼び出しで実装するし
ロジックを設計した段階で単純ループになってればループ構造で実装する。
そのように考える方が分かりやすいからそういうロジック設計になっているのだし
リソースが潤沢な時代だからどっちでもいい。
Re:どっちで考えるかだけ (スコア:1)
趣味では使うが、仕事では積極的に使わない。
ハイエンドのマシンを使う顧客とか、ピーク時でギリギリ扱えるぐらいの余力だったりする。
やはり、リソースが潤沢という前提が成り立つかどうかかが、業務などの環境依存なので環境依存のコードを入れるのは避けたいところ。
色んな顧客がいて、負荷がかかるコンポーネントも少しずつ違うし、負荷特性の違う顧客にそれぞれの顧客に対して、
再起呼び出しで使うスタックサイズが十分であることを保証し続けることが面倒。
顧客のシステムが運用中にスタックオーバフローで落ちるとか目も当てられないので、
まずは、見積もり式が必要になるが、これを作成し、メンテナンスし続けるのが手間。
再起関数を修正すると、必要なスタックサイズも変更になるし、その度に再見積もりさせる訳にもいかない。
というより、再起呼び出しを使わなくても、スタックに置くデータサイズには気を使う。
ヒープ見積もりも、見積もりしやすいようにデータ構造の管理方法とか工夫しているくらい。
Re: (スコア:0)
とはいえスタックサイズを過信しないほうがよいと思う。
Re: (スコア:0)
計算量O(N)以上のアルゴリズムの実装には再帰を使わない方がいいよ。リソースが膨大でも実際にスタックとして確保されるメモリは多くない。たかだか1〜10MB
末尾再帰以外の再帰呼出しは関数型言語でも基本的にスタックを消費する。
再帰とループの違いが全くわからん (スコア:2)
/* どうちがうのか、自分には全くわからない。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: (スコア:0)
同じ結果になるように実装しているのだから、どう違うのかといえば違いませんな。
コードについて言えば...
int x を (static な生存期間をもつ現在位置ではなくて) auto な生存期間のものにするともうちょっと違う鴨。
C (なのかな、exit がそう書けるかどうか...?)だと main の引数は変更できないから(※1)別の関数名にする必要があり、
さらに脱出に exit 以外のものを使用する必要がありますが。
コンパイラがそう最適化するはず/べきだ、という話であれば、
極端に話「学生に数字を列挙せよ」というところからプログラミングといってるのと同じで話してるレベルがちょいと違う。
(学生が理解できないのは学生がタコなだけ、ですし)
※1 あーフリースタンディング環境がどうとかいう話は別でお願いね ^_-☆
Re: (スコア:0)
その例だったら前者の方がマシだと思います。
まぁ、コンパイル通らないけど。
使うこともある (スコア:1)
再帰的なデータ構造を扱うとき(ツリーをトラバースするときなど)は、再帰呼び出しを直接使うことがあります。
その他、末尾呼び出しがスタックフレームを消費しない言語を使うときは、継続条件が繰り返しの途中に現れるようなループを書く際に、再帰呼び出しを直接使います。
より抽象化された高階関数などが使える時は、当然ながらそちらを使うべきだと思います。
Re: (スコア:0)
> より抽象化された高階関数などが使える時は、当然ながらそちらを使うべきだと思います。
関数型言語のコミュニティでも、再帰呼び出しを直接書くのは好ましくないスタイルとされているはずです
ケースバイケースですけども、mapやfoldrが使えるのにオレ再帰は歓迎されません
Re: (スコア:0)
個人的な印象だと、動作や検証などフローに着眼するものは高階関数より再帰の書き下しのほうが理解しやすい気がします
値を生成するものは高階関数が読み書きのどちらも具合がいい
あくまで個人的な印象です
Re: (スコア:0)
>再帰的なデータ構造を扱うとき(ツリーをトラバースするときなど)は、再帰呼び出しを直接使うことがあります。
これは再帰を使わないほうが難しいね
ソートで教えればいいやん (スコア:1)
クイックソート等で再帰呼出使えば、両方教えられて一石二鳥だと思う
ソートで教えるのは最悪 (スコア:1)
クイックソートこそが、再帰呼び出しを使うのに最も不適切な例の一つじゃね。
入門書に載ってることが多いけど、マネすると酷い目に遭う。
Re:ソートで教えればいいやん (スコア:1)
ポインタで折れなかったCの初学者が次に迎える難関が、再帰の例としてクイックソートを示されることですね。
Re: (スコア:0)
マージソートにしとけ。その方が無難。
#あえて罠にはめて学習させるのが目的なら別だけど。
再帰呼び出しの階層の深さが予測可能なら (スコア:1)
自分を信じないこと (スコア:1)
Cのポインタとかもそうなんだけど、「便利だしその機能であるほうが自然で有利」っていうのはある(なので使う時は使う)
ただ、他コメントから引用すれば「プログラマがタコ」が悪をもたらすなら、できれば利用しないですむようにするのがいいよなぁ。とは思う。
# むろん言語の実装によって、スタックはそもそも使わないとか害がないタイプもあるだろうけど
# ちゃんとしないと末尾再帰が最適化されないとか、ただのトラップにしかならんときもある。
まあ、ケースバイケース、なんですが。
M-FalconSky (暑いか寒い)
わかるだろ (スコア:1)
再帰が必要なら再帰にする。
必要かどうかがわからないなら、まだケツが青いってこった。
再帰呼び出しを必要とする例 (スコア:0)
public void listRecurse(File directory) {
for (File file: directory.listFiles()) {
System.out.println(file.getPath());
if (file.isDirectory()) listRecurse(file);
}
}
Re:再帰呼び出しを必要とする例 (スコア:1)
キューを使う方法も知っておくと、今後の人生とメモリ使用量が豊かになるでしょう。
Re: (スコア:0)
まて。スタックを使うのではなく?
Re: (スコア:0)
あ、いや、FILOなコレクションを使うのではなく?という意味で。
Re: (スコア:0)
幅優先探索のこと言ってるんじゃね?
キューのメモリはヒープに取る希ガス。
Re: (スコア:0)
ああ、俺もフォルダ階層潜る時にしかつかってないかも。。
Re: (スコア:0)
データ構造が再帰的なんだから
アルゴリズムが再帰的になるのは当たり前
元の主張は,意訳すると,反復処理をわざわざ再帰で書き直すことに意味が無いと言ってる.
日常的に使っている (スコア:0)
Javascriptでajaxだして、その結果をみてまたajaxだして、...
というプログラムは再帰にせざるを得ない。
エディタが一畳分くらいの面積で全部を見渡せるほどの注意力があれば非同期ハンドラを入れ子にすればいいのかもしれないが。
それ以外にもDOMトラバースとか、再帰でやる方がコードが見やすい。
みんなもそうだよね?
Re: (スコア:0)
つ[Promise]
Re: (スコア:0)
だから、$.ajax()のdone()の中で$.ajaxが必要なら再帰になる。と言っているわけですが。
技術的な問題がある (スコア:0)
末尾呼び出しの最適化が仕様で保証された言語以外でループ代わりに使うと、あっという間にスタックを使い切る。(再帰的定義で繰り返しを表す発想の起源である)数学ではスタックの深さは無限だから問題にならないだろうけど(ただし停止することの証明が必要)。
Re: (スコア:0)
数学的帰納法は停止しないよね!…するのか?どっちだろ。
Re: (スコア:0)
最初にプログラムを作った時は問題なくても、
繰り返し何度も修正をしたりすると(他人がコードを直すとかあったりすると)スタックオーバーフローとかよくありそうw
Re: (スコア:0)
やはりスタックがどんどん積み上がるのをイメージしてしまい躊躇しますよね。実際はほとんど実害ないのでしょうけど
中断や再開 (スコア:0)
中断や再開といった処理が必要になった場合困るので
自分的には避けられるならば避ける。
具体的には例えばGUIのある場合、
再起ループだとマウスへの応答に支障が出る。
その場合、自前でスタック構造を組んでループ。
場合によってはさらにインタープリターを組んでVMを構成する。
Re: (スコア:0)
VBですらDoEvents()があるのに?それに今どきUIスレッドで処理すんなや。
使うかな (スコア:0)
スタックが十分にあれば
読みやすくなるかどうか、が第一でしょう (スコア:0)
再帰で書いたほうが読みやすくなるなら使うし、そうでないなら使いませんよね。
ただし、後世メンテナンスする人間の質が期待できない場合は
再帰を使ったほうがすっきりするケースでもあえてループで書く場合もあります。
Re: (スコア:0)
SQLだと見やすいので使っちゃいますね
再帰が必要になるような設計にしたやつが悪いってことで
再帰呼び出しで反復処理を行うのが一般的? (スコア:0)
プログラミング言語としては関数型であろうとも、ループの機能を持っていないものは無いのでは?
関数型プログラミングの原理/スタイルを学ぶ時には再帰で反復処理を記述したとしても、現実のアプリケーション開発ではループを使わないはずが無いでしょう
(そもそも再帰的なアルゴリズムを実装したり、再帰の方が簡明に記述できる処理をするのなら話は別だが)
Re:再帰呼び出しで反復処理を行うのが一般的? (スコア:2)
再帰は深さが不定なツリーを舐めるような処理、つまり文字通り「再帰的」な処理に適してる。
ループじゃキツイでしょう?
Re: (スコア:0)
HaskellにはForもWhileもありません。
機械的にコーディングすればいいだけの会社なら命令型以外のパラダイムなんて知る必要もないのでしょうが。
Re: (スコア:0)
whileはあるぞ…
Re: (スコア:0)
機械的にコーディングするのがプログラミングの全てだと思い込んでる人が多い気がする、ここを見てると。
Re: (スコア:0)
さすがにそれは酷い思い込みだと言わざるを得ない
# 思い込んでる人が多い、という思い込みのことだぞ
Re: (スコア:0)
反復はともかく、再帰が必要なデータ構造が増えている。
たとえば、
製品AにはオプションA1,A2,A3があって、オプションA1にはサブオプションA11、A12、A13があって、A12にはサブサブオプションA121が..
なんて階層になった選択画面を作ってくれといった話はどこにでもあると思うんだけど。
もちろん、結果がどう残るのかはともかく、表示上はA1とA2は排他。
で、何階層まであるんですか?と聞けば決まってない、でも簡単でしょ?と言い返される。
簡単にサクっとつくってやろうじゃないか。
#でも、後々ちゃんと保守できる技術者確保しなければどうなっても知らないよ。
Re:再帰呼び出しで反復処理を行うのが一般的? (スコア:2)
> チューリング完全ではなかったぐらいだ
チューリング完全でなかったのは意図的な仕様でしょ。
プログラミング言語がチューリング完全であるというのは
必ずしも望ましい特性ではない。
できるだけ避けるが (スコア:0)
できるだけ避ける。あまりスタックを無駄遣いしたくない。
しかし、goto文などと同様に適切と思うときは使う。まあ、当然のことね。
好きか嫌いかと言われましても。 (スコア:0)
A → 関連データがない
├B → 関連データがある
│└C → 関連データがある
└D → 関連データがない
└E→ 関連データがある
こんな時に、 BとEを演算して、Aの結果のように振る舞うような処理とかあるし……。
必要な時に使うってだけじゃないかな。合理的な理由があるかどうかなだけで。好きも嫌いもない。
あ。でも再起の中でアレコレごちゃごちゃ処理入れてくるのは嫌い。
可能な限り探査だけで済ませたい。
Re: (スコア:0)
左右の探索結果を掛け合わせればいいだけじゃん。
コールスタックのハード実装 (スコア:0)
そもそもIntelはコールスタックを一部ハード実装して高速化する仕組みが入っている。
というよりコールスタックが深すぎるとキャッシュアウトして、メインメモリに行きかねない。
つまり深すぎる再帰プログラムを書くと、実行速度がスピンダウンする上に、オーバーフローのリスクが有る。
したがって、デバッグ版や作り捨てでは 再帰で実装するけど
リリース版(商用実装)では、それをループなどに展開して、自前のコールスタックに入れてオーバーフローしそうになったらスローする実装にする。
Re:論外、使用禁止 (スコア:1)
ありがとうございます。
お言葉とおり甘えさせていただきます。
#だってアマチュア