なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
>>366
昨日から昨晩に掛けてのやり取りを知らないのか?
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。 やり取りからだって?
2chの妄想だけじゃなくて現実を見ろよ。 ∞倍 wwwww
無限大を憶えたての小学生かよ
quick sort 再帰/quick sort 非再帰 = ∞, すなわちquick sort 非再帰が0って事だな。
再帰を必死に否定しているバカの主張
1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
5 非再帰版qsortの実行時間はゼロ
本当に知能が低い >>364
最適化なくてもループのが速いでしょ
10000倍は無いがw >>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。
大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」
俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」
であって、
ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。
クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや 繰り返しの方が再帰より速い!
(ただしシェルスクリプトに限る) >>371
引数受け渡しとかレジスタ待避とかで、余分なメモリー操作が発生する。 >>374
>>260
定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。 >>374
明示的なスタック操作と大差ないのでは? >>373
純粋に処理速度の話してんならネイティヴコード化したものでないとさ >>375
横ですが、再帰呼出だとcallのオーバーがある分遅くなるで良いのかな?
まあ数パーセント程度だと思うけど クイックソートだからなんとかなってるだけで
たとえば赤黒木の操作を自前でスタック管理するアホはいないわけ >>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5〜3clockくらいの差になると思う。
今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。 >>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。
一体お前は何を求めてるんだ? >>382
そこまで解説できる人ならネイティヴコードだと逆転するのわかるでしょ
アセンブリで書けとは言わんけどさ
>>381はすまん >>384
ループ以外の本質的な処理に100clock掛かるとすれば、
数%の差だけどループより再帰のが遅くなるって意見は正しいねって話さね
381については了解 >>378
tail callを繰り返しに変換できるようなケースだと
関数呼び出しはコスト高かも知れないが、
ループ版では明示的スタック操作をしなければならない場合、
call,ret相当のことをjpと組み合わせて明示的にやらないといけない。
通常、関数呼び出し後のスタックフレームの確保はcalleeが明示的にやるからループ版と変わらないが、
スタックフレームの開放はretが自動的にやる。
だからコスト的には大差なく、
関数呼び出しの方が有利なケースだってあるはず。
繰り返しの明示的なスタック操作が圧倒的有利にあるのは、
FILOじゃなくてFIFOにしたり戦略が建てられること。 >>379
お前は何を言っているんだ。
FreeBSDもLinuxも.NETもJavaも赤黒木はループで実装してるぞ。
再帰はプログラムの中に時限爆弾仕込むようなもの。再帰使うやつはテロリスト。 頑張ってバグ入れずに済んでよかったね、としか。
しかもそれで得られる速度の向上も微々たるもの。 >>389
再帰にしたらバグが減るってものでもないしなあ。
不変オブジェクトを使うから再帰がやりやすいのであって
可変オブジェクトでの再帰はループよりもややこしいところがあるよ。 >>388
>赤黒木はループで実装してる
本当か?やればできるものなのか?証拠をみせてみろ
平衡ニ分木であるからスタックもむやみに深くならないし,
正直なところ,可能だとしてループ化するメリットがあるのかね >>391
freebsd red black tree source
とかで検索すれば出てくるよ >>390
バグ云々ではなくて、コード数や可読性だと思うが
そもそも再帰呼出を理解出来ない人は論外だが 知らないうちにコードが再帰化してハマりました
のほうが多そう >>395
バグが増える要因はプログラミングソースのステップ数や可読性に左右されるのであって、アルゴリズムは特に関係ないということ >>396
アルゴリズムによってステップ数や可読性は変わるよ >>388
LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してないからあたりまえ。
どっかで見たことある気がしたので探してみたらunbound
http://code.metager.de/source/xref/freebsd/contrib/unbound/util/rbtree.c
また一つ、再帰否定バカが無知のエビデンス(笑)を積み重ねていく >>398
知らない人がいたから言っただけだよ。
ループで実装されてるんだよーって。
インターフェースを実装してないからとか理屈付けする意味あるのかな。
バカはお前。 インターフェース?
再帰と関係あるのかな?
わからん。この世はわからんことだらけだ。 > LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してない
?
OSが…インタフェースを…実装? >>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない? >>402
スタック管理の解釈次第だね。>>388が変だと結論できる解釈もありだね。 >>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね? 最近、書き込みが多くなって
このスレの勢いがすごい >>406
確かに。
>>256から数えて、1日半で150も伸びてる。 >>405
再帰をループに置き換えるときには
再帰で暗黙的に管理されるスタック上の情報を
明示的に管理する必要がある。それをやるのは面倒だから
赤黒木は再帰で実装されているはずだというのが>>379に関する俺の解釈。
面倒なことないよ、現に赤黒木はループで実装されることが多いよっていうのが>>388 語句の解釈に文句つけるのはあまり建設的じゃないような・・・。
その先には何もないような・・・。 クイックソートについても再帰のスタックをそのまま
ループで再現するっていうのはどうかと思うなあ。
末尾再帰は単純なループに変換できる。ループで書くならループらしい書き方をするべき。 >>408
ふーむ。
複雑な再帰構造を持つ場合、例えば再帰下降構文解析器みたいに複雑な相互再帰をする場合には
クイックソートの時のように簡単に再帰をループで置き換えることは出来ない。
そして一般に再帰をループで置き換えるならスタックが必要で、
込み入った再帰をスタックを使ってでもループに置き換える奴は居ないだろう。
現に赤黒木をスタック管理をしてでも強引にループで書き直すようなアホは居ないんじゃないの?
というのが>>379に関するこっちの解釈。
それに対し、いやいや赤黒木はループで実装してるんだぜ!ってのが>>388の俺の解釈。
話が噛み合って無くね?ってのが>>402
日本語の問題な気も >>411
解釈が違うのなら話が噛み合わないことについては筋が通るかと。 >>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ! >>413
一方の再帰呼び出しは末尾再帰になるっしょ。ループに置換できる。 >>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと >>415
・・・・・・それは依然として再帰関数と呼ぶのでは? >>416
僕とー君とーは解釈が違うよねってことだよ。
こき下ろすべきじゃないと思うのは君の勝手ー。
こき下ろすのも僕の勝手ー。
ヒューマニズム振りかざす人大嫌いー。←これ僕 >>417
ループを書く場合、一方の再帰呼び出しは末尾再帰だから
単純なループに置き換えられるよねってことだから、もはや再帰関数とは呼ばないよ。 >>418
いや、君が>>403で言ったのは「スタック管理」の解釈の違いだろ?
「赤黒木が再帰で書かれてる」等とは一言も言ってない>>379を読んだ君が>>408みたいな解釈をして、
人のことをテロリスト呼ばわりするのってどうなの? >>419
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0
「再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」
ループを含む関数は再帰関数にはなれないの?
そんなことはないと思うんだけど。 末尾再帰を勘違いしている人がいるので説明しておこう。
末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
(単純な)ループを何らかの理由で再帰の形にしないといけない時、
末尾再帰の条件を満たすように、ループを再帰に変換すると
コンパイラが再帰をループに逆変換してくれる機能
なので、再帰を全て末尾再帰にできるわけではなく
(末尾再帰にできるのは、元が単純なループの場合のみ)
また、ループ ─(人間)→ 再帰 ─(コンパイラ) → ループ
というふうに、ループに戻しているだけなのでループより速くなることはない。 >>401,404
FreeBSDのrbtreeもLinuxのrbtreeもそういうインターフェースを実装していないって事だよ。 >>422
より正確には、「再帰全てをノーコストで末尾再帰にできるわけではなく」かな。
関数がファーストクラスならCPSに変換すれば末尾再帰の形にはなる。
・・・・・・ヒープガリゴリ使うし、スタックを自前で持つのと変わらんけど。 >>420
>>379は「赤黒木が再帰で書かれてる」とは一言も言ってないけれども、
「赤黒木の操作を自前でスタック管理するアホはいない」と言っているのだから
赤黒木の操作は、自前でスタック管理しないやり方、つまり再帰で実装される
と思っているという解釈は妥当だと思ってる。悪いけど、この解釈については譲歩するつもりはないよ。
120%君が間違っているし、再帰を使う人は120%テロリスト。それでいいね? >>424
速くするための末尾再帰なのに、
逆に遅くなったら本末転倒だよなw >>421
無理。再帰を使うなら全部再帰で書くべき。
ループを使う処理では再帰を書かない。
再帰を使う処理ではループを書かない。
それで初めてループと再帰の決着がつけられる。
そしてループが勝利する。 >>425
確率が1を超えてるとか、幼稚園に迷い込んだ気分だよ。
「赤黒木の操作を自前でスタック管理するアホはいない」と言っている以上、
赤黒木の操作は、スタックなんてものをそもそも自分で触らないようなやり方、
つまり再帰か、又は上手なループで実装されているって話だろ?
フィボナッチ数を計算する関数をスタックを使わずに書いたって言った時、君は再帰の方しか思い浮かべられないのかい?
もしかして自閉症患者かい? >>427
それじゃぁ各ノードに可変個の子要素を持つ多分木を列挙するコードは
どうやって書くつもり?
for (auto it : children) {
if (it->is_leaf()) {
printf("%d ", it->value);
} else {
it->print_values();
}
} >>428
>>389を見るに、そうじゃないと思うんだがなあ。
俺は自閉症患者だけれども、それとこれとは関係ない。
お前は全国の自閉症患者やそのご家族の方に謝罪するべき。
あとテロリストにも。 >>429
どうやってって何がだよ?
ループでか?再帰でか? >>430
日本語って難しいよね。分かる分かる。
>>389の解釈は、
再帰でも書けるところをループで書いたんだ。へぇ。バグってなくて良かったね。ご苦労さん。
じゃないの?
>>379が再帰を仮定しているかどうかとは別問題。
俺も自閉症患者だけどね。自分に謝るのって変な感じがするよ。 >>431
どっちでも良いけど、どっちかしか「使ってはならない」というローカルルールの元ではどう書くの? >>431
まだ出来ないの?
>>429に7行で書いたような、こんなコードが走ります的な切れ端で十分伝わるんだよ? >>432
スタックで管理の解釈の違いだな。やっぱり噛み合わない。 >>434
あのさ、同意も取らずに強引に物事を進めようとするのってどうかと思うよ。
北風と太陽って話くらい知ってるでしょ?コンセンサスってとても大事。
お前コンセントしか知らないだろ。扇風機の線をぶち込んどけば何とかなるものと
しか思ってないだろ。それじゃないからな。
まずは、どういう理由で書いてほしいのかっていうところと
それによって何が成し遂げられるのかっていうところとどうして自分で
やらないのかって言うところを説明して、心からお願いしないと俺の不動の心は動かないよ。 >>435
残念。
>>436
ループを含む関数が再帰関数になれないのであれば、
>>429のような書き方は認めないって事だよね?
君ならどう書くの?って聞いただけなのになんでそんな反応になるのかね? 横道にそれ過ぎずに、それぞれの論旨を書いてみろよ。
中傷合戦ひどくてわからん。 >>437
ループと再帰の優劣をつける場合、ループはループだけで
再帰は再帰だけで実装するべきだよねって話をしただけだよ。
お話の前提をすり替えてあたかもお話が続いているように
するのはよろしくないと思うんだよな。 >>438
俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
恐ろしいことだ。 >>438
大本の論旨としては、人のことをテロリスト呼ばわりするのってどうなん?って事なんだけど。
ループと再帰の優劣をつけるなんてどこから出てきた? >>441
テロリストと呼ばれるのが嫌ならテロ行為やらなければいいだろ。
クイックソートでやってただろ。ループがいいか、再帰がいいかって。それのこと。
知らなかったの?じゃあ知って。今知って。 バッファオーバーフロー攻撃を成功させるためには、再帰が最も都合よい。 攻撃されるのと攻撃するのと、どちらが良いか?
当然、攻撃する方が良い。
つまりテロリストは勝ち組なのである。
当該スレにおいて再帰を推奨している人は勝ち組である。
なぜなら危険物を推奨するのは攻撃側だからである。 >>443
そういうことだな。昨今、関数型言語の流行に伴って再帰がすぐれたものであると
思い込んだニワカのペーペーどもがろくな知識も持たずに危険なコードを
書きまくって悦に入ってる姿を見ると暗い気持ちになる。再帰というのは
ループに大敗北した歴史を持つものだっていうのを知って欲しい。
for whileというのは再帰の進化形。メガ進化。 お前ら逮捕されても知らんぞ。
公共の場所で再帰を勧めたりしてたら、そのうち警察が事情を聴きに来るぞ。 どうでも良いけど、再帰がテロ行為になるなんて初耳だなぁ
# 今日の夕飯はすき焼きでした >>447
自動車の256バイトしかないRAMで再帰したら、バシバシ轢き殺すぞ。
そこまでやってこそ本物のテロリストだろ。 >>448
誰がそこまで特殊でオンボロな例を挙げろと
ちなみにテロリストの定義はテロリズムを奉ずる人で、
テロリズムの定義は
https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%AD%E3%83%AA%E3%82%BA%E3%83%A0#.E5.9B.BD.E9.9A.9B.E9.80.A3.E5.90.88
「住民を威嚇する、または政府や国際組織を強制する、あるいは行動を自制させる目的で、
市民や非戦闘員に対して殺害または重大な身体的危害を引き起こす事を意図したあらゆる行動」
だそうですよ。
あと自動車の場合、バシバシ轢き殺すなんて事態にはならず、単にエンストするだけだと思うの。
フェイルセーフって知ってるよね? >>440
> 俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
> 機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
俺の知ってる事実と違うね。
俺は今日は364から話を始めた。そこにID:9aquywWvが388から割り込んできて、
人のことをやれテロリストだやれ機関銃をもって脅してきただ喚いてるの。 >>450
テロリストは自分のことをテロリストだと思っていないんだよな。
聖戦士だと思ってる。
正義のために再帰を仕込むんだよな。
まあでも、国民側から見ればテロリストなんだけどな。 再帰なんてある意味爆弾みたいなものだしな。
テロリストが使う新型爆弾なんじゃねーかな。 そうやって正義の為にループを仕込むんだね?
よく分かったよ!
ちなみにバッファオーバーフローの攻撃手法としては再帰は下の下だからな。
getsなんかを使った方がよっぽど手っ取り早い上に任意コード実行まで出来る。 >>450
聞かれたから答えてたけど、>>388は君に対するレスじゃないよ。 >>454
知ってるよ?
でも再帰使うやつはテロリスト発言で敵を増やしてないかい? >>455
割り込んでないよね。テロリストと糾弾されて君が勝手にファビョッただけだよね。
僕は畑耕してただけ。 >>456
文脈をよく読もう。
364から始まる再帰とループに関する話に混ざった379に君が割り込んでるね? >>457
割り込んでないね。僕は>>379に話しかけただけだね。
君が>>379とお話したかったのなら>>379に話しかけるべきだね。 >>458
そうだね、偉大だね。
スプンタ・マンユに祈りを!(宗教ちげぇ) >>460
いわゆる暇人という奴では。
>>461
木構造って知ってる?
あと、俺はそのレス(>>379)にその返し(>>388)って変じゃね?って言っただけで、
それに対して君が「スタックの管理とは」なんて話を始めるから(>>403)
そのコード(>>398)の何処にスタックなんて使われてるんですか―って訊いて(>>405)
それに対してまだ答えが返ってきてないんだけど。
君はあれかな、都合の悪い質問は見なかったことにする人なのかな。 >>463
なんで僕にレスしてくるの?
自分が話したいことがあるならそれを話せばいいじゃん。
僕は僕で自分の話したい話を話したい人とするから。
たまたま>>379だったってだけで君が>>379と話したいなら
僕はそれを否定しないよ。割り込まれたとも思わない。
ほら話しかけろよ。>>379も絶対お前のこと好きだって。
言っちゃえよ。好きだって言っちゃえよ!