なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
>>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
速くするための末尾再帰なのに、
逆に遅くなったら本末転倒だよなｗ >>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も絶対お前のこと好きだって。
言っちゃえよ。好きだって言っちゃえよ！ >>466
それで、人のことをテロリスト呼ばわりするのってどうなん？ >>467
違うんだ、待ってくれ、君のことをテロリストと言ったんじゃない。
再帰を使う人はテロリストなんだ。君じゃない。 >>470
つまり、>>469で示したように再帰を使う俺はどっち？ やっぱり再帰無しでループによるプログラミングが最高だね！ 私生活において自分ほど品性の高い奴はそうそういないよ
何をしていてもカリスマ性があふれ出してしまう 「しね」というのは、実は奥の深い言葉なんだけど知っていましたか？
プログラム中でいえばNULLと似ている
人はなぜ生きるのか、なぜ死なないのか、
その真理を見つける事は誰も出来ていない
よって「死」とは恐怖かもしれないし、救いかもしれない
つまり正解でも不正解でも無い
それゆえに「しね」という言葉を発しても、敵と味方は最終的に五分にしかならない意味のない言葉なんです
だから頻繁に使っていくと良いよ >>423
インターフェースとか抽象データ型ってことを理解できてないから、
そう言っただけでは理解できないんだと思うよ。 >>485
お前のほうが分かっていないような気がするが‥ >>422の「なので、再帰を全て末尾再帰にできるわけではなく」とか恥ずかしいよなw >>489
>422 「再帰を全て末尾再帰にできるわけではな」いのは当然だが，どうしてはずかしいんだ？ > コンパイラが再帰をループに逆変換してくれる機能
恥ずかしい発言はこれだね。 掲示板ではレベルのミスマッチがよくあるんだよな。
たとえば、アセンブリと機械語は一対一で対応していると純粋に信じてる人は世の中に結構多い。
そういう人たちとプロセッサのデザイナが掲示板で議論すると当然ミスマッチが起こる。
こういう場合、当然勢力の面でデザイナの方が分が悪くなるね。
世の中、知ったかぶりのバカの方が多いから。 手動で末尾最適化をしてみればいいんだよ。
そうすれば、なるほど、
これが最適化されたコードなんだな！って
ループになったコードを目の当たりにすることになる。 そういう周りくどい事やってるうちは三流
uyの領域に到達すると文章読むだけで理解する >>491
コンパイラが再帰をループにしてくれる機能はあるよ，恥ずかしいのはどちら？ 再帰の方が有利なら、わざわざループに変換するなよ。
むしろ、ループを自動的に再帰に変換しろよ。 >>492
逆変換が意味不明
単に変換なら同意するけど 再帰が実用的でなく
ループの方が有利だから
変換しないといけない。 >>498
それは文脈による，よく逆電圧っていうが実は順電圧だったりすることはあるし >>501
> それは文脈による，
だからこの文脈だと意味不明って言ってるんだが
> よく逆電圧っていうが実は順電圧だったりすることはあるし
ますます意味不明 分かるように説明できないんじゃ周りは皆分からず屋に見えてしまうね 我々市民はテロリストを納得させるような言葉を持たない。
従って、テロリスト自ら変わらない限り、テロリストは永遠に市民の敵である。 >>496
キミの方だとおもうよ。ぷぷぷ。
「末尾再帰は... コンパイラが再帰をループに変換してくれる機能」
> 末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
> （単純な）ループを何らかの理由で再帰の形にしないといけない時、
> 末尾再帰の条件を満たすように、ループを再帰に変換すると
> コンパイラが再帰をループに逆変換してくれる機能 >>496
それは、「末尾再帰最適化」というコンパイラの機能だね。 「ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる」
頭沸いてるだろ。ぷぷぷ。最初からループで書いとけよ。 そんなんじゃ小説なんか読めないだろう。
読解力なさすぎだよ。 読解力が足りないとか言いだしたぞ。このバカ。
> ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる機能 >>490
再帰はすべて機械的に末尾再帰に変換できる。
そんな基本的なことも知らないのは恥ずかしいだろう？ おー、すげー。天才現る。
これで、スタックオーバーフロー完全克服だ。 末尾再帰に変換できるとは言ったが,スタックオーバーフローを回避できるとは言ってない(ｷﾘｯ クイックソート10000倍高速化とか再帰→末尾再帰の自動変換とか、このスレには天才が多いな。 >>510
俺は第三者だ。
俺は書き込んだ奴の言いたいことが容易に把握できている。
それがキミにはできないという。
再帰についてのスレで再帰について書かれているのだから、バックボーンの違いではないだろう。
知識ではなく読解力の問題だ。
こんなもん小学生でも意味をくみ取るぞ。 >>516
>>422を理解出来てるのか? こりゃすげーわ。
ループを再帰の形にするときに、ループを再帰に変換すると、再帰をループに逆変換してくれるコンパイラの機能が末尾再帰?
>>422が末尾再帰を理解してない事が読み取れるだけだ。
それをお前が読み取れるという事は、同一人物以外あり得ない。 そんなんじゃ小説も読めないだろう。
末尾再帰とは、本来ループで書くべきものを再帰で書いた時にコンパイラが
自動でループに直す機能・・・という主張なのだろう。 >>515
よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。 逆変換という言葉は、そういった前提があって出てくる言葉だと思うぞ。 コンパイラが最適化してくれるならコンパイラにやらせるのが普通の話だよね >>520
末尾再帰の説明に「逆変換」を使うってどういう前提だよ www >>523
本来ループであるべきものをプログラマが再帰に変換しているので、
コンパイラがループに逆変換するという主張なのだろう。
お前、本当にこの程度の文章が読めないの？
そんなんじゃ小説どころか論文も読めないだろう。
俺は元の文すら読んでいなく、引用されてるのを見てそこまで理解できてるぞ。
もう一度聞くけど、お前本当にこの程度の文が読めないの？ > インバータ（Inverter）とは、
> 直流電力から交流電力を電気的に生成する（逆変換する）電源回路、
> またはその回路を持つ電力変換装置のことである。
> 逆変換回路（ぎゃくへんかんかいろ）、逆変換装置（ぎゃくへんかんそうち）などとも呼ばれる。
逆変換ｗ >>519
>よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。
何言ってんだこいつ >>524
おおー、スゲー
その調子で>>422を解説してくれや。 >>526
読解力が、足りない。
半端な知識を振り回す知ったかぶりが沢山いるという事だよ。 >>528
それは読解力関係ないだろう。
俺にも全く意味が分からなかった。
何言ってんだコイツ？というのが素直な感想。 http://athos.hatenablog.com/entry/20110119/p1
ここまでこれの話題ないって相当終わったレベルの奴らしかこのスレにいないんだな
さっさと死ねよ >>531-532
本当に頭悪いカスだな
rubyに限定せず実装出来ると思うけど技量的に理解すら無理な感じ？
再帰とループの変換や末尾再帰の話題には触れてもここはTCOという単語が今まで一回も出てこないという事実
「知ってる側」からすると嘘をついてるのがすぐにわかってしまう
知ったかぶりのクズ >>533
だって末尾再帰なんてlisp/schemeでは当たり前だもの，今はgccでも当たり前だし
いまさらrubyですかね‥ むしろ自分でやんないと末尾呼び最適化が利かない処理系って（ry >>533
何度も出てるし「末尾再帰」といった時点でジャンプへの変換という意味を持っていってるんだよ。
最適化が無ければ「末尾」と特別な扱いをする意味が無い。
runyって最近言い出したのか。30年遅れてるな。 理解度が低すぎる
このアルゴリズムはこのスレでは初出だと認識してるけど
読めなくてわけわかんない状態か
さっさと死ねゴミ 妥協点でPythonだからね
それ以下の言語でアルゴリズム語ってるスレ見ると
そこで話してる内容とか読む前に
まずはスレ民を学習させる事から初めて
レベルを上げてやらないと話にならない >>540
末尾再帰のループ最適化は >>5 や >>507 ですでに出てきているよ
>>541
最適化の話題なら python や ruby のようなインタプリタではなく
コンパイラで比較するのが適切だね，インタプリタ上で速くなっても
だれもうれしくない．C/C++一択だよ
ま，fortran でもいいが >>542
理解力なさすぎだな
お前の学校の担任はさぞかし苦労したことだろう >>546
どんな点をみて「理解力がない」と判断したのか？
説明できますかね，それとも吼えるだけ？ つか、末尾再帰ってループそのまんまで再帰の利点ないし
recHoge1(a,n,arg...){
dobefore()...
if(a<n)recHoge1(a,n,arg...);
}
loopHoge1(a,n,arg...){
while(a<n){
dobefore()...
}
}
再帰は無意味、使う必要なし
recHoge2(a,n,arg...){
dobefore()...
recHoge2(a,n,arg...);
doafter()...
}
loopHoge2(a,n,arg...){
while(a<n){
pushargstack();
dobefore()...
popargstack();
doafter()...
}
}
再帰で有意味、この場合使える pop,push逆だった
loopHoge2(a,n,arg...){
while(a<n){
popargstack();
dobefore()...
pushargstack();
doafter()...
}
} pushargstack();
popargstack();
ユーザー定義のこれらはめんどくさいから
再帰関数使ってコンパイラ任せにするよ またゴミカス初心者が来たけど
また１から説明して教育しなきゃいけないの？ recHoge1(term,arg...){
dobefore()...
if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
while(term){
dobefore()...
}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
dobefore()...
if(term)recHoge2(term,arg...);
doafter()...
}
loopHoge2(term,arg...){
while(term){
popargstack();
dobefore()...
if(term)continue;
pushargstack();
doafter()...
}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 >>551
>>552
以上のことの何があるか説明してみてよ ttp://nas6.main.jp/Maze.cpp
再帰、ループ、等価迷路 recHoge1(term,arg...){
dobefore()...
if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
while(term){
dobefore()...
}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
dobefore()...
if(term)recHoge2(term,arg...);
doafter()...
}
loopHoge2(term,arg...){
while(term){
pushargstack();
dobefore()...
if(term)continue;
popargstack();
doafter()...
}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 、勘違い訂正 >>554で、
ループ実装が好きなやつはいないと思うんだけどな RubyかPythonで書き直して
C++とかいうゴミいらねーから 「｛Ｃ＋＋規則をかなり抑えてＣライク｝で書かれたソースコード」
のクロスランゲッジなんて、ほぼ、ライブラリの関数名を書き換えるだけだろ あ、あと制御構文もちゃっちゃっと書き換えれば出来上がり それをなぜ最初から簡潔な言語で書かないで
わざわざ冗長したC++・C言語といった言語でドヤァとソースコード貼りつけてくるのか、理解しがたいんだけど
カスレベルの初心者である事を数レスに渡る自己紹介でもしにきたのかね？
アルゴリズムの抽象化でC++とか使う奴はその時点で初心者だって一瞬で分かるって言ってるのに
自分が知恵遅れだと分かってないままの奴が続々現れるからこういう場所は話題がループする 熱烈なC++アンチって速度要求される場面に出会ったことがないんだろな
もしくはフォートラン信者なんだろな オッパイソンはベーシックみたいなもんで非プログラマが使うのに適してるけど、
プログラマが使うには色々しょぼすぎ。
ペイントショッププロのマクロにオッパイソンが採用されたときは、来るかと思ったけど、
それを機に没落していった。
イヌックスの呪いは有名だけど、オッパイソンの呪いもあるのかもしれん。 しかし、エクセルのマクロ使いはザラにいるのに、他のアプリはマクロ使いが
ほとんどいないんだよな。
イーマックソとか言うウンコは置いといて。
CADなんかマクロの使いであると思うのだが。
Autocadなんかウンコ使いが泣いて喜ぶLisp搭載してるのにな。
なんでだ。 とりあえずuyがほんとになにもわかってないことだけわかった ruby知らんがこんな感じだろ
def recHoge2(term,arg...)
dobefore(arg...)
if term
recHoge2(term,arg...)
end
doafter(arg...)
end
end
def loopHoge2(term,arg...)
while term
pushargstack(arg...)
dobefore(arg...)
if term
next
end
popargstack(arg...)
doafter(arg...)
end
end class stack
def initialize
@ret = -1
@crnt = 0
@MAX_STACK = 32768
@stk[MAX_STACK]
end
def pop_stk()
if -1 < crnt
ret = stk[crnt]
crnt = crnt - 1
end
end
def push_stk(v)
if crnt < MAX_STACK - 1
crnt = crnt + 1
stk[crnt] = v
end
end
end
stk = stack
def pushargstack(arg1...argn)
stk.push_stk(arg1)
...
stk.push_stk(argn)
end
def popargstack(arg1...argn)
argn = stk.pop_stk()
...
arg1 = stk.pop_stk()
end def recHoge2(term,arg...)
dobefore(arg...)
if term
recHoge2(term,arg...)
end
doafter(arg...)
end
で、こんだけで済むのに、
ループにしたいからって
スタックのユーザー定義なんて馬鹿だろう 再帰をループにしたかったら
こういうのをいちいち作らなきゃだめだよ
class stack
def initialize
@crnt = 0
@MAX_STACK = 32768
@stk[MAX_STACK]
end
def pop_stk()
if -1 < crnt
ret = stk[crnt]
crnt = crnt - 1
return ret
end
end
def push_stk(v)
if crnt < MAX_STACK - 1
crnt = crnt + 1
stk[crnt] = v
end
end
end プログラミング半年目くらいだろうかコイツは
多く見積もって1年半
それ以上なら今すぐPC捨てたほうが良いレベル Array.push()、Array.pop()があるんね
>>568で済む内容を、ループで書きたかったら↓しなければならない
def loopHoge2(term,arg...)
while term
pushargstack(arg...)
dobefore(arg...)
if term
next
end
popargstack(arg...)
doafter(arg...)
end
end
stk = Array.new()
def pushargstack(arg1...argn)
stk.push(arg1)
...
stk.push(argn)
end
def popargstack(arg1...argn)
argn = stk.pop()
...
arg1 = stk.pop()
end def recHoge2(term,arg1...argn)
dobefore(arg1...argn)
if term
recHoge2(term,arg1...argn)
end
doafter(arg1...argn)
end
↑は、こう↓書き換えられる
def loopHoge2(term,arg1...argn)
while term
pushargstack(arg1...argn)
dobefore(arg1...argn)
if term
next
end
popargstack(arg1...argn)
doafter(arg1...argn)
end
end
stk = Array.new()
def pushargstack(arg1...argn)
stk.push(arg1)
...
stk.push(argn)
end
def popargstack(arg1...argn)
argn = stk.pop()
...
arg1 = stk.pop()
end #同色上書き塗りつぶし
def refill(dest,src,x,y,color,minx,miny,maxx,maxy)
if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
return
end
dest[y][x] = color
#上
if (src[y-1][x] == color) && (dest[y-1][x] != color)
refill(dest,src,x,y-1,color,minx,miny,maxx,maxy)
end
#左
if (src[y][x-1] == color) && (dest[y][x-1] != color)
refill(dest,src,x-1,y,color,minx,miny,maxx,maxy)
end
#下
if (src[y+1][x] == color) && (dest[y+1][x] != color)
refill(dest,src,x,y+1,color,minx,miny,maxx,maxy)
end
#右
if (src[y][x+1] == color) && (dest[y][x+1] != color)
refill(dest,src,x+1,y,color,minx,miny,maxx,maxy)
end
end
↑のループ等価が↓ stk =Array.new()
#同色上書き塗りつぶし
def loop_refill(dest,src,x,y,color,minx,miny,maxx,maxy)
term = 0
while !((x < minx) || (maxx < x) ||(y < miny) || (maxy < y))
dest[y][x] = color
#上
if (term < 1) && (src[y-1][x] == color) && (dest[y-1][x] != color)
term = 0
stk.push(x)
stk.push(y)
stk.push(term)
y = y - 1
term = 0
next
end
#左
if (term < 2) && (src[y][x-1] == color) && (dest[y][x-1] != color)
term = 1
stk.push(x)
stk.push(y)
stk.push(term)
x = x - 1
term = 0
next
end #下
if (term < 3) && (src[y+1][x] == color) && (dest[y+1][x] != color)
term = 2
stk.push(x)
stk.push(y)
stk.push(term)
y = y + 1
term = 0
next
end
#右
if (term < 4) && (src[y][x+1] == color) && (dest[y][x+1] != color)
term = 3
stk.push(x)
stk.push(y)
stk.push(term)
x = x + 1
term = 0
next
end
term = stk.pop()
y = stk.pop()
x = stk.pop()
end
end 再帰関数を無理矢理ループで書くことが
正解だなんてとても思えないんだけど・・・ >>575-577
はdestにcolorが最初から使われていると、それ以上塗れないバグがあるな
ま、いいか destはコピー先だからそういう条件でクリア済みってことで 2色必要だった・・・
srcのx,yからcolor2の連続部分をdestにcolor1で塗りつぶし
#同色上書き塗りつぶし
def refill(dest,src,x,y,color1,color2,minx,miny,maxx,maxy)
if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
return
end
dest[y][x] = color1
#上
if (src[y-1][x] == color2) && (dest[y-1][x] != color1)
refill(dest,src,x,y-1,color1,color2,minx,miny,maxx,maxy)
end
#左
if (src[y][x-1] == color2) && (dest[y][x-1] != color1)
refill(dest,src,x-1,y,color1,color2,minx,miny,maxx,maxy)
end
#下
if (src[y+1][x] == color2) && (dest[y+1][x] != color1)
refill(dest,src,x,y+1,color1,color2,minx,miny,maxx,maxy)
end
#右
if (src[y][x+1] == color2) && (dest[y][x+1] != color1)
refill(dest,src,x+1,y,color1,color2,minx,miny,maxx,maxy)
end
end recHoge2(term,arg1...argn){
dobefore(arg1...argn);
if(term)recHoge2(term,arg1...argn);
doafter(arg1...argn);
}
この↑再帰関数を無理矢理
loopHoge2(term,arg1...argn){
while(term){
pushargstack(arg1...argn);
dobefore(arg1...argn);
if(term){continue;}
popargstack(arg1...argn);
doafter(arg1...argn);
}
}
ループで書くのはpushargstack()popargstack()書くのもだし
再帰関数でreturnされた時の箇所で
制御をdoafter()に飛ばすように考えるのもめんどくさい
つまり、再帰関数の構造化の部分までなんでわざわざ
コーディングする必要があるのか謎 そうだね、グリーンだね。
任意の再帰はスタックを使えばループに書き直せるし、任意のループは末尾再帰で書き表せるけど
書きやすい方で書いたら良いんじゃない？
配列を舐めるだけのループをわざわざ再帰で書く必要はないし、
二分木を舐めるだけの再帰をわざわざループで書く必要はない。
勿論例外は幾つもあるけどね。 >>589
時間とフィンガーポイントを無駄にしない為に今すぐ2chから立ち去るんだ！
さぁ早く！ http://kakaku.com/item/K0000791258/
これを使ってるけど打ちにくい
隙間にゴミが入りにくいキーボードで何か探してくれれば長文レス出来るけど
ゲームもやるから同時押しが出来ないキーボードは使えないんだよ
バッファローのこのキーボード系列は
何故かゲーミングキーボードでもない癖にかなりの同時押しが出来る
お前らもこれくらい社会の役に立ってくれ tail callはrecursive callと直行する概念だと理解してないのが何人かいるな 読みやすい方で書いたらいいんちゃうの？
無理にループにしてソース長くしてテスト項目増やす奴の気がしれんわ 取り敢えずutがカスだってのは旗から見てわかった
補足しておくけどループで済むものを再起にしろと言ってるわけではないからな そりゃrecursiveじゃないtail callなんざ幾らでもあるわ 仮にもプログラマならHHK使ってます自慢くらいしろよっていう
そういう俺はreal forceだけど。 自分はプログラマじゃないんだよ
目的を最高効率で達成する事を念頭に置いてるスクリプトキディだ
そして複数人でプログラムを組むときに必要なノウハウなんて持ってない
そもそも自分はそういう事をしなくて良いから、生きてく上で必要無い配慮だから
周りが読みにくいとか知った事ではないし
身分がちげーんだよカス （他人の作った）スクリプトを使うしか能の無いお子様
正しく自分のこと理解してるということでいいのかもしれないですね。 正しく自分を理解していたら、あんなバカな生態を晒し続けるわけが無い
スクリプトキディとは、他人の作ったスクリプトでいたずらしてはしゃぐお子様の事だね 誤送信
2ちゃんに書き込んでる地点で効率最悪といえる 数学的な再帰定義関数は好き
プログラムの再帰定義は多少罪悪感が >>605
読みやすさを考慮しなくていいとか言うなら、ソースあげんなksが まともなプログラムは再帰使わないて
Javaじゃ標準でhashでもvisitorでも使ってるやん
初心者かな？ >>615
ウェブサイトがハッキングされるのはそのせいかもしれませんね。 Haskellを知ればJavaなんぞ子供のおもちゃにも及ばない。 いや、もしかしたら
データベースを扱うのに困難を伴うゴミ人間って意味かも もしかして、もしかしてだけどさ、Haskelのこと言ってるんじゃね？ Haskellほどデータベース扱いやすい言語も少ないからそれはない 世界一のデータベースを持つと言われるGoogleがHaskellで動いているくらいだからね。 Haskellって実用で使われてんのかｗ
おもちゃかと思ってたわｗ イッテヨシとかギコはにゃーんとかもう死語なんだろうな。
ゴルァはまだありかな。 ヌルポにはガッっていうのはなぜだったのか理由がいまだに判らないので
香具師にどう反応すればいいのかも判らない >>633
ぬるぽにかぎらず、例外発生したら、ガッ！ >>633
NullPointerExceptionをぬるぽと呼ぶスレだかなんだかいうスレタイのスレが立った2分後に
2が1にガッしたから
だった筈 ガッはガッチャの略だろ。 ガッチャマンでお馴染みのガッチャはI have got you.の略で捕まえたとかの意味。 でもアメリカのドラマ見てると了解するときにガッチャ！って言ってるよね。
特にチャーリーズエンジェルのカエル顔が（別のドラマでも）言ってるような気がする。 それ再帰のせいじゃなくてもともと難しいアルゴリズムなんじゃ 同じコードでも言語やバージョンの違いで即死する可能性があるのがネック。
可能ならwhileにするよ。
どうでもいいスクリプトなら木にしないけど。
べ、別に再帰関数苦手なわけじゃないんだからね！ 再帰否定派は生きるのがつらいんだよ
いつも周りのもの何もかも否定してるよ 無限か有限かを判別するだけでも難しい再帰コールが簡単に作れるからな 例えば再帰を使えばC++149文字で数学的に非常に判別が難しいコードが作れる
ステップ数がF_φ_ω(0) (n)のオーダー
再帰を使わないともっとずっと必要な文字数は増える つまり再帰を使うと簡単に分かりにくいコードが書けてしまうというアピール
アホなのこいつ？ 適材適所
まぁ、ループは現代ではほとんど高階関数に置き換えられてはいるが 再帰、ループ、高階関数は互いに別カテゴリーの概念だけどな。 >ループは現代ではほとんど高階関数に置き換えられてはいるが
mapとかfoldって言いたいの？ 最近の言語は分かり易いから好んで使う人多いみたいだね。
俺はダメだわ。単純な再帰でもアセンブラ時代の間接修飾と再帰を混合で使ってたときのトラウマが・・・ >>665
ループ，というよりは map によるメモ化を先にするべきかと思う アッカーマンメモ化はやめとけ
メモリ使用量がシャレにならん。
小さい引数ならいいけど。 と思ったけどスタック消費量は逆に減る？
よくわからんくなってきた。 メモ化とかメモリリークしてるに等しい欠陥技術でしょ。 >>672
fjの昔からの議論をここで蒸し返しますか？ 再帰というソフトにはスタックというハードがあるけどほかのソフトをハードで実装するのはどうなの？
ＧＣとかハードで実装してまったくフリーズなしに出来ないの？ int main(){return main();} とあるRubyスクリプトだけどこれと等価のＣ書けんの？
$f=lambda{
print "f";
return $g
}
$g=lambda{
print "g"
return $f
}
a=$f
10.times{a=a.call} rubyはcで書かれているんやで知らんかったやろ？ そういう等価じゃなくて文法的にというか。
Cだと$fと$gの型をどうしていいかわからん。 グローバル変数じゃなくてもこれでいけるっぽい
g=nil
f=lambda{
print "f";
return g
}
g=lambda{
print "g"
return f
}
a=f
10.times{a=a.call} typedef void *(*F)()でいいやんけ これでいけるやろ
#include <stdio.h>
typedef void *(*F)();
void *f();
void *g();
void *f()
{
puts("f");
return g;
}
void *g()
{
puts("g");
return f;
}
int main()
{
int i;
F func;
func = f;
for (i = 0; i < 10; ++i)
func = func();
return 0;
} g++だとエラーになるんだが。
コンパイラは何で確認した？ なんでいきなりg++やねんw
これ以上はcの質問スレでもいって聞けタコ 通るわアホw
つーかそんなレベルでよくその質問出来るなお前 だからコンパイラは何つかったんよ。
こっちでも確認するから教えれ。
有料コンパイラだったら諦めるけど。 >>690
ふーむ確かに。
コンパイラがC++だといかんの？ しかしvoid * はなにか負けたような気分になるなｗ キャストが嫌ならちゃんと型定義すればいいじゃん
と思ったがちゃんとやるには自己参照型定義みたいなのが必要になるのか
Cでそれってできるのかな
関数型Fのポインタを返す関数型をFと定義 voidにキャストがどうのって、rubyでコード書くような奴に言われてもなぁ。 >関数型Fのポインタを返す関数型をFと定義
これ定義できる静的型言語ってあるの？
それとも本質的論理的に矛盾した型であって、どうやっても定義できないの？ Forループは正直見た目が汚らしい
場合にもよるんだろうけど、再帰で書けるならそっちのほうがコードが綺麗になる なんでルビイなんだ？
ハスケルバカならまだわかるが。 Y = λf.(λx.f (x x)) (λx.f (x x)) #include<stdio.h>
char*s="#include<stdio.h>%cchar*s=%c%s%c;main(){printf(s,10,34,s,34);return 0;}";main(){printf(s,10,34,s,34);return 0;} ピクセルシェーダーで再帰関数使えるようになるのはいつだろうか CPUがGPU化するのが先かGPUがCPU化するのが先か。
まあ超並列プログラムは憧れるけどね。 main = putStrLn $ q ++ show q where q = "main = putStrLn $ q ++ show q where q = " 超並列はどうしてもデータレースが怖いからハードウェアトランザクションは必須だな ツクツクボウシの鳴き声を一番正確に表せた奴が優勝 [無断転載禁止]©2ch.net
1 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:01:56.231 ID:EVnE4ji20
ツクツクボーシッ！！！！ツクツクボーシッ！！！！ツククツ、ツククククククク……！！！
ｱｯ ヴィーナス！！！！ ヴィーナス！！！！ヴィヴィヴィヴィッ！！！！！
8 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:05:05.180 ID:rZ8gq0650
ツクツクホーシ！ツクツクホーシ！ッツクツク、ツクツクホーシ！
ッ！ツクツクヴィーヨー！ツクツクヴィーヨー！ツクツクツクツクアアアアｱﾞｱﾞｱﾞｱﾞｱﾞ…天
12 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:24:50.425 ID:SYCMGSQFa
ツクツクウィーヨーンｗｗｗｗｗｗツクツクウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗあああああああああああああああ あ！！！！！！！ GitHubで匿名通信（Tor、i2p等）ができるBitComet（トラッカーサイト不要でDHTだけで日本語検索可能）
みたいな、BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al
ちなみにオイラはCovenant(純粋P2Pのファイル共有ソフト)の完成が待ち遠しいプログラミングできないアスペルガーｗ
q 匿名通信（Tor、i2p等）ができるファイル共有ソフトBitComet（ビットコメット）みたいな、
BitTorrent（Covenant）が活発な情報交換・交流コミュニティでオープンソース開発されています（プログラマー募集中）
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise氏）がそういう人と話したいそうなので、よろしければツイートお願いします<(_ _)>
https://twitter.com/Lyrise_al
ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできない情報発信好きアスペルガーｗ
The Covenant Project
概要
Covenantは、純粋P2Pのファイル共有ソフトです
目的
インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します
特徴
Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)
接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
ｔ 眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの？ チューリングマシンになる
証明：以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。
# ツッコミ待ち グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。 女性限定、恋愛相談サイトオープン。
4000名のイケメンカウンセラーが在籍中♪
自己紹介動画はいつでも見放題です！
メンガ って検索してください
※本当のサイト名は英字です >>719
そう言う時期が俺にもあったな...（遠い目） 再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや 再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない import Data.Function (on)
import Data.List (concatMap, groupBy)
main =
let (f:r) = mypi 2 4 1 12 4
s = slice 5 $ slice 10 $ concatMap show r
in putStrLn (show f ++ ".")
>> putStr (unlines $ map unwords $ take 200 s)
slice :: Int -> [a] -> [[a]]
slice n ls = let q = concatMap (replicate n) [0..] :: [Int]
in map (map snd) $ groupBy ((==) `on` fst) $ zip q ls
mypi :: Integer -> Integer -> Integer -> Integer -> Integer -> [Integer]
mypi k a b a1 b1 =
let p = k * k
q = 2 * k + 1
a' = a1
b' = b1
a1' = p * a + q * a1
b1' = p * b + q * b1
loop a a1 d d1 =
if d == d1 then
d : let a' = 10 * (a `rem` b' )
a1' = 10 * (a1 `rem` b1')
in loop a' a1' (a' `quot` b') (a1' `quot` b1')
else
mypi (k + 1) a b' a1 b1'
in loop a' a1' (a' `quot` b') (a1' `quot` b1')
えんしうりつを100まんけたひょうじする $ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた 深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。 まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど flattenがあると再帰書かなくて済むことがまれによくある。 超簡単なハノイの塔のコードを
理解出来ない奴らばかり
俺様ステキ
再帰は楽しい ハノイの塔って最初誰が考えたんだろなｗ
まさに再帰のための問題だよなｗ >>737
エドゥアール・リュカ/1800年代後半 連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ？ 数学のように条件を書くだけで処理が書けるのは楽しい >>741
では
これの値を教えてください
lim[n->∞]sin(πen!)
わりとまじです void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。 昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ int main()
{
return main();
} 再帰は面白いと思ってた時期もあった気がする。
ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか ただのループでスタックオーバーフローの心配はないからなぁ x 再帰はループの一つ
x ループは再帰の一つ
o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる >>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。 再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する >>758
あー、ループあるな。そういう意味では。
すまんかった。 >>755
再帰と同じようにループを実装すればオーバーフローしますけど。
>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。
ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。
まずこうゆうときは、E（電力）あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。
再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。 >>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ？ 分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね 再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。 スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。 >>767
int main(){ return main(); } 簡単です C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに >>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。 >>770
C++で、クラス内に関数を定義すりゃいいだけ >>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。 >>770
なるほどね，コンパイル単位内だけで末尾再帰を保証するわけだね >>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か 木構造をループで辿りたいときってスタック使わずにできる？ 辿るだけ（構造を保持しなくていい）ならできるでしょ
たとえば全てのアドレスを出すだけとか スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。 ツリーだってメモリがツリー状になってる訳じゃない罠 質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない
意味不明 >>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな >>786
ニーハオ！
モドル サキ ハ ドコニ キヲク シマスカ？ ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。 馬鹿には永遠に判らんだろうけど。 情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。 誰かの口真似したのかもしれないけどそれは完全に間違ってますよ >>796
Prologですから再帰述語で関数ではありませんが、
repeat :- 割り込みあり,!.
repeat :- repeat.
の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。 すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。
repeat.
repeat :- repeat. >>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。 >>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。 >>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。 好きか嫌いかで言ったら好きだ
趣味以外では使わないけど 再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの？
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの？ >>806
ループで実現したときはスタックに積まれない。 >>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒 抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。
抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。 >>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか？ すみません。最後
こういうことを「実体」というのではないか？
です。 >>813
根本的には処理もデータも区別なく実体ってことでしょ。
ループ自体も関数自体も実体。 継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の１割に満たないんだろうな。 物自体の実在性を議論してんのかよ
やっぱ再帰って難しいわ 私は再帰の塊のようなプログラムを作ったことがある。
DirBaseだ。
起動後のウィンドウにエクスプローラからファイルやフォルダを
ドラグ＆ドロップするだけで簡単にツリーができる。
DirBaseで検索すれば、ダウンロードできる。 競プラではforループが盛んらしいが、言語開発者としては再起の方が使って欲しい
ソースは俺が今朝見た夢 >>819
ん？setjmp/longjmp のことですか？ (数値計算を主体とする)関数では使わないけど、
再帰ルーチンで使用頻度が激しいのは、外部記憶装置を含めた初期化ルーチン。
一つのルーチンで、内部記憶(主記憶装置)と外部記憶(HDD等)の出入りを管理している場合に、
初期化ルーチンで外部記憶が存在しない場合には、ルーチンで保存している定数を読みだして、外部記憶に保存する。
初期化ルーチンからの定数の読み出し・外部への保存が再起処理。
初期化ルーチン以外では使わない手法。
分割して作成すると、何年か後に見直した時に、どのように初期化しているのかわからない、という事態になることが多発したので、
初期化が必要な場合には、このような手法で同一ルーチン内に収めるようにした。
もっとも一番利用頻度の高いのは、Winでは、ダイアログボックスのプロシージャ。再起の塊で、何をしているのかわからなくなってくる。 再帰プログラムは関数の呼び出しで積みあがるスタックを配列とみなせば、ループアルゴリズムそのものだ。 ファイルやフォルダ、ダイアログやウインドウは階層構造で構成されるので、再帰プログラムを使うのが一般的だ。 再帰って何?って頃から普通に再帰使ってたからなあ。
自分自身を呼び出せば良いじゃんみたいな。
高校で数列とか演繹法が得意だったせいかも。
自然に使ってた。 再帰云々言ってるのは大昔のFORTRANとかCOBOLを使ってた人ぐらいじゃないのかな
あと組み込みとかでスタックサイズが厳しい環境で組んでるとか 再帰プログラムの基本はスタックにデータを入れ積み上げていく過程と、スタックからデータを取り出しスタックをクリアしていく過程の二つの動作しか基本的にない。
データを取り出したら、そのデータを使ってプログラミングされた処理を実行する。スタックはデータを貯めることと同時に処理の順番を決めている。再帰のプログラミングには二つの概念が必要だ。 javaで再起処理書いたらガーベッジコレクションが掃除してくれるもんだと思ってたけど違うの？
十年前の記憶だから曖昧ですまない
cpu使用率が100%になるけど影響ないから使ってます〜って顧客に言われたのを思い出したもんやで 僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
980U0 今時スタックオーバフローぐらいでOSは死なないから大丈夫 再帰アルゴリズムはなるべくライブラリで隠蔽して欲しいな。
自分で書くのはまだしも他人の再帰コードを読むのはかなり嫌。 再帰関数と言えばアッカーマン関数とかたらい回し関数などが
有名ですが他にも何かある? 174 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:04:12.40 ID:N77Q/1ZeM
＞ドラゴンクエストの世界観が全く反映されていないような印象
ド ラ ゴ ン ク エ ス ト と は 何 か ？
ドラゴンクエストとは何かを問い続けるのが、終わらないドラゴンクエストだろう？ 違うか？
2 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:42:40.97 ID:N77Q/1ZeM
再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。
この例のおかげもあり、はじめは再帰関数なにそれ状態から、最後はしっかりと実装できるようになりました。再帰関数はPythonで実装しています。
https://qiita.com/jumpyoshim/items/20e6b5e70efa466699b4 再帰関数『終わらないドラゴンクエスト』
ドラゴンクエストとは？（）{
ドラゴンクエストとは？（）
} def DQ(n)
puts "DQ #{n}"
DQ(n+1)
end >>1
好き嫌いの問題じゃないと思うが、理論上再起かそれと同等の内部処理履歴を残さないと実現できない処理なら、使うだろう
再起にならざるを得ない具体的な数学（科学）的な条件は忘れたが、けっこう複雑な処理じゃない限り再起じゃなくても実現できたように思う >>858
「再起」じゃなくて「再帰」ね
スタックを使えば、つまりメモリを余分に使用することを認めれば
再帰はループに書き換えることができるから
再帰でなければ出来ないことは原理的に存在しない
更に言えば関数を受け取りまた返す高階関数があれば
いわゆる不動点演算子に相当するものが書けるので
関数の再帰的定義は不要になる 論理的にはクイックソートよりマージソートが好き。
実用性はクイックソートが上なのかな？ >>859
>再帰はループに書き換えることができるから
そのループ再帰だよ・・・
再帰の問題点もそのまま同等に引き継いでるよ・・・ ループも不動点演算子も再帰関数の実装の仕方でしかない リストに対してはクイックソートやマージソートより選択ソートや挿入ソートのが速かった。
ケースによって使い分けるために色んなソートがあるんだなと実感した。 >>861
ループと再帰とは違うよ
更に言えば高階関数があればループも再帰も必要ない
不動点演算子もループも再帰だと言うのはナンセンスだ
それは「再帰と同じだ」と君が思うものを再帰と呼ぶ、と主張しているに等しい
こんな君だけの主観による再帰の定義では議論にならない チューリング完全なんだからどの言語でも一緒、という暴論と同程度に「ループと再帰は同じ」も暴論
コンピュータからみた話じゃなくて、プログラムを書く人にとってループと再帰が同価値なのかが問題になる
自分は、複雑でも読み溶ける再帰の方が好き。ループが複雑になると、どの変数がいつのどの値を持っているのか追いきれなくなる
再帰で同程度に複雑な処理を書くと、引数の数やら名前からすぐにヤバイ臭いがするんでそんなに腐らない 末尾再帰にすると結局for文とやってることが一緒になる モナドな再帰(IOモナドやリスト->リストな再帰)は単純な再帰でもスタック消費しない。
繰り返しコードの単純さは再帰>末尾再帰>=ループ。 非同期処理の終了を待って、次の繰り返しを行う
再帰でなければ書けない >>871
非同期処理の終了はイベントやコールバックで通知されるものとする
終了を待つ同期プリミティブは存在しない
Javascriptだとこれが普通で、繰り返しでは書けない async/await が JavaScript の新しい仕様として入ったのも知らんのか await/asyncの仕組みを知らないと見える
それ使って、繰り返しで書いてみなよ やっぱ、await/asyncで出来そうな気がしてきた >>867
違うよ
柴犬にこっちは太郎でこっちは次郎だから別の犬だ、と言ってるのと同じ 再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。
再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。
普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する >>881
そらまあ再起が辿るイメージ図は全てツリーって名称付けれますし ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい >>883
ミニマックス法かアルファベータ法だろ？ マイコンだとスタックが1桁とかだから再帰書いた瞬間に死ぬ ルネサスのRL78/G10はRAMが128Byteしかないらしいな λf . (λx . f (x x)) (λx . f (x x)) ループで書くと出現する余計な変数がなくなるのが再帰のメリット >>889
？
kwsk
ループ変数は再帰関数でも必要なのでは？ どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど 再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。 CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが 今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど >>890
要らない
/* n の階乗を求める */
int fact(int n)
{
if(n==0){
return 1;
} else {
return fact(n-1);
}
}
実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。 おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺（泣） くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ 最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ？ >>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない >>8
ループと再帰の能力は同じです
かなり古い計算論の結果です >>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが
ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました >>902
scheme の継続渡しに関係しますか？
キーワードありがとうございます >>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで すき
しかし再帰絶対書かないマンが思いの外多くて草生えるわ
末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん
再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変 スタックとヒープは別物
共有してるアーキテクチャもあるが ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。 >>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね 再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする
こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A 何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ レス数が900を超えています。1000を超えると表示できなくなるよ。
