なあ、再帰関数好きな人いる？ [転載禁止]©5ch.io
レス数が1000を超えています。これ以上書き込みはできません。
0001名無しのプログラマ
2015/08/09(日) 17:46:33.69ID:Icb40LOY皆から敬遠されてる気がする
0002デフォルトの名無しさん
2015/08/09(日) 17:47:17.56ID:FkAVUmEu0003デフォルトの名無しさん
2015/08/09(日) 20:07:41.86ID:+GEmkdAw0004デフォルトの名無しさん
2015/08/09(日) 20:50:06.80ID:Q/67NMOwプログラマが末尾再帰にしなければいけないっていうのが
超絶ダサいと思う
0005デフォルトの名無しさん
2015/08/09(日) 22:53:43.45ID:PuCXERZpなれるとむしろループが書けなくなる
0006デフォルトの名無しさん
2015/08/09(日) 23:20:43.14ID:cELMilqM0007デフォルトの名無しさん
2015/08/09(日) 23:21:40.87ID:MmR8qrNe0008デフォルトの名無しさん
2015/08/10(月) 00:11:12.37ID:+JcaMZeA「普段は Lisp や Prolog を使ってるのかもしれない」くらいの想像はしてあげたいものだ。
0009デフォルトの名無しさん
2015/08/10(月) 01:03:21.60ID:3agS2rXWループで簡単に書けない再帰はある。
再帰でおk
>>6みたいなのはHaskell触って発狂するといいよ。
0010デフォルトの名無しさん
2015/08/10(月) 05:19:14.46ID:o4/Calnz0011デフォルトの名無しさん
2015/08/10(月) 09:23:09.48ID:/lbZh+eGメモリ取り過ぎ
再帰の回数が多ければプログラムが落ちる
実用的なプログラムを書くなら再帰は厳禁
再帰は下らないネタ処理
ループなら１万回でも１億回でも高速に処理できる
0012デフォルトの名無しさん
2015/08/10(月) 09:31:04.36ID:DXpO9Rx+0013デフォルトの名無しさん
2015/08/10(月) 16:47:13.89ID:+JcaMZeA他には Concurrent処理のカレンちゃんとか。
0014デフォルトの名無しさん
2015/08/10(月) 17:27:22.90ID:rm8AF5t7今日もスタックを溢れさせて先輩に罵倒されて会社辞めろって言われたの
そろそろ録音データもそろったし、パワハラで訴えまくって一攫千金よ
0015デフォルトの名無しさん
2015/08/10(月) 21:06:03.71ID:CK/F4dHF何も考えてないっていってるようなもの
0016デフォルトの名無しさん
2015/08/11(火) 00:30:45.20ID:EeLTxYYq彼は確実に君より賢いと思うよ。
0017デフォルトの名無しさん
2015/08/11(火) 03:14:25.43ID:SPQSl72c>再帰はパフォーマンスが悪すぎ
>メモリ取り過ぎ
>
>再帰の回数が多ければプログラムが落ちる
>
>実用的なプログラムを書くなら再帰は厳禁
>再帰は下らないネタ処理
釣りなの？
0018デフォルトの名無しさん
2015/08/11(火) 04:16:54.02ID:1RwbGpvK0019デフォルトの名無しさん
2015/08/11(火) 12:31:37.30ID:BomPGBV/0020デフォルトの名無しさん
2015/08/11(火) 15:13:45.87ID:pr+lgJy5スタック浪費して実行アド変えるデメリットが理解できてないやつはヤヴァすぎ
玩具言語で玩具作ってるなら好きにすればー
0021デフォルトの名無しさん
2015/08/11(火) 15:25:06.46ID:TpmJtB/J0022デフォルトの名無しさん
2015/08/11(火) 17:15:37.10ID:W3jiVQE7そんな犯罪者はとっとと首にしなくちゃ。
0023デフォルトの名無しさん
2015/08/11(火) 17:42:06.75ID:cL5jCBIN0024デフォルトの名無しさん
2015/08/11(火) 18:24:05.65ID:Ghx6BuLg↓
（意味なく）再帰にしたい！
↓
再帰にするとスタックがー、関数呼び出しがー、どうのこうの
↓
末尾最適化される再帰にすればいいんだぜ！フフン
↓
末尾最適化されるような再帰コードを書く
↓
コンパイラがループの実装に戻す
結論
人間がループを再帰に変換し、
コンパイラが再帰をループに戻すという無駄！
0025デフォルトの名無しさん
2015/08/11(火) 20:07:51.21ID:SPQSl72c無理にループを書き換えるのは意味ないね
0026デフォルトの名無しさん
2015/08/11(火) 20:55:40.81ID:I9e7/X970027デフォルトの名無しさん
2015/08/11(火) 21:08:11.97ID:s8tCNx0W0028デフォルトの名無しさん
2015/08/11(火) 21:12:51.45ID:I9e7/X970029デフォルトの名無しさん
2015/08/11(火) 21:58:02.48ID:EeLTxYYq0030デフォルトの名無しさん
2015/08/11(火) 22:20:09.41ID:C3iuhTExYou must die
0031デフォルトの名無しさん
2015/08/11(火) 22:22:14.08ID:p1BzFXAwそのときもスタックの深さが管理出来ないようにはしない
0032デフォルトの名無しさん
2015/08/11(火) 22:59:04.11ID:hIAJ5PwO0033デフォルトの名無しさん
2015/08/11(火) 23:39:17.34ID:BomPGBV/理解が早いのは完全に地頭がいいだけじゃね？
0034デフォルトの名無しさん
2015/08/11(火) 23:47:24.15ID:6ebVNzRe0035デフォルトの名無しさん
2015/08/12(水) 00:19:33.18ID:UEtymV4nそして、プログラムなど知らない他人も
その対象を直感的に再帰にだと思うであろうものは
再帰にする価値はあるが、
そうでないものは、ループが良かろうよ。
0036デフォルトの名無しさん
2015/08/12(水) 01:27:14.94ID:Pci5W2YJ>>= や map , foldで書けるならそっちで書くべし
0037デフォルトの名無しさん
2015/08/12(水) 09:02:17.34ID:VcXSwt9vこれを実際のアプリ開発で使っちゃいけないって分からないアホは、超危険で社会に有害。
一生プログラミングの問題を解いてるだけで引きこもっててね。
0038デフォルトの名無しさん
2015/08/12(水) 09:38:26.25ID:CSXYMy4+0039デフォルトの名無しさん
2015/08/12(水) 09:51:11.59ID:uNqySeoG0040デフォルトの名無しさん
2015/08/12(水) 11:49:56.16ID:TAHn/fs+fold使う
0041デフォルトの名無しさん
2015/08/12(水) 12:17:54.41ID:KQiec6kq> 理解が早いのは完全に地頭がいいだけじゃね？
慣れの問題でしか無い。
プログラミング技術の学習段階はこんな感じ
1. 技術を知らない（再帰を知らない）
2. 技術があることをするが使えない（再帰を知っているが使えない）
3. 技術がわかる。（再帰がわかる）
4. なんでもその技術で解こうとする。（何でも再帰を使おうとする）
5. 技術を使うのに適切な場合とそうでない場合の区別がつく。（適切な場合に再帰を使う）
技術がわかった＝技術をマスター ではなくて、必ず4の段階を通る。
で4の段階で止まってしまうと、技術使える俺は頭いいとか言い出すｗ
0042デフォルトの名無しさん
2015/08/12(水) 12:52:34.13ID:Pe25qO3w普通に処理できる凡打にダイビングキャッチで飛びつく
俺が一番ダイビングキャッチが上手いんだ
誰よりも綺麗にローリングを決められる
だから俺が一番野球が上手いんだ
0043デフォルトの名無しさん
2015/08/12(水) 14:53:32.12ID:ALDJfVhAScalaはともかく、OCamlは再帰使えないと話にならない
ループを使わせないためにforとwhileは使いにくくしてある
それにしても再帰がネタだとか言ってる奴は
ふだん何を書いているのだろうか…
0044デフォルトの名無しさん
2015/08/12(水) 15:04:08.55ID:VrhF+ys7そんな言語一般的な業務では使われないよ
0045デフォルトの名無しさん
2015/08/12(水) 16:34:31.46ID:ALDJfVhAそうですか、よかったですね
0046デフォルトの名無しさん
2015/08/12(水) 17:33:35.71ID:7e8ZJE3m勝つことだけが目的の頭がおかしい人は無視しましょう。
0047デフォルトの名無しさん
2015/08/12(水) 18:39:35.26ID:xMooa+yrC++がマイナーと言われたらもうしらん
0048デフォルトの名無しさん
2015/08/12(水) 18:42:06.21ID:9kD/QFWj0049デフォルトの名無しさん
2015/08/12(水) 18:53:02.68ID:dUzyVUNe0050デフォルトの名無しさん
2015/08/12(水) 18:58:06.19ID:jdzlUPnwそれはやめたほうがいいよ。
0051デフォルトの名無しさん
2015/08/12(水) 19:14:48.75ID:JsRAlNhV再帰下降パーサ自体、セキュリティ上の観点から安易に採用するべきではないとされてる。
海外では常識になってきてるけど、国内で浸透するには20年くらいかかるかもしれんね。
0052デフォルトの名無しさん
2015/08/12(水) 19:22:06.01ID:YIqOZZQS業務では再帰使うことは滅多と無いかもしれないが、理解することでプログラムの重要な考え方が身につくと思う。
決してネタなんかじゃないｗ
0053デフォルトの名無しさん
2015/08/12(水) 19:43:06.19ID:KQiec6kq俺は>>41でいう5の段階だから、当然知ってるよ。
再帰を知ったのは高校の時ぐらいかな？
指定ディレクトリ以下のすべてのファイルを処理する必要があって
必然的に知る必要があった。そこからもう10年以上たつし。
最近ではMIMEメールのパースとか、連想配列の
全ての値の処理とかで使ったかな。
再帰を使うことはめったにない。そしてミスをしやすい所でもある。
だから再帰を使うときは、再帰を考慮しなくていい形に置き換えるようにしている。
つまりJavaScriptでいうmapやreduceの形にする。再帰部分と処理部分に分けて再帰部分を隠ぺいする。
通常書くのはコールバックで呼ばれる処理部分のみ。
そうすることで可読性も大きく上昇する。
普段はやはり再帰のコードは書くべきじゃないよ。
可読性悪いからね。
0054デフォルトの名無しさん
2015/08/12(水) 20:12:28.34ID:x2olvrlJ0055デフォルトの名無しさん
2015/08/12(水) 20:19:49.72ID:TAHn/fs+逆にfilterMみたいな高階関数の実装みてすぐ理解とか難しそう
0056デフォルトの名無しさん
2015/08/12(水) 20:33:35.39ID:KQiec6kq例えば連想配列の全ての値を×10したいなら、これだけでいい。
※JavaScript
recursive(obj, value => value * 10);
これだけで済むように（内部で再帰を使って）recursiveという関数を作る。
作った関数の中身はもう見る必要はないからあとはこれだけのコードで済む。
このコードは、その場で再帰のコードを書くよりも明らかに可読性が高い。
なので可読性が悪い再帰のコードは、さっさと隠蔽化してしまって
普段は再帰を意識しないようにするということ。
で所で話は変わるが、recursiveという名前をつけたが、
このように連想配列の全ての値を処理するという関数、
なにか適切な名前ない？ 他の言語だとありそうなものなんだが。
0057デフォルトの名無しさん
2015/08/12(水) 20:34:03.13ID:KQiec6kq0058デフォルトの名無しさん
2015/08/12(水) 20:39:45.65ID:TAHn/fs+0059デフォルトの名無しさん
2015/08/12(水) 20:45:15.71ID:JsRAlNhV0060デフォルトの名無しさん
2015/08/12(水) 20:46:34.22ID:TAHn/fs+ScalaだとmapValuesって名前だな
アンダースコアみたいなjsライブラリではオブジェクトでもmapだ
0061デフォルトの名無しさん
2015/08/12(水) 20:47:57.61ID:KQiec6kqmapは一般的には配列から配列の変換でしょ？
ツリー上の構造まで対応しているmapとかあるの？
余談けどmapって写像のことだよね。
数学勉強してるとプログラム言語みたいで楽しいよね。
代数学の体とか束とか。
体は演算子オペレータが定義されたクラス
束はComparableインターフェースを持ったクラス
とかさ。（↑結構適当にいってるので突っ込まないで）
こういう風にプログラム言語と結びつけて
解説している記事ってあまりないよね。
プログラミングなら知識あるんで、こっち方面から
数学を解説してくれるとわかりやすいのにｗ
0062デフォルトの名無しさん
2015/08/12(水) 20:48:29.50ID:ALDJfVhAtraverse
0063デフォルトの名無しさん
2015/08/12(水) 20:51:09.08ID:KQiec6kq俺はlodashの方が好みなんで（どうせ同じだろうから）こっちで話をすると
https://lodash.com/docs#map
確かにlodashのmapはオブジェクトにも対応しているようだ。
これはちょっと見落としていた。だけどこうなるみたいだけど？
function timesThree(n) {
return n * 3;
}
_.map({ 'a': 1, 'b': 2 }, timesThree);
// → [3, 6] (iteration order is not guaranteed)
俺の希望としては { 'a': 3, 'b': 6 } こうなってほしい。
0064デフォルトの名無しさん
2015/08/12(水) 20:51:09.67ID:JsRAlNhVHTMLを配列に変換して操作する処理をちょっと書いてみたよ。
0065デフォルトの名無しさん
2015/08/12(水) 20:53:32.81ID:KQiec6kqそれがあったか。
ディレクトリトラバーサルとか普通に言えるのに
思いつかなかった。
その単語が使われてる言語やライブラリってありますか？
0066ID:KQiec6kq (連続書き込み規制対策で変更）
2015/08/12(水) 20:55:24.34ID:S25mloU+lodashにmapValuesあるやん・・・
https://lodash.com/docs#mapValues
なんで俺気づかんかったんや・・・
0067デフォルトの名無しさん
2015/08/12(水) 20:59:28.34ID:S25mloU+_.mapValues({"a":1, "b": 2, "c": {"d":4}}, n => n*3)
{ a: 3, b: 6, c: NaN }
0068デフォルトの名無しさん
2015/08/12(水) 21:08:39.02ID:ALDJfVhAHaskell
0069デフォルトの名無しさん
2015/08/12(水) 21:12:50.83ID:S25mloU+ありがとう。
こういう原始的に近い処理をする関数は
いい英単語が中々思いつかんから困る。
0070デフォルトの名無しさん
2015/08/12(水) 21:20:31.80ID:TAHn/fs+0071デフォルトの名無しさん
2015/08/12(水) 21:51:03.50ID:DorBHKZm> 可読性の悪い再起とかあるの？
再帰に限らず頭の悪い人間が書いた代物は可読性が悪いケースが多い
プログラムコードに限らず文章でもね
聡明な人間が書いた再帰コードは頭の悪い人間が書いた同じ目的を果たす反復コードよりも可読性に優れている
0072デフォルトの名無しさん
2015/08/12(水) 22:24:59.02ID:S25mloU+データそのものが再帰であるのだから
それを扱うコードも再帰を使ったほうがわかりやすい。
だけどデータがリスト構造なだけなら
普通にループを使ったほうがわかりやすい。
適切に選ぶべきだ。
0073デフォルトの名無しさん
2015/08/12(水) 22:49:42.67ID:JsRAlNhV0074デフォルトの名無しさん
2015/08/12(水) 23:00:43.40ID:ALDJfVhA>だけどデータがリスト構造なだけなら
>普通にループを使ったほうがわかりやすい。
んなわけねーだろ
普通に再帰使うわ
0075デフォルトの名無しさん
2015/08/12(水) 23:01:27.55ID:ALDJfVhA0076デフォルトの名無しさん
2015/08/12(水) 23:10:56.27ID:Pci5W2YJリストは最も基本的な再帰構造だと思うんだけど
haskell
data [a] = [] | a : [a] deriving (Eq, Ord)
scala
sealed trait List[+A]
case class Cons[+A](head:A,tail:List[A]) extends List[A]
case object Nil extends List[Nothing]
0077デフォルトの名無しさん
2015/08/12(水) 23:16:15.63ID:S25mloU+それは何の反論にもなってない。
リストはツリー構造のサブセット。
ツリー構造の柔軟性の一部を禁止してシンプルにしたもの。
そのシンプルなデータ構造に対してはシンプルな処理を
使ったほうがわかりやすくなるのは当たり前。
再帰よりもループのほうが単純なことしか出来ないが、
単純なことしか出来ないから、余計なことを考える必要がなくなる。
シンプルな構造にも複雑な構造にも複雑な構造用の道具を使うのではなく
シンプルな構造にはシンプルな構造用の道具、
複雑な構造には複雑な構造用の道具を使うことが、
適切に道具を選ぶということ。
0078デフォルトの名無しさん
2015/08/12(水) 23:16:55.97ID:Pci5W2YJlength [] = 0
length (x:xs) = 1 + (length xs)
ループより分かりやすくね?
まぁ リストの長さなら
def length[A](list:List[A]):Int = list.foldLeft(0)((total,_)=>total + 1)
みたいにfold使った方がいいかもわからんが
0079デフォルトの名無しさん
2015/08/12(水) 23:18:07.58ID:S25mloU+よくわからないので、ループで書いてくださいｗ
0080デフォルトの名無しさん
2015/08/12(水) 23:18:53.71ID:ALDJfVhA伺いますけど、あなたのリストにはループに使うインデックスついてるんですか？
appendとか恐ろしく高コストで使えない不思議なリストですね
でもそうじゃないとインデックスでのアクセスはO(n)なんでねえ
なんでリストを扱ったプログラミングしたことないくせに偉そうなんだろ
0081デフォルトの名無しさん
2015/08/12(水) 23:20:08.29ID:S25mloU+え？append？
なんでオーダーなんか出てきてんの？
今までそんな話全くしてない。
話がずれてるね。
0082デフォルトの名無しさん
2015/08/12(水) 23:20:45.20ID:Pci5W2YJ高階関数使ったほうがよさげじゃね？
fmap, foldr, >>=, <*> なんかを使ったほうがいいと思う
0083デフォルトの名無しさん
2015/08/12(水) 23:21:38.26ID:S25mloU+そうだよ？
高階関数を使ったほうがもっと良い。
高階関数の話は上の方でしている。
ただ再帰を使って書く必要ねーなって話。
0084デフォルトの名無しさん
2015/08/12(水) 23:23:21.20ID:Pci5W2YJfoldのほうが分かりやすいけど
再帰のほうは
リストの長さは空だったら0 空じゃなかったらtailの長さに+1したものって宣言的に買い取るだけ
0085デフォルトの名無しさん
2015/08/12(水) 23:23:52.85ID:ALDJfVhAなんで「そんな話」が出てくるのかわからないなら
再帰もリストもまったく知らないってことなんですけどねえ
低レベルだわあ
0086デフォルトの名無しさん
2015/08/12(水) 23:24:48.52ID:S25mloU+つまり、それ何をやってるの？
日本語で、一言で言うと・・・？
0087デフォルトの名無しさん
2015/08/12(水) 23:24:50.58ID:Pe25qO3wむしろツリーはメモリ上の配列に表現されてるようなもんなんじゃ
まともなバイナリフォーマットって大抵オフセットもってたりしてシンプルにデコードできるようになってる
糞古いフォーマットでハフマンみてーなのだとどーしても再帰の使用を考えるようになるんだけど
これは今の計算機が持ってるほぼすべての並列化機構を機能不全にするのよね
0088デフォルトの名無しさん
2015/08/12(水) 23:25:35.07ID:JsRAlNhVHTMLを取り扱うクラスを書いてみたんだけど。
このスレ程度のデータ量でも簡単にスタックオーバーフローする。
タスクマネージャで見ると、ほんの数メガバイト、しかも大部分は
ネットワークキャッシュに使われてるような状態なんだけども。
まあ、C++使いは十分注意したほうが良いと思う。
あと、マシンスタックの大きさはWindowsなら簡単に設定できるわけだけど、
そんなことはせずに、素直にループにした方が良いマナーだと思う。
0089デフォルトの名無しさん
2015/08/12(水) 23:25:50.72ID:S25mloU+苦笑ｗ
話の内容はわかってる。
そんな話は俺はしてないといってる。
わかってるから、俺はしてないといえるわけだよ。
OK？
0090デフォルトの名無しさん
2015/08/12(水) 23:27:05.85ID:Pci5W2YJ個人的には
問題にあった適切な高階関数 > fold > 再帰 > 末尾再帰 >ループ
で読みやすさが変わるイメージ
0091デフォルトの名無しさん
2015/08/12(水) 23:27:56.05ID:ALDJfVhAリストをループで処理するとか言うアホに言われましても
どうぞmapをループでお書きくださいな
＃ 配列とリストの区別もついとらんとはねえ
0092デフォルトの名無しさん
2015/08/12(水) 23:30:43.07ID:ALDJfVhA末尾呼びにしなきゃそりゃそうなります
0093デフォルトの名無しさん
2015/08/12(水) 23:30:43.36ID:Pci5W2YJ>>86
リストの長さ
0094デフォルトの名無しさん
2015/08/12(水) 23:31:51.38ID:S25mloU+> どうぞmapをループでお書きくださいな
これでいい？
function map(list, callback) {
let ret = [];
for(item of list) {
ret.push(callback(item));
}
return ret;
}
0095デフォルトの名無しさん
2015/08/12(水) 23:32:45.32ID:JsRAlNhVこれ、コーディング中は小さなデータでテストしてるから気が付かないことがあると思う。
というか俺はそうだった。
特定のサイトでだけスタックオーバーフローするので何かと思ったら、
デストラクタが再帰するのであった。
0096デフォルトの名無しさん
2015/08/12(水) 23:33:03.35ID:6ZXtaURLループの方がよっぽど要らないような
0097デフォルトの名無しさん
2015/08/12(水) 23:35:11.79ID:S25mloU+「リストの長さ」っていうより
「空だったら0 空じゃなかったらtailの長さに+1したもの」っていう方が
日本語の言葉として明らかに長いよね？
0098デフォルトの名無しさん
2015/08/12(水) 23:35:36.01ID:JsRAlNhVC++だとコンカレントは遅くなること多いんだよな。
コンカレントが入って喜び勇んで使ってみたけど、まあまだ使える時代じゃないと思った。
0100デフォルトの名無しさん
2015/08/12(水) 23:36:36.85ID:S25mloU+> レスを読む限り、mapのがよく問題を分離できるし並列もできるから
> ループの方がよっぽど要らないような
mapとループの話じゃなくて、
ループと再帰の話で、再帰使うまでもない所で
再帰使う必要ないよって話をしてるんだよ。
要らないとは誰も行ってない。
シンプルな道具を適切に使いましょう。
0101デフォルトの名無しさん
2015/08/12(水) 23:38:07.01ID:Pe25qO3w0102デフォルトの名無しさん
2015/08/12(水) 23:38:19.63ID:S25mloU+> mapをmapで定義してくださってどうもありがとうございます
どこがmap？
for...of ループの話？
ほれ、for...of ループ の説明
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Statements/for...of
0103デフォルトの名無しさん
2015/08/12(水) 23:39:14.64ID:6ZXtaURL自分もコピーコンストラクタの再帰バグとかよくやりますｗ
C++は基本的部品は自分で書かず、
よくテストされてもの使った方がいいですね
0104デフォルトの名無しさん
2015/08/12(水) 23:39:27.31ID:S25mloU+function map(list, callback) {
let ret = [];
for(let i = 0; i < list.length; i++) {
ret.push(callback(list[i]));
}
return ret;
}
って書くだけだけどね。
0105デフォルトの名無しさん
2015/08/12(水) 23:40:41.46ID:6ZXtaURLいえいえ、ループを引き合いに出してるので、
その2者なら再帰よりもループのが要らないでしょうと
0106デフォルトの名無しさん
2015/08/12(水) 23:40:57.52ID:JsRAlNhVSIMDとかは更にまだまだ時代じゃないような気がする。
特定の環境に合わせてシコシコこさえるくらいの時代。
0107デフォルトの名無しさん
2015/08/12(水) 23:42:37.68ID:S25mloU+「要らない」の理由がおかしいんだよ。
再帰でループが実現できるのは知ってる。
君は、大は小を兼ねる理論で、
大があれば小はいらないという考え方だろうけど、
俺は大には大を、小には小を使った方が
いい（わかりやすい）と言ってるわけ。
0108デフォルトの名無しさん
2015/08/12(水) 23:44:25.03ID:JsRAlNhV俺もそれはそうだと思う。
最初、イテレータを持つようにしてみたんだけど、何となく汚く見えたんで
std::shared_ptr使ってノードを表現したら、デストラクタがネストするバグを
こさえてしまった。
でも、結果的に、感動的にうまく動くアルゴリズムができて満足。
色々勉強になった。
0109デフォルトの名無しさん
2015/08/12(水) 23:46:49.96ID:JsRAlNhV0110デフォルトの名無しさん
2015/08/12(水) 23:53:27.52ID:Pe25qO3wパイプライン
0111デフォルトの名無しさん
2015/08/12(水) 23:58:30.93ID:6ZXtaURL私は再帰を代替にしろ、という話は一切してないですよ
率直に言って、あなたの主張は再帰を相手にしなくてもいい一般化ですし、
他人を下と決めつけてかかって煽ってるようにしか見えません。
0112デフォルトの名無しさん
2015/08/13(木) 00:02:20.41ID:AIiQbQBJひどいいいがかりだな
0113デフォルトの名無しさん
2015/08/13(木) 00:03:45.02ID:AIiQbQBJレッテル張り
0114デフォルトの名無しさん
2015/08/13(木) 00:04:44.19ID:Vkqae3eeここは言語の違いだと思うけどjavascriptみたいな手続き型で再帰を特にサポートしていない言語は
再帰は基本的に使わない方がいいけど
関数型プログラミング言語だとむしろループより再帰の方が書きやすいし自然だから
よっぽど高速化したい時じゃないとループ使わないと思う（ループだとそのコードみたいに破壊的代入が含まれるし）
0115デフォルトの名無しさん
2015/08/13(木) 00:09:22.93ID:G0UckYXUレッテル貼りとは、太平洋戦争の頃に使われた言葉で、現代の若者は
ラべリング問題と言わないとわからないらしい。
あと、レッテル張りとは、レッテルを瓶に貼る前に水でピンと張る工程のことで、
それは、昭和初期のラべル職人以外には通じない言葉らしい。
0116デフォルトの名無しさん
2015/08/13(木) 00:14:19.60ID:Vkqae3ee0117デフォルトの名無しさん
2015/08/13(木) 00:15:41.46ID:AIiQbQBJ常識で考えろよ、昭和初期のラベル職人以外には通じないことを
ここで言うと思うか？バカじゃね。
0118デフォルトの名無しさん
2015/08/13(木) 00:16:00.68ID:NebXzry6もう何の話かわからないけど、無駄に知識がついてしまった
0119デフォルトの名無しさん
2015/08/13(木) 00:17:24.90ID:AIiQbQBJパターンマッチはifで書けばいいし、再帰はループで書けばいい。
いきがるな。
0120デフォルトの名無しさん
2015/08/13(木) 00:18:56.16ID:AIiQbQBJラリってるだけ。
0121デフォルトの名無しさん
2015/08/13(木) 00:23:14.84ID:Vkqae3eeifはパターンマッチ漏れをコンパイラが警告してくれないんやで
val a = list match {
case Nil => Nil
case head :: tail => tail
}
をifで書くと
var a;
if(list.isEmpty){ a = Nil } else { a = list.tail }
だろ 辛い
0122デフォルトの名無しさん
2015/08/13(木) 00:24:32.15ID:NebXzry6JavaScriptならswitch(true)で頑張れば、ある程度は代替できそうですが、
基本的に静的型言語じゃないと真価を発揮できない気がしますね
0123デフォルトの名無しさん
2015/08/13(木) 00:24:38.47ID:Vkqae3ee言語の違い、データ構造の違い
0124デフォルトの名無しさん
2015/08/13(木) 00:27:11.91ID:AIiQbQBJループを再帰で書く奴はミーハーで頭の中ハコスカなだけ
0125デフォルトの名無しさん
2015/08/13(木) 00:28:36.37ID:FUyksqfE再帰的なアルゴリズムなら再帰を使えばいいし
反復なアルゴリズムならループを使えばいいし
どちらでもいいなら気分でかけばいいじゃん？
どっちか一方しか使わない使えないでは話にならん
0126デフォルトの名無しさん
2015/08/13(木) 00:33:41.96ID:Vkqae3eeむしろ最初に再帰が浮かび後からループにいやいや書き換えるのではないか
0127デフォルトの名無しさん
2015/08/13(木) 00:38:27.39ID:FUyksqfEアルゴリズムの考え方が先行して考えられると思うけど
0128デフォルトの名無しさん
2015/08/13(木) 00:57:49.87ID:NebXzry6ループや再帰処理それ自身がアルゴリズムなので、
強いて依存先として挙げるならデータ構造じゃないかと
0129ID:JsRAlNhV
2015/08/13(木) 01:30:53.70ID:1C0y4JfF反論者と擁護してくれる人の両方がいるな。
0130デフォルトの名無しさん
2015/08/13(木) 01:35:10.57ID:G0UckYXU再帰を使うべきって話ですか？
0131デフォルトの名無しさん
2015/08/13(木) 01:35:43.95ID:1C0y4JfF> レッテル張り
全くだね〜ｗ
>>114
> ここは言語の違いだと思うけどjavascriptみたいな手続き型で再帰を特にサポートしていない言語は
> 再帰は基本的に使わない方がいいけど
というか逆だね。（一部の？）関数型言語のような、
ループを再帰よりも書きづらくしているものに限って言えば、
再帰を使うしか無いよ。仕方なく。
そういう言語以外は、再帰よりもループのほうが簡単に書ける。
（データ構造自体が再帰に適している場合は除く）
> ループだとそのコードみたいに破壊的代入が含まれるし
破壊的代入はするよりもしないほうがいいのは確かで、
俺もコードレビューなどで破壊的代入はするなって言ってるけど、
それは方針であって絶対的なもんじゃない。
破壊的代入をしたほうがわかりやすい場合もある。
よく言われるように手段と目的を履き違えるな問題だよ。
0132デフォルトの名無しさん
2015/08/13(木) 01:37:43.32ID:1C0y4JfF> どっちか一方しか使わない使えないでは話にならん
俺もそれを言ってる。
再帰を知った奴がなんでも再帰を使って
解こうとしている。それに対して警告してる。
まだまだだよって。
0133デフォルトの名無しさん
2015/08/13(木) 01:38:45.50ID:1C0y4JfF> 末尾再帰云々言ってる人は、コンパイラがループに変換してくれるから
↓ 俺が最初のほうで書いたレスｗ
24 自分：デフォルトの名無しさん[sage] 投稿日：2015/08/11(火) 18:24:05.65 ID:Ghx6BuLg
ループで実装する
↓
（意味なく）再帰にしたい！
↓
再帰にするとスタックがー、関数呼び出しがー、どうのこうの
↓
末尾最適化される再帰にすればいいんだぜ！フフン
↓
末尾最適化されるような再帰コードを書く
↓
コンパイラがループの実装に戻す
結論
人間がループを再帰に変換し、
コンパイラが再帰をループに戻すという無駄！
0134デフォルトの名無しさん
2015/08/13(木) 01:43:20.43ID:1C0y4JfF> むしろ最初に再帰が浮かび後からループにいやいや書き換えるのではないか
女性の列の中から男の娘を探しなさいって言われた時、
前から一人づつ見ていくという方法を思いつく人は多くいると思うが、
俺「一人だけ確認した。あとは俺に頼む」→俺「はーい、わかりました。俺も同じことをしまーす。」→俺「以下同文」
という考え方をする人は滅多に居ないと思うが。
0135まーた連続書き込み規制だよ
2015/08/13(木) 01:50:39.52ID:kS/o56L+そういう場合、switchを使うんだけど
ちょっと数が増えただけで、循環的複雑度を調べるツールで
複雑だって言われるんで、これぐらいいいじゃねーかと思いながら
（※注 そのツールを導入したのは俺ｗしきい値を8に設定してるのも俺ｗ）
関数テーブル呼び出し的なコード（意味わかるよね？）に書き換えるんだけど、
そうしたらやっぱり前よりわかりやすくなって、
やっぱりswitchいらねーか、とか思ってしまうｗ
関数テーブル呼び出し的なコードにすれば、パターンマッチ漏れは
nullを関数呼び出しすることになって、実行時エラーになってはくれるよ。
0136デフォルトの名無しさん
2015/08/13(木) 01:54:14.37ID:NebXzry6私は相手をその手の人間と決め付けて話す事が、
おかしいといってるだけですよ
0137デフォルトの名無しさん
2015/08/13(木) 01:59:57.44ID:kS/o56L+> 元から再帰で無理矢理書くことを勧めてる人は、そういないんじゃないかと
うん、こいつらぐらいかな？ 適切なものを選ぼうとせずに
何でも再帰、再帰のほうがわかりやすい。
再帰使うほうが頭いい、（理由ないけど）普通に再帰だわ
とか言ってる人。
25 名前：デフォルトの名無しさん[] 投稿日：2015/08/11(火) 20:07:51.21 ID:SPQSl72c [2/2]
再帰のほうがわかりやすいと思えない子が
26 名前：デフォルトの名無しさん[sage] 投稿日：2015/08/11(火) 20:55:40.81 ID:I9e7/X97 [1/2]
再起が得意かどうかで頭の良さが決まる
33 名前：デフォルトの名無しさん[] 投稿日：2015/08/11(火) 23:39:17.34 ID:BomPGBV/ [2/2]
再帰苦手なのは練習不足なだけ
理解が早いのは完全に地頭がいいだけじゃね？
74 返信：デフォルトの名無しさん[] 投稿日：2015/08/12(水) 23:00:43.40 ID:ALDJfVhA [5/11]
>>72
>だけどデータがリスト構造なだけなら
>普通にループを使ったほうがわかりやすい。
んなわけねーだろ
普通に再帰使うわ
0138デフォルトの名無しさん
2015/08/13(木) 02:00:23.27ID:NebXzry6それってfoldかfilterで良くないですか？
そう言う意味で、再帰よりループのが不要に見えるんですが
0139デフォルトの名無しさん
2015/08/13(木) 02:03:39.26ID:G0UckYXU0140デフォルトの名無しさん
2015/08/13(木) 02:06:24.18ID:G0UckYXU結局、純粋な関数型言語の時代は来ないんじゃないですかね。
0141デフォルトの名無しさん
2015/08/13(木) 02:07:07.66ID:kS/o56L+> そう言う意味で、再帰よりループのが不要に見えるんですが
え？ 君、foldかfilterでいいにしても、再帰の話してないよね？
foldもfilterもループでも再帰でも書けるわけだから。
高階関数呼び出しを行うそれらの関数を使えば
ループ（または再帰）が不要になるっていう話なら別に否定してない。
俺もよく使うし、上の方でも書いたよ。
>>53
> 最近ではMIMEメールのパースとか、連想配列の
> 全ての値の処理とかで使ったかな。
>
> 再帰を使うことはめったにない。そしてミスをしやすい所でもある。
> だから再帰を使うときは、再帰を考慮しなくていい形に置き換えるようにしている。
> つまりJavaScriptでいうmapやreduceの形にする。再帰部分と処理部分に分けて再帰部分を隠ぺいする。
> 通常書くのはコールバックで呼ばれる処理部分のみ。
> そうすることで可読性も大きく上昇する。
再帰はわかりづらいからtraverseみたいな形にすることで再帰を内部に隠ぺいする。
ループを内部に隠蔽してfoldかfilterがあればループが不要だというのなら、
同じ理由で、再帰を内部に隠蔽したtraverseで良いから、再帰は不要だって言えばいいの？
0142デフォルトの名無しさん
2015/08/13(木) 02:13:00.97ID:NebXzry6必要性の比較として、その手の関数で簡単に書き下せるloopの方が、
再帰より不要ではないですか？と言う意味ですよ
実装としては、さすがにループが完全になくなるとは思ってません
0143デフォルトの名無しさん
2015/08/13(木) 02:15:06.80ID:kS/o56L+>>140
> 結局、純粋な関数型言語の時代は来ないんじゃないですかね。
俺もそう思う。
高階関数は便利だけど、純粋な関数型言語まではいらないかな。
あとScalaでいうval、再代入不可能な変数も欲しいけど。
0144デフォルトの名無しさん
2015/08/13(木) 02:19:20.99ID:NFzWJ2Cc0145デフォルトの名無しさん
2015/08/13(木) 02:19:45.60ID:kS/o56L+そもそもの話が、「ループで簡単に書けるようなもの」を
再帰でわざわざ書くなって話なんだよ。
正確に言うと、再帰を使わないでいいような処理に
再帰を使うなという話。
だから、その手の関数で簡単に書き下せる処理に
再帰を使うなっていう話でも有る。
0146デフォルトの名無しさん
2015/08/13(木) 02:20:52.90ID:kS/o56L+話が再帰してるから
（ループをわざわざ再帰にしてみました！）
0147デフォルトの名無しさん
2015/08/13(木) 02:24:57.75ID:NebXzry6では、それを踏まえた上でどう思います？
0148デフォルトの名無しさん
2015/08/13(木) 03:17:20.09ID:kS/o56L+最初っからおんなじ
再帰は可読性悪いんで
使わずに済むなら使わない方がいい。
0149デフォルトの名無しさん
2015/08/13(木) 03:18:50.05ID:WDxyRHha内部に隠蔽して、再帰であると意識せずに
また再帰のコードを見ずに、処理できるようにした方がいい。
0150デフォルトの名無しさん
2015/08/13(木) 03:30:05.42ID:NebXzry6いえ、そうではなく、二者択一で
再帰とループで、必要性が高いのはどっちだと思います？
もちろん、高階関数や各種操作関数での置き換えを踏まえた上での話です
必要と思うならどういう場面なのかなと
0151>>150
2015/08/13(木) 03:31:16.05ID:NebXzry60152デフォルトの名無しさん
2015/08/13(木) 03:36:08.86ID:WDxyRHhaお前バカじゃね？
足し算と掛け算どっちが必要かって
言ってるようにしか聞こえん。
適切なものを使えよ。
0153デフォルトの名無しさん
2015/08/13(木) 03:39:48.62ID:WDxyRHhaあっても隠蔽するから両手で数えられるほどしか無い。
片手でもいけるかもｗ
0154デフォルトの名無しさん
2015/08/13(木) 03:51:07.78ID:NebXzry6私はそこまで一般化はしてないですし、適材適所も否定してません
それと必要性の比較も関係ありませんよ
例えばgoto文も適材適所ですが、必要性は低いと思ってます
再帰がループと同程度に必要と思うなら、そう言ってくれればいいです
違う場合に、その先の話がしたいだけなので
0155デフォルトの名無しさん
2015/08/13(木) 04:15:21.85ID:NebXzry6どうあっても再帰は不要といいつつ、ループが必要とは言わないんですね…
0156デフォルトの名無しさん
2015/08/13(木) 04:27:48.44ID:WDxyRHha実践では再帰はあまり使いません。
必要性の話をするのなら
それが現実では？
0157デフォルトの名無しさん
2015/08/13(木) 07:42:46.93ID:GBQWWFg+0158デフォルトの名無しさん
2015/08/13(木) 07:48:57.17ID:FXSompvo0159デフォルトの名無しさん
2015/08/13(木) 08:21:16.88ID:Iax2S8IU実用的なクイックソートはループ。
まさか再帰でしか実現できないなんて考えとるんか？
0160デフォルトの名無しさん
2015/08/13(木) 08:52:19.31ID:GBQWWFg+再帰より可読性の高い、ループでのクイックソートの実装は寡聞にして知りません。
0161デフォルトの名無しさん
2015/08/13(木) 09:30:01.18ID:Iax2S8IU特別なことはやらないから、誰でもすぐ実現できるはず。
Cどころか昔のVBのようなへぼ環境でも
何百万ものデータを高速にソートできてしまう。
0162デフォルトの名無しさん
2015/08/13(木) 09:53:04.16ID:GBQWWFg+https://github.com/lattera/glibc/blob/master/stdlib/qsort.c
本来の再帰アルゴリズムを、非再帰で記述するために状態を自前のスタックで管理しなきゃならない。
余計なコードが必要な分、可読性は低いですね。
0163デフォルトの名無しさん
2015/08/13(木) 10:07:42.74ID:Q4WJ33HHFSF、Microsoft、そしてAppleが再帰を避けるのは何故か考えてみては。
0164デフォルトの名無しさん
2015/08/13(木) 10:10:35.79ID:wsd38m6Jどっちでもいいよ。
金太郎飴をループで切るか再帰で切るか、程度の話しかしてない
みたいだしな。その関数がその構造のどこまでのデータを扱うのか
ってことを意識してりゃ別にいい。
再帰でよその子をいじったりとかするのは馬鹿のやること。
0165デフォルトの名無しさん
2015/08/13(木) 10:13:00.13ID:1x08JE5T>>162は可読性について論じているのに
0166デフォルトの名無しさん
2015/08/13(木) 10:27:03.54ID:Q4WJ33HHわざわざglibcのソース引っ張り出してるとこからして、本人も言いたいことが自分で分かっていないのでは？
Cで再帰するコードを書けば、たいていのチェッカが警告するし、品質保証からお叱りを受けるはず。
やってはいけないことの一つとして、ほとんどの企業で明文化されているはずです。
そして良く知られるMISRA-Cも通りません。
こういう状況下で、glibcのソースを引用して再帰するべきと主張するのはおかしい。
glibcでも再帰は避けている、再帰するべきでないという主張になるのが当然だと思う。
そうなっていないという事は、本人が一番自分の主張をわかっていない。
と思うのです。
0167デフォルトの名無しさん
2015/08/13(木) 10:30:12.83ID:NebXzry60168デフォルトの名無しさん
2015/08/13(木) 10:30:37.05ID:Iax2S8IU再帰の場合よりも良くなくてはいけないと？
理解困難なコードでなく実用性があるのなら採用するでしょ。
プログラマはソート処理のコードは使いまわして
比較関数を用意すればいいだけだし。
0169デフォルトの名無しさん
2015/08/13(木) 10:32:46.72ID:GBQWWFg+可読性の話をしてるんですが?
0170デフォルトの名無しさん
2015/08/13(木) 10:38:27.46ID:WDxyRHha> 本来の再帰アルゴリズムを、非再帰で記述するために状態を自前のスタックで管理しなきゃならない。
だから適切なものを選べって言ってるじゃん。
誰が、再帰が適切なものまで、
ループにしろって言ったよ？
ループで済むものを再帰でやるなって話。
ほんと>>41で書いた4の段階のやつだなお前は。
0171デフォルトの名無しさん
2015/08/13(木) 10:40:07.80ID:WDxyRHha> プログラマはソート処理のコードは使いまわして
> 比較関数を用意すればいいだけだし。
そういう場合、そのソートは何に使われるかわからないから
往々にして、速度が一番早い方法を選ぶんだよね。
つまりループで実装。
0172デフォルトの名無しさん
2015/08/13(木) 10:41:21.58ID:A9RCljrX可読性の基準が変わってくるでしょ
再帰で触感的に記述できるのは再帰構造持ったアルゴであって
本来行うべき実行じゃないから非直観的なんよ
可読性として表現したい対象がそもそも違うのよね
0173デフォルトの名無しさん
2015/08/13(木) 10:42:13.58ID:96XWMJC8スタックオーバーフローを検出して適切にエラー処理するために自前のスタックにするとかは普通にあるし
0174デフォルトの名無しさん
2015/08/13(木) 10:43:10.07ID:NebXzry6中身ちゃんと読んでますか？
このソース要素数が一定以上の場合、どうやらquicksortしない仕様で、
quicksort処理部もスタック使ってるようですよ
要素数で分けて安全性を保っているだけで、
処理そのものの安全性そのものは再帰と変わってません
0175デフォルトの名無しさん
2015/08/13(木) 10:47:32.08ID:Iax2S8IU何言っとるんだ？
0176デフォルトの名無しさん
2015/08/13(木) 10:47:43.55ID:WDxyRHha> ソースがコンパイラにどう最適化されて実行時にどう動かされるかを考えてると
> 可読性の基準が変わってくるでしょ
可読性の読みやすさって
人間の読みやすさだからｗ
コンパイラにとっては可読性関係ないよ
どんなに読みづらいコードでも
書いてあるとおりに解釈してくれる。
0177デフォルトの名無しさん
2015/08/13(木) 10:48:35.29ID:Q4WJ33HH自前のスタックを使っています。
確かにあなたのおっしゃる通り*自前の*スタックを使っています。
ですが再帰ではありません。
0178デフォルトの名無しさん
2015/08/13(木) 10:48:36.95ID:Q4WJ33HH自前のスタックを使っています。
確かにあなたのおっしゃる通り*自前の*スタックを使っています。
ですが再帰ではありません。
0179デフォルトの名無しさん
2015/08/13(木) 10:51:04.09ID:Q4WJ33HH明文化された事実なんですよ。
手間がかかろうがなんだろうが、再帰を無くさなければならない。
そんなこと当たり前じゃないですか。
0180デフォルトの名無しさん
2015/08/13(木) 10:51:19.49ID:GBQWWFg+glibcのqsortでもstack_node stack[STACK_SIZE]が溢れますね。
メモリ消費量は、再帰で書くとそれに加えて、リターンアドレスやフレームの保存領域が余計に必要になるだけですよね。
0181デフォルトの名無しさん
2015/08/13(木) 10:53:38.16ID:Q4WJ33HHじゃあ品証にそう言って噛みついてみては？
0182デフォルトの名無しさん
2015/08/13(木) 10:55:16.00ID:Q4WJ33HH0183デフォルトの名無しさん
2015/08/13(木) 11:01:18.21ID:Iax2S8IUこれは指定の番号のデータが、ソート結果として
第何番目になるかを出力させるといい。
つまり順番に数値を格納した配列を用意して
その要素をクイックソートの置き換え処理の対象にさせる。
また、比較関数もこれに対応したものを用意する。
この方式なら
int stack[STACK_SIZE]
を用意すればいいので、件数は多くても
メモリ消費量はそんなに必要にならない。
0184デフォルトの名無しさん
2015/08/13(木) 11:01:20.46ID:GBQWWFg+>>53が言い出した「再帰は可読性が悪い」に対する反論なのですが。
0185デフォルトの名無しさん
2015/08/13(木) 11:01:38.29ID:NebXzry6コメントとMAX_THRESHで追えば解ると思います
全くしないわけではないです
0186デフォルトの名無しさん
2015/08/13(木) 11:13:50.27ID:GBQWWFg+非再帰版は再帰を自前のスタック管理でエミュレートしているだけなんだから、
同一データを、再帰版と非再帰版で実行すると再帰版の再帰の深さと、
非再帰版のstackの使用個数は同じになるに決まってるじゃないですか。
0187デフォルトの名無しさん
2015/08/13(木) 11:15:13.87ID:1x08JE5TＯＳとかの制作には向いてないってことで
普通のソフトならオーバーフローしない限り問題ない
0188デフォルトの名無しさん
2015/08/13(木) 11:22:16.59ID:Q4WJ33HH使いません。
0189デフォルトの名無しさん
2015/08/13(木) 11:24:47.30ID:Q4WJ33HHよく使われるガイドライン、規約で明示的に禁止されています。
C/C++で再帰は邪悪なのです。
再帰を使う人は悪人です。
0190デフォルトの名無しさん
2015/08/13(木) 11:26:18.86ID:1x08JE5T0191デフォルトの名無しさん
2015/08/13(木) 12:51:43.10ID:GBQWWFg+ウソつき。 禁止してるのってMISRA-Cだけですね。
CERT C Secure Coding Standard
Recursion can also lead to large stack allocations. Recursive functions must ensure that they do not exhaust the stack as a result of excessive recursions.
ISO/IEC TR 24772:2013
6.37.5 Avoiding the vulnerability or mitigating its effects
Software developers can avoid the vulnerability or mitigate its ill effects in the following ways:
+ Minimize the use of recursion.
+ Converting recursive calculations to the corresponding iterative calculation.
In principle, any recursive calculation can be remodeled as an iterative
calculation which will have a smaller impact on some computing resources but
which may be harder for a human to comprehend.
The cost to human understanding must be weighed against the practical
limits of computing resource.
+ In cases where the depth of recursion can be shown to be statically bounded
by a tolerable number, then recursion may be acceptable, but should be
documented for the use of maintainers.
0192デフォルトの名無しさん
2015/08/13(木) 12:54:40.29ID:V/aggySn0193デフォルトの名無しさん
2015/08/13(木) 13:05:26.51ID:WDxyRHha0194デフォルトの名無しさん
2015/08/13(木) 13:06:35.36ID:t3mydoM30195デフォルトの名無しさん
2015/08/13(木) 13:12:01.20ID:WDxyRHha0196デフォルトの名無しさん
2015/08/13(木) 13:12:01.28ID:A9RCljrX糞みたいな本のコピペ宣伝がくるね
0197デフォルトの名無しさん
2015/08/13(木) 13:13:19.26ID:WDxyRHhaそれは、押すなよ、押すなよってやつですか？
それとも自分でコピペして、ほら俺の言ったとおりだった（ドヤ顔）を
やるための布石ですか？
0198デフォルトの名無しさん
2015/08/13(木) 13:13:33.60ID:GBQWWFg+これに異論はありますか?
0199デフォルトの名無しさん
2015/08/13(木) 13:14:50.27ID:aB+CmHXzループは再帰で表現するのが推奨
Scala特有とか意味わからん
0200デフォルトの名無しさん
2015/08/13(木) 13:19:18.15ID:WDxyRHha中途半端な質問するなよｗ
クイックソートは再帰版の方が可読性が高い。
バブルソートは再帰版の方が可読性が高い。
マージソートは再帰版の方が可読性が高い。
これに異論はありますか?
やるならこれぐらいやれよｗ
その言い方だとクイックソートだけしか勝ち目がないと
自覚しているかのようだぞ。
なお、ソートの種類には以下の様なものが有るらしい。
https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
バブルソート、シェーカーソート、コムソート、ノームソート、選択ソート、挿入ソート
シェルソート、2分木ソート、ライブラリソート、マージソート、In-place マージソート
ヒープソート、スムースソート、クイックソート、イントロソート、ペイシェンスソート
ストランドソート、奇偶転置ソート、シェアソート
半分も知らんなｗ
0201デフォルトの名無しさん
2015/08/13(木) 13:20:57.51ID:WDxyRHha推奨とか、破壊的代入を禁止するという制約のために
選択肢がないだけに見えますが。
破壊的代入を禁止することが、
必ずしも可読性を高めるとは限らないので。
0202デフォルトの名無しさん
2015/08/13(木) 13:24:34.58ID:NebXzry6fold mapでループは消えますので、再帰より不要ですね(煽り)
0203デフォルトの名無しさん
2015/08/13(木) 13:27:20.56ID:WDxyRHhafold mapによって消えるものがなぜループだと？
fold mapによって再帰が消えるのではないのですか？
0204デフォルトの名無しさん
2015/08/13(木) 13:28:32.66ID:W1EX3EBl自覚してるんでしょうね（煽り）
0205デフォルトの名無しさん
2015/08/13(木) 13:30:40.85ID:GBQWWFg+>>53
> 普段はやはり再帰のコードは書くべきじゃないよ。
> 可読性悪いからね。
これが間違いであることは、反例を1つ示せば十分ですよね。足りないというなら、
ID:Q4WJ33HH氏がドヤ顔で言い出したISO/IEC 24772:2013にも
In principle, any recursive calculation can be remodeled as an iterative
calculation which will have a smaller impact on some computing resources but
which may be harder for a human to comprehend.
The cost to human understanding must be weighed against the practical
limits of computing resource.
って明記されてるし。
0206デフォルトの名無しさん
2015/08/13(木) 13:34:22.81ID:W1EX3EBl普段に当てはまらない場合は違うと言ってるわけで、
反例があるってことは、最初から言ってることですね。
0207デフォルトの名無しさん
2015/08/13(木) 13:43:25.91ID:GBQWWFg+その「普段」は発言者の彼によると、「再帰を繰り返しに置き換える」ので、クイックソート非再帰版が「普段」ですよね。
> 再帰を使うことはめったにない。そしてミスをしやすい所でもある。
> だから再帰を使うときは、再帰を考慮しなくていい形に置き換えるようにしている。
0208デフォルトの名無しさん
2015/08/13(木) 13:44:15.15ID:W1EX3EBlその発言者は私ですが、普段というのは
日々の仕事の話ですよｗ
普段あなたは何をしてるのですか？
の普段です。
0209デフォルトの名無しさん
2015/08/13(木) 13:47:30.00ID:W1EX3EBl普段はクイックソートの実装などせずに
予め用意されたソート関数、つまり高階関数を引数にしたソート関数を
呼び出すだけなので普段は再帰を使ったコードを書きません。
>>202の発言風に言うと、
sortで再帰は消えますので、再帰は不要ですね（煽り）
0210デフォルトの名無しさん
2015/08/13(木) 13:47:49.82ID:GBQWWFg+「普段」はクイックソートのように再帰版の方が可読性の高いものを、非再帰版に書き直さないのですか?
0211デフォルトの名無しさん
2015/08/13(木) 13:50:17.90ID:W1EX3EBl普段は再帰は可読性が低いので、
再帰だとわからないように
sort関数のようなものを作ります。
再帰が可読性高かったら、
わざわざsort関数なんて作りませんよｗ
0212デフォルトの名無しさん
2015/08/13(木) 14:02:03.63ID:GBQWWFg+再帰版クイックソートは可読性が低いという主張ですね。
>>206と矛盾しますが。
> 普段に当てはまらない場合は違うと言ってるわけで、
0213デフォルトの名無しさん
2015/08/13(木) 14:09:44.52ID:NebXzry6え…？再帰構造にmap使うんですか？
かなり効率悪いと思いますが
0214デフォルトの名無しさん
2015/08/13(木) 14:23:38.44ID:W1EX3EBlえ？そんな話してませんよ。
話の内容を整理しましょう。
fold mapによって消えるものがなぜループだと
思っているということは、fold mapが再帰ではなく
ループで実装されていると思っているからでしょう？
fold mapを使えば、ループが要らないっていうのはそういうことですね。
もしfold mapの中身が、ループではなく再帰で実装されていると思っているのなら、
fold mapで消えるのは再帰だと考えるはずです。
だから、ははん、こいつはループを使ったほうが適切な問題だって
わかっていると言ったんです。
最初っから言ってるように、適切なものを使う。
単なるリスト構造であればループで良い。
再帰的な構造であれば再帰使えばいいと言ってます。
0215デフォルトの名無しさん
2015/08/13(木) 14:27:29.97ID:W1EX3EBl> 再帰版クイックソートは可読性が低いという主張ですね。
全く違います。
再帰を使ったコードは可読性が低いので、
sort等の関数を使って再帰を隠蔽するというのが
私の主張です。
何回も説明したはずですが？
「普段」というのは>>208で書いたように、
日々の仕事のことですから、普段は再帰は使いません。
使うことがあっても内部で隠蔽されたsort関数などを使うし、
自分で隠蔽するので、普段は再帰は使いません。
0216デフォルトの名無しさん
2015/08/13(木) 14:29:35.52ID:NebXzry6>思っているということは、fold mapが再帰ではなく
>ループで実装されていると思っているからでしょう？
全然違います
ループに代替可能、かつ効率が上がる可能性があるからです
mapの実装がループって…ループや再帰で実装はできますが、
逐次処理に書き下したらmapの優位性なくなりますよ
その下は間違った前提で話してるのでスルーします
0217デフォルトの名無しさん
2015/08/13(木) 14:31:12.41ID:NebXzry6間違い訂正：ループに代替可能 → ループを代替可能
0218デフォルトの名無しさん
2015/08/13(木) 14:39:15.29ID:W1EX3EBlもしかして、mapの実装をmapで書いてると言った人ですか？ｗ
mapというのは写像のことです。
f: A → B のことです。
プログラミング的に書くならば、
B = f(A) という形になってないとmapではありません。
ループもしくは再帰でmapを実装するのですよ。
もっともこの場合は、ループで実装するのが適切だから
再帰は使いません（何度も私が言ってます。道具は適切に使いましょう。）
そして逐次処理に書き下しするって何の話してるのですか？
逐次処理の反対は並列処理ですが、今並列か逐次かの話なんかしていましたかね？
ループも再帰も逐次処理ですし。
0219デフォルトの名無しさん
2015/08/13(木) 14:49:38.43ID:NebXzry6mapはあなたの言う通りただの写像ですから、
それだけで逐次か並列かを縛るものじゃないですよ
再帰処理という意味なら、必然的に並列化して分割統治できるので、
どう見ても再帰が有利ですね
0220デフォルトの名無しさん
2015/08/13(木) 14:52:27.40ID:t3mydoM3いやだからリストは最も基本的な再帰的なデータ型だから。。
木より
0221デフォルトの名無しさん
2015/08/13(木) 14:56:24.24ID:W1EX3EBl全てのループは再帰で変換可能なので、
全てのループは並列化して分割統治できるということになりますが？
何度も言ってるように、適切なものを使いましょう？
ループを使ったほうが良い場合は
わざわざ再帰にする必要はないのですよ。
ちょっと出かけなきゃならないので、wikipedia貼って終わらすけど、
再帰だからって並列化できるとは限りません。
https://ja.wikipedia.org/wiki/%E4%B8%A6%E5%88%97%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
再帰的でありながら並列化が非常に難しい問題もある。例えば、グラフにおける深さ優先探索がある。
0222デフォルトの名無しさん
2015/08/13(木) 14:57:39.52ID:W1EX3EBl再帰の中でも一番シンプルなデータ構造です。
シンプルなデータ構造にはシンプルなループを使いましょう。
0223デフォルトの名無しさん
2015/08/13(木) 15:00:06.78ID:W1EX3EBl再帰、再帰ばかり言ってないで、
最近何処かに出かけたか？ｗ
引きこもってばかりだと、
体が細菌だらけになっちゃうぞｗ
0224デフォルトの名無しさん
2015/08/13(木) 15:09:12.83ID:NebXzry6主張してない事を主張として反論する事が多いですね…
逐次処理が必須なものは、並列化できなくて当然ですね
あえて挙げる意味ありますか？
ループと逐次処理で、並列の分割統治はできません
並列した時点でもうループではなく、並列、または再帰的処理です
そもそも自分で高階関数でいいと言ってるんですから、
逐次処理のループは消しましょう
>>223
もう本当ただの煽りですねｗ
0225デフォルトの名無しさん
2015/08/13(木) 15:16:09.30ID:GBQWWFg+> 全く違います。
これと
> 再帰版クイックソートは可読性が低いという主張ですね。
これ
> 再帰を使ったコードは可読性が低いので、
> sort等の関数を使って再帰を隠蔽するというのが
の、どこが違うのでしょう?
再帰版クイックソートは非再帰版に比べて、可読性が低いのですか? 高いのですか?
0226デフォルトの名無しさん
2015/08/13(木) 15:44:30.69ID:t3mydoM3いやどっちがシンプルな方法かは状況によりますし
そもそもリストの再帰でシンプルにならなかったら別のデータ構造使うべし
0227デフォルトの名無しさん
2015/08/13(木) 15:53:27.98ID:uKHAyuPa再帰関数は自己満足でしかないな
0228デフォルトの名無しさん
2015/08/13(木) 16:00:20.34ID:Iax2S8IU実用的なプログラミング手法
0229デフォルトの名無しさん
2015/08/13(木) 16:13:22.44ID:t3mydoM30230デフォルトの名無しさん
2015/08/13(木) 16:29:24.52ID:wsd38m6Jつくだけの議論に価値はないから、メアドでも交換して、
勝手にメールでやってくんない？
0231デフォルトの名無しさん
2015/08/13(木) 17:14:18.17ID:dAU/S6bTデザイナか底辺コーダーみたいなヤツらばっか
0232デフォルトの名無しさん
2015/08/13(木) 17:41:32.08ID:FeXmcCf70233デフォルトの名無しさん
2015/08/13(木) 17:55:50.75ID:A9RCljrX0234デフォルトの名無しさん
2015/08/13(木) 19:13:46.18ID:ZdpNokWxループはコンパイル時に最適化かかるから高速化しやすい
0235デフォルトの名無しさん
2015/08/13(木) 19:38:20.24ID:4z/i7w/x0236デフォルトの名無しさん
2015/08/13(木) 23:05:53.46ID:TPLbUV1y速度も含めて、再帰と非再帰でそんなに大騒ぎするほどの違いがあるかなあ。
0237デフォルトの名無しさん
2015/08/13(木) 23:12:53.85ID:WInk48Wa0238デフォルトの名無しさん
2015/08/13(木) 23:47:23.70ID:WInk48Wa再帰使うなと書いてあるだろ。
何言ってんだお前。
0239デフォルトの名無しさん
2015/08/14(金) 00:02:47.08ID:She38G+m0240デフォルトの名無しさん
2015/08/14(金) 00:31:35.66ID:bS+eLMvHこれが国際ルール。
0241デフォルトの名無しさん
2015/08/14(金) 00:38:24.26ID:30JcjEEEID:W1EX3EBl氏曰く、可読性が悪いから許容出来ない。らしい。
0242デフォルトの名無しさん
2015/08/14(金) 00:45:15.19ID:She38G+m0243デフォルトの名無しさん
2015/08/14(金) 00:49:42.60ID:EjQiuBiC0244デフォルトの名無しさん
2015/08/14(金) 00:53:34.88ID:She38G+m0245デフォルトの名無しさん
2015/08/14(金) 02:23:00.05ID:bS+eLMvH再帰を使わなければならない言語は実用性ないからやめとけ。
煽ってるように思うかもしれないが、10年後に思い返してみ。
その通りだったとわかるから。
0246デフォルトの名無しさん
2015/08/14(金) 03:21:13.76ID:EMHxFo3V関数型を選ぶのはコンプレックスとか本来の目的以外がモチベーションになってる
0247デフォルトの名無しさん
2015/08/14(金) 04:02:13.98ID:wyMAq0xx0248デフォルトの名無しさん
2015/08/14(金) 04:50:19.83ID:MLcHO6rW0249デフォルトの名無しさん
2015/08/14(金) 05:07:39.58ID:QRcaU/9J英語は読み間違えるし、コードを読む力が皆無だし
再帰のコードをループに直せないし、
何よりも再帰を使用してはいけないことが理解できない。
プログラマの基礎学力を欠いてる。
0250デフォルトの名無しさん
2015/08/14(金) 05:20:19.69ID:wyMAq0xx0251デフォルトの名無しさん
2015/08/14(金) 05:46:48.29ID:SrkbsMCI読み間違えるんじゃなくて、読んでないんだろ。
何となくそれっぽいこと書けばいいみたいな。
再帰の危険性を指摘した文章を引用して、再帰するべきであると主張してるし。
自前スタックによる実装を示して、再帰してると主張するし。
しかも、読んでないだろとか言いがかりつけてくるし。
打ち負かすのが目的だから話にならない。
CERT CC読むだけでも再帰がなぜいけないのかわかるだろうに。
0252デフォルトの名無しさん
2015/08/14(金) 05:53:10.80ID:SrkbsMCI2chコーディング規約第一条、再帰の禁止。
再帰を用いる者は、50万円以上の過料、あるいは10年以上の禁固刑と処す。
0253デフォルトの名無しさん
2015/08/14(金) 05:55:31.01ID:wyMAq0xxその人禁止されてないって言ってるだけじゃない
言いがかりばっかりだね
0254デフォルトの名無しさん
2015/08/14(金) 05:56:35.55ID:wyMAq0xx0255デフォルトの名無しさん
2015/08/14(金) 06:03:17.11ID:SrkbsMCI再帰の禁止はそれと同じレベルの話。
紀元前においてはそれで良かった。
古い教科書には、再帰による例だって載っているだろう。
昔、0終端を仮定していたようにな。
しかし、現在ではそれは良くないマナー。
全てのセキュリティ勧告が再帰を警告し、すべての規約が再帰を禁止している。
2chにおいては禁固刑になるほどの悪徳とされている。
0256デフォルトの名無しさん
2015/08/14(金) 09:48:40.23ID:IQ5ciGpN0257デフォルトの名無しさん
2015/08/14(金) 13:36:50.53ID:S4Thnq8WあれはC言語のサブセット。
0258デフォルトの名無しさん
2015/08/14(金) 15:18:36.00ID:MLcHO6rW普通にTCRで書けばいいだけ。それどころかそこに
> In principle, any recursive calculation can be remodeled as an iterative
> calculation which will have a smaller impact on some computing resources but
> which may be harder for a human to comprehend.
> The cost to human understanding must be weighed against the practical
> limits of computing resource.
ループは人間が理解するのが先より難しいけど人間が理解するコストは
計算機資源の限界と衡量しなきゃだめよ、って書かれてる。
再帰のほうが人間には読みやすい、ってさ
0259デフォルトの名無しさん
2015/08/14(金) 15:42:19.07ID:S4Thnq8W| ウソつき。 禁止してるのってMISRA-Cだけですね。
| CERT C Secure Coding StandardもISO/IEC 24772:2013も禁止なんかしていませんね。
| 証拠↓
って書かなきゃ読み取れないのか。
0260デフォルトの名無しさん
2015/08/14(金) 16:12:00.57ID:yjzzXtw+0261デフォルトの名無しさん
2015/08/14(金) 17:36:18.62ID:lAGFmjya0262デフォルトの名無しさん
2015/08/14(金) 21:22:39.45ID:JKvGE0+H第一条で再帰が禁止されている。
0263デフォルトの名無しさん
2015/08/14(金) 21:42:25.71ID:tycV63/Uアレを規定せざるを得なかった闇がある
MISRA本はその闇のエピソード、笑いあり涙ありの
感動ストーリーを綴っているんだ
0264デフォルトの名無しさん
2015/08/14(金) 23:59:17.48ID:XChvySBsstatic void sort(int[] a) {
sort(a, a.length - 1);
}
static void sort(int[] a, int i) {
if (i < 0) {
return;
}
sort(a, i, 0);
sort(a, i - 1);
}
static void sort(int[] a, int i, int j) {
if (j >= i) {
return;
}
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
sort(a, i, j + 1);
}
static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
0265デフォルトの名無しさん
2015/08/15(土) 00:18:15.82ID:f9Sa8wCpたとえ正しく動くとしてもこれはないだろう。
でも聞きたいのはそういうことじゃないのかな。
0266デフォルトの名無しさん
2015/08/15(土) 00:22:42.84ID:JxzjZBTNどうしてこれはないと思うのかね？(ヒント:再帰だから)
0267デフォルトの名無しさん
2015/08/15(土) 01:24:19.54ID:f9Sa8wCp馬鹿馬鹿しいけど返事してやるよ。
O(n^2) だからだ。コード書く以前の問題だよ。
0268デフォルトの名無しさん
2015/08/15(土) 01:34:17.46ID:vCc4fVXG0269デフォルトの名無しさん
2015/08/15(土) 01:44:24.34ID:+Mrs40dUこんなひどいアルゴリズムでドヤ顔とかｗ
0270デフォルトの名無しさん
2015/08/15(土) 01:48:48.57ID:WFfeEk5g再帰どころか分割しすぎのクソコードで自爆ｗｗ
static void sort(int [] a){
sort(a, a.length -1, 0);
}
static void sort(int [] a, int i, int j){
if( j < i ){
int t = a[i];
a[i] = a[j];
a[j] = t;
sort(a,i,j+1);
}
else if( i > 0 ){
sort(a,i-1, 0);
}
}
0271デフォルトの名無しさん
2015/08/15(土) 01:49:45.86ID:WFfeEk5gstatic void sort(int [] a, int i, int j){
if( j < i ){
int t = a[j];
a[j] = a[j+1];
a[j] = t;
sort(a,i,j+1);
}
else if( i > 0 ){
sort(a,i-1, 0);
}
}
0272デフォルトの名無しさん
2015/08/15(土) 05:15:13.18ID:IGI9KIAb再帰
# coding: utf-8
def hanoi(disk_number, f, t, w, tower_dict):
if disk_number > 0:
hanoi(disk_number-1, f, w, t, tower_dict)
tower_dict[t].insert(0, tower_dict[f].pop(0))
print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
hanoi(disk_number-1, w, t, f, tower_dict)
if __name__ == '__main__':
disk_number = int(input())
tower_dict = {'left': [i for i in range(1, disk_number+1)], 'center': [], 'right': []}
print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
hanoi(disk_number, 'left', 'right', 'center', tower_dict)
0273デフォルトの名無しさん
2015/08/15(土) 08:34:36.98ID:pcfePhGh0274デフォルトの名無しさん
2015/08/15(土) 08:40:27.84ID:WFfeEk5g何やってんだ俺
static void sort(int[] a, int i, int j){
if( j < i ){
if (a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
sort(a,i,j+1);
}
else if( i > 0 ){
sort(a,i-1, 0);
}
}
型変えてgccで末尾再帰最適化確認した
0275デフォルトの名無しさん
2015/08/15(土) 08:43:31.65ID:aV490TlT0276デフォルトの名無しさん
2015/08/15(土) 09:51:49.02ID:9roGQVeV再帰に向かない物まで再帰にするのが良くないだけだろ？
0277デフォルトの名無しさん
2015/08/15(土) 11:26:39.03ID:LE4LycT3最適化してくれないjsみたいなのは除くとして
0278デフォルトの名無しさん
2015/08/15(土) 12:06:13.60ID:oUuKlgWMその台詞はオプティマイザのご機嫌とって
オブジェダンプかけながらソースを書いていた事があって言ってるのか
0279デフォルトの名無しさん
2015/08/15(土) 17:28:44.82ID:7X/ZNWxVこういう必死さみても再帰の有害さがわかる
0280デフォルトの名無しさん
2015/08/15(土) 17:33:32.28ID:OJGJ2QAvすいません
関数型プログラミング言語でしか再帰書いた事ありません><
0281デフォルトの名無しさん
2015/08/15(土) 23:44:57.75ID:KDDvbpTiどや？
static void sort(int[] a) {
for (int i = a.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
0282デフォルトの名無しさん
2015/08/16(日) 02:27:58.97ID:LltgmYR9副作用死すべし
0283デフォルトの名無しさん
2015/08/16(日) 02:31:35.69ID:ysqlqGaE0284デフォルトの名無しさん
2015/08/16(日) 03:05:47.99ID:IVc263H9オーダーはデータ量が増えればこの項は無視できると
いうふうに項を消した残りかすなんだからデータ量が少ない
情況を仮定するとバブルソートがクイックソートより高速なのは常識。
オーダーを理解できてないアルツハイマーはお前の方。はいバブルソート論破。
0285デフォルトの名無しさん
2015/08/16(日) 03:08:28.72ID:IVc263H9「早すぎる最適化は諸悪の根源である」というプログラムの常識を理解してない池沼の根源。
0286デフォルトの名無しさん
2015/08/16(日) 03:21:51.10ID:ysqlqGaEお、そうだな
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/speed-compare.html
0287デフォルトの名無しさん
2015/08/16(日) 03:35:29.90ID:ysqlqGaEバブルソート{約(1/2)*n(n+1)}は10個以下でquicksortのオーダーを下回る
0288デフォルトの名無しさん
2015/08/16(日) 07:52:21.53ID:42LjL2Kj学校で習った知識を自慢したかったのか？
そーいや夏休みだったなあ
0289デフォルトの名無しさん
2015/08/16(日) 08:10:34.59ID:ysqlqGaE0290デフォルトの名無しさん
2015/08/16(日) 11:35:18.70ID:t2Jj+if90291デフォルトの名無しさん
2015/08/16(日) 13:14:51.24ID:6UxdI0kW絶望的に長くなって読み難くなるものがある。
全員に訊こう。
例えば、多重再帰じゃないと簡潔に書けないものは存在する。イエスかノーか。
0292デフォルトの名無しさん
2015/08/16(日) 13:28:24.19ID:onk31F/8再帰だとと簡潔に書けるものもある。
だからすべての場合で同じ方法を使わず
適切に使えというのは最初から言われていること。
その再帰万能って考え方はいつになったら治るのかね？
0293デフォルトの名無しさん
2015/08/16(日) 13:32:21.21ID:IVc263H9そういうことだな。
0294デフォルトの名無しさん
2015/08/16(日) 13:38:08.54ID:6UxdI0kW0295デフォルトの名無しさん
2015/08/16(日) 13:41:10.33ID:iyw7PDsuほら見ろ、再帰万能じゃねーか。
って言うつもりだろう？
面白そうだから俺がノーと
言ってやろうｗ
ノーだ。ノー。
0296デフォルトの名無しさん
2015/08/16(日) 13:45:55.82ID:H2axMdYbバカも休み休み言え。
0297デフォルトの名無しさん
2015/08/16(日) 13:47:02.94ID:6UxdI0kW俺は「ものもある」「ものは存在する」と訊いてるんだから、「ノー」なら完全否定派なだけだ。
別に面白い展開は無いぞ。
>>296
じゃあCにしよう。
0298デフォルトの名無しさん
2015/08/16(日) 13:49:00.82ID:iyw7PDsuなんか、策でもあるんだろ。
誘導尋問だか、屁理屈や揚げ足だか、重箱の隅や失言狙いかしらんけど。
言葉尻を捕らえようとする戦略なんだろうから
生暖かく見てやろうぜ。
0299デフォルトの名無しさん
2015/08/16(日) 13:51:11.93ID:iyw7PDsuその後の展開（レス）は無いのかよｗ
0300デフォルトの名無しさん
2015/08/16(日) 14:07:57.73ID:t2Jj+if9どんなケース？
という疑問を抱くから、ノーかな。
0301デフォルトの名無しさん
2015/08/16(日) 14:16:38.84ID:bhCkQFe7深さ優先でもスタックオーバーフローを考慮しなきゃいけない状況ならループで書く。
要は、状態を自分で管理して関数のパラメータとして引き回すくらいならループにする。
0302デフォルトの名無しさん
2015/08/16(日) 14:20:58.92ID:H2axMdYbこれが、このスレのこれまでの結論なので、
答えはノー
∵ 全ての再帰は簡潔でない
0303デフォルトの名無しさん
2015/08/16(日) 14:28:14.30ID:6UxdI0kW0304デフォルトの名無しさん
2015/08/16(日) 15:06:07.80ID:LltgmYR9スタックオーバーフローしないよ
ヒープ使いまくるけどね
0305デフォルトの名無しさん
2015/08/16(日) 17:45:23.08ID:t2Jj+if90306デフォルトの名無しさん
2015/08/16(日) 20:22:40.46ID:kniDeEJc>要は、状態を自分で管理して関数のパラメータとして引き回すくらいならループにする。
再帰使う人間はまさにこれがいやだから再帰使うんだが
そもそも、深さ優先か幅優先かで書き方変えるとかあり得ない
抽象化に失敗してるだけだ
0307デフォルトの名無しさん
2015/08/16(日) 21:43:54.44ID:IVc263H9幅優先探索をループで書いて、深さ優先探索を再帰で書くのはよくあるケースだと思うけどな
抽象化は関係ないｗ
0308デフォルトの名無しさん
2015/08/16(日) 22:39:02.64ID:ysqlqGaEお前あれだけ恥ずかしい事書いておいてよくまた出てこれるなｗ
0309デフォルトの名無しさん
2015/08/16(日) 22:47:59.54ID:bhCkQFe7単にスタックかキューかの違いなので、このコードなら $strategy を array_pop にすれば深さ優先で array_shift にすれば幅優先。
ループでも再帰でも、そこの戦略は簡単に抽象化できる。
<?php
class tree {
public $value;
public $children;
function __construct($value, $children = []) {
$this->value = $value;
$this->children = $children;
}
}
// [1, [2, [3, 4]], [5, [6, 7]]]
$sample = new tree(1, [new tree(2, [new tree(3), new tree(4)]), new tree(5, [new tree(6), new tree(7)])]);
function traverse($tree, $strategy) {
$task = [$tree];
while ($task) {
$node = $strategy($task);
echo $node->value;
foreach ($node->children as $c) array_push($task, $c);
}
}
traverse($sample, 'array_shift'); echo "\n"; // 幅優先
traverse($sample, 'array_pop'); echo "\n"; // 深さ優先。right to left になるのはご愛嬌。foreach の走査に array_reverse を入れれば left to right になる。
0310デフォルトの名無しさん
2015/08/16(日) 22:55:01.73ID:bhCkQFe7まず深さ優先なら再帰で書くってのは、次の depth_first_rec のように書けば $task をコードから消せる。状態管理なんてのは本質じゃないので消せるならそう書く。
function depth_first_rec($node) {
echo $node->value;
foreach ($node->children as $c) depth_first_rec($c);
}
depth_first_rec($sample); echo "\n";
一方、幅優先を再帰で書こうとしたら、$task を再帰のパラメータに乗せなきゃならない。
関数のシグネチャはアルゴリズムの本質を表明すべきだと思うので、$task みたいなものを出したくない。これならループで書く。
もちろん関数型言語で書く人は、綺麗な関数でラップして traverse_rec みたいなのは内部に隠蔽するだろうけど、
見比べてみればそれって、>>309 の traverse が「綺麗な」外側の関数で traverse_rec が while ループに対応する。全く同じことやってる。
function traverse_rec($strategy, $task) {
if ($task) {
$node = $strategy($task);
echo $node->value;
foreach ($node->children as $c) array_push($task, $c);
traverse_rec($strategy, $task);
}
}
traverse_rec('array_shift', [$sample]); echo "\n";
traverse_rec('array_pop', [$sample]); echo "\n";
0311デフォルトの名無しさん
2015/08/16(日) 22:57:42.02ID:bhCkQFe7おやすみ。
0312デフォルトの名無しさん
2015/08/16(日) 23:04:29.84ID:qX4pihue> 一方、幅優先を再帰で書こうとしたら、$task を再帰のパラメータに乗せなきゃならない。
載せる必要はない。
普通は関数内関数（クロージャー含む）を使って
再帰関数の外の変数を使うもの
C言語ではやりにくいが、グローバル変数を使えば可能
こんな常識も知らないのか？
0313デフォルトの名無しさん
2015/08/16(日) 23:10:17.19ID:bhCkQFe7コメントありがとう。
今回の問題でそういう実装にすると $task に破壊的代入を行うことになると思うけど、
それを気にしないなら別によいと思う。
0314デフォルトの名無しさん
2015/08/16(日) 23:23:41.26ID:ysqlqGaEとてもわかりやすいコード乙
>>312
最適化とステートレス化のためにパラメタで渡すのは常識だろ
荒らすな
0315デフォルトの名無しさん
2015/08/16(日) 23:24:18.75ID:5vUfdwLX再帰使うと攻撃に弱くなる。
0316デフォルトの名無しさん
2015/08/16(日) 23:30:59.94ID:5vUfdwLX操作がやりやすくなる。
直列された状態では通常、前から後ろに移動していくと、深さ優先探索の状態になる。
デメリットは、キャッシュに乗りにくくなることと、使用メモリー量が
大きくなること。
ただし、操作のコストが一般に低くなるので、十分ペイする。
そして攻撃に強い。
0317デフォルトの名無しさん
2015/08/16(日) 23:32:55.62ID:qX4pihue> 最適化とステートレス化のためにパラメタで渡すのは常識だろ
お前、最適化と言ったら、スピード上げることしか思いつかないのか？
「可読性の最適化」だよ。
可読性がいい方向にコードを最適化することで
メンテナンス性を上げることができる。
お前は単なるスピード狂。
お前が書くコードは読みづらい
0318デフォルトの名無しさん
2015/08/16(日) 23:44:57.83ID:5vUfdwLX0319デフォルトの名無しさん
2015/08/16(日) 23:47:34.77ID:5vUfdwLXグローバル変数は、再利用性を著しく損なうので避けるべき。
0320デフォルトの名無しさん
2015/08/16(日) 23:55:06.97ID:ysqlqGaEスタック消費抑えるために最適化するのは常識なんだが
どこの世界の似非プログラマ？
0321デフォルトの名無しさん
2015/08/17(月) 00:08:45.56ID:kjPlSxav今のアーキテクチャにはあわんでしょ
0322デフォルトの名無しさん
2015/08/17(月) 00:28:50.83ID:ZK4qdIAD0323デフォルトの名無しさん
2015/08/17(月) 00:36:22.18ID:I1eaKx/Iバブルソートで論破されて必死やなｗ
>>309
衒学的なオナニーされておられるところ大変恐縮ですが、結局ループでいいってことだろ。
抽象化言いたいだけやろ。しょうもな。
0324デフォルトの名無しさん
2015/08/17(月) 00:40:53.56ID:I1eaKx/I再帰厨は潔く観念して俺に敬服するべきだと思うんだよね。
0325デフォルトの名無しさん
2015/08/17(月) 01:17:00.24ID:3kIm88tb0326デフォルトの名無しさん
2015/08/17(月) 01:44:30.24ID:y5LPXYrpほんこれ。
0327デフォルトの名無しさん
2015/08/17(月) 02:05:13.63ID:PZrD2gdn再帰を使わないと解決できない問題があるとすれば、再帰を使えない事がその人の限界になる。
今でも普通クイックソートだね．
次数が減ったら挿入ソートや選択ソートに切り替えはするが
0329デフォルトの名無しさん
2015/08/17(月) 08:18:37.09ID:bgkOWECjこれ常識
ループの可読性が悪いなんて言ってるのはレベル低すぎ
0330デフォルトの名無しさん
2015/08/17(月) 09:50:03.46ID:fqo2f2L7while()って読み難くありませんか？
0331デフォルトの名無しさん
2015/08/17(月) 10:03:44.62ID:HKx5lNza質問じゃなくて、コードを書いて、
このコードとこのコードを比較して
while()は読みづらいって言いなさい。
他人の失言を狙ってるのバレバレだから。
0332デフォルトの名無しさん
2015/08/17(月) 10:29:19.62ID:i5qYhPSf繰り返しで書いたクイックソートは再帰で書いたそれに比べて可読性が低いのだ。
0333デフォルトの名無しさん
2015/08/17(月) 10:50:30.82ID:HKx5lNza0334デフォルトの名無しさん
2015/08/17(月) 10:52:50.02ID:PCwhqe1a頭の中で最適化すればループになるし、という話だよね。
どっちでもいい人にとってはこれほど無駄な議論はない。
結局どちらかしか使えない無能たちの罵り合いでしかない。
0335デフォルトの名無しさん
2015/08/17(月) 10:56:29.07ID:HKx5lNzaいや、そうじゃないんだよ。
某関数型言語では、その言語の制約上
再帰で書くしかないんだよ。
だけど、自分が使ってる言語は優れていると
思いたいものだから、再帰しか使えない制約ではなく
再帰のほうが優れてるかということにしたいんだよ。
どちらかしか使えない人なんていない。
関数型言語が使えないだけ。
0336デフォルトの名無しさん
2015/08/17(月) 11:02:29.07ID:PZrD2gdn関数コールが少ない分、ループの方が圧倒的に速い。
速度を追求するならループになる。
0337デフォルトの名無しさん
2015/08/17(月) 12:05:32.92ID:fqo2f2L7for( ;<<ループの終了条件>>; ){ p() } は
for( ;<<ループの終了条件>>; p()){} の内、必要な情報だけ第三引数に抽出することができるが、
while(<<ループの終了条件>>) { p() } だと
どんな情報に着目するべきかは終了条件以外のヒントがない。
それでwhile()は難しいかと。
0338デフォルトの名無しさん
2015/08/17(月) 12:18:46.07ID:HKx5lNzaなんの情報が必要なんだよ？
終了条件さえあれば十分だろ？
ジェネレータとか、そういうもんだぞ。
0339デフォルトの名無しさん
2015/08/17(月) 13:15:13.35ID:i5qYhPSfお前、バカだろう。
繰り返しで書いたクイックソートは再帰で書いたそれに比べて可読性が低いのだ。
仕様上、繰り返しを記述出来ない言語は比較の対象外だ。
0340デフォルトの名無しさん
2015/08/17(月) 13:43:37.43ID:bgkOWECj読めるコードであれば何の問題もない。
実際にプログラマは比較関数を自作して
クイックソートのライブラリに当てはめるだけなんだし。
実用性を備えるループ方式と、
使用厳禁の再帰方式とじゃあ比較にならない。
0341デフォルトの名無しさん
2015/08/17(月) 13:51:20.52ID:i5qYhPSf> ループの可読性が悪いなんて言ってるのはレベル低すぎ
0342デフォルトの名無しさん
2015/08/17(月) 13:57:08.88ID:bgkOWECjクイックソートのコードは十分に読めるコード
ループの可読性が悪いなんて言ってるのはレベル低すぎ
0343デフォルトの名無しさん
2015/08/17(月) 14:08:09.19ID:J0NniHMW0344デフォルトの名無しさん
2015/08/17(月) 14:09:55.63ID:bgkOWECj0345デフォルトの名無しさん
2015/08/17(月) 14:18:37.75ID:HKx5lNzaただ可読性は高い方がいい。
ただそれだけのことだろう？
0346デフォルトの名無しさん
2015/08/17(月) 14:53:55.09ID:i5qYhPSf(可読性悪くても)読めるコードなら問題ない。と言いつつ。
同レス内で、ループの可読性の低さを否定してる。
お前、バカだろう。
0347デフォルトの名無しさん
2015/08/17(月) 18:09:10.76ID:5EpnwL1P書いてみろよ
というより，クイックソートはループでは書けない
ヒープにスタック構造を持ち込んでおきながら「ループで書きましたぁ」とか‥
0350デフォルトの名無しさん
2015/08/17(月) 20:16:45.10ID:rLKFJTDK再帰処理のクイックソート vs 非再帰処理のクイックソート
http://www.drk7.jp/MT/archives/000995.html
再帰を使わないでクイックソートは実装できるね。
しかもそっちのほうが速い
0351デフォルトの名無しさん
2015/08/17(月) 20:18:08.13ID:rlqXRw2u0352デフォルトの名無しさん
2015/08/17(月) 20:40:03.62ID:RDuEyBYc可読性に関する再帰のコストはほぼ周りがCS卒かどうかで決まる
CS勉強してりゃ再帰の方が圧倒的に読みやすいし加工しやすいし最適化しやすい
してなきゃループがわかりやすい。そんだけ。
0353デフォルトの名無しさん
2015/08/17(月) 20:52:33.62ID:bgkOWECjこれまで話を完全に無視して、
ループでは書けないなどと言い出すものまで現れるのかよ・・・
それ，結局データ構造にスタックを持ち込んでいるね‥
非再帰とはいいにくい，普通に再帰で書いたほうがいいんじゃないかな‥
0355デフォルトの名無しさん
2015/08/17(月) 21:27:59.23ID:rlqXRw2uサンクがどれだけ詰まれてくか目に見えないじゃない
ああ、Lispならわかるんだっけ
0356デフォルトの名無しさん
2015/08/17(月) 21:34:14.06ID:5i910ycA再帰による実装は、コードが簡潔になる利点はあるものの、
スタックが足りなくなる恐れがあります。
ソート作業は、大量のデータに対して行うことも多いので、
この問題は致命的です。
この問題は、自力でスタックを制御できるようにして、
再帰構造を取りやめれば解決できます。
スタックサイズは log2 n 以上の容量があれば足りることが実証されています。
int型が 64ビットだとしても、たかだか 128要素で済むので、定数で構わない
ttp://u222u.info/nh3Q
0357デフォルトの名無しさん
2015/08/17(月) 23:29:17.65ID:i5qYhPSfお前、バカだろう。
perlは関数呼び出しのオーバーヘッドがでかいのであたりまえ。
java版 繰り返し:平均 408.86 ms, 再帰:平均 236.81 ms
http://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
The average of the iterative solution was 408.86 ms while of recursive was 236.81 ms
However -these are constant number of ops, while not changing the number of "iterations".
アンチ再帰の根拠がまた一つ否定された。
0358デフォルトの名無しさん
2015/08/18(火) 00:54:03.83ID:iaUEwJyIさすがに古すぎる
単位にサイクル使ってるやつだけ参考にしろ
0359デフォルトの名無しさん
2015/08/18(火) 04:11:08.35ID:6SfpmUjrlog2 nに限定するならメディアン必須になるし、
投機的実行や並列化の恩恵にも預かれないぞ
それこそ「現在のアーキテクチャに合わない」
>>358
サイクルって何？
0360デフォルトの名無しさん
2015/08/18(火) 08:16:42.70ID:FMltliIelog N 「以上」なのでメディアン（割りきれるか割りきれないかだよね？）は融通効くし、
パイプラインは関係ないと思うんだけど具体的にどう、最適化に悪影響なの？
0361デフォルトの名無しさん
2015/08/18(火) 09:23:27.84ID:6SfpmUjr並列は言わずもがな、分岐が増えるほど投機実行も不利
>log N 「以上」なのでメディアン（割りきれるか割りきれないかだよね？）は融通効くし
だから全要素からのメディアン取るのが必須になるだろと
さもなくば埋まったら切るとかの戦略でもない限り、大きさ固定のスタックは無理
0362デフォルトの名無しさん
2015/08/18(火) 09:32:58.52ID:6SfpmUjrごめん、リンク先見てなかった
小さい方だけ計算していくなら、再帰でもループでも可能だね
0363デフォルトの名無しさん
2015/08/18(火) 09:55:04.16ID:biaMMpq3処理速度やメモリ消費の点で効率が悪い。
これが真実。
効率の求められるクイックソートはループ方式ですね。
0364デフォルトの名無しさん
2015/08/18(火) 10:02:42.34ID:FMltliIe実は自分もメディアンのこと、ピボットのことだと気づかなかったから変なこと言ってました……
なんかlog Nとスタックのワードだけで勝手に勘違いしてた。
恥ずかしいからROMります……
0365デフォルトの名無しさん
2015/08/19(水) 06:32:50.20ID:h1yQg/qVオーダーと比較するんだからCPUサイクルのわけないだろうし
0366デフォルトの名無しさん
2015/08/19(水) 06:48:19.79ID:8XFwGYsLこれは既に常識。
0367デフォルトの名無しさん
2015/08/19(水) 06:53:40.18ID:3Ipmhs8Yワトソンでは基幹部分で使われている。大変だ。
0368デフォルトの名無しさん
2015/08/19(水) 06:59:26.41ID:8XFwGYsL0369デフォルトの名無しさん
2015/08/19(水) 08:04:33.92ID:8XFwGYsL◯◯では使われてる → じゃあ◯◯は使うな、使われてないのに適当なこと言ってたら訴えられますよ？
再帰下降法も使うなというのか？ → 再帰下降法は使うな、入力の解析を再帰で行うのは最も危険。
0370デフォルトの名無しさん
2015/08/19(水) 08:08:05.43ID:3Ipmhs8Yワトソンの基幹部分にPrologが使われているというのは常識だが。
0371デフォルトの名無しさん
2015/08/19(水) 08:18:36.42ID:cBcKF4Irだから一般化しすぎだろ
scalaとかでも同じ事言うの?
0372デフォルトの名無しさん
2015/08/19(水) 08:20:15.23ID:8XFwGYsLいまさら再帰を使うべきというのはおかしい。
しかも、何故かWEB系の人に多いのがおかしすぎる。
WEBは最も再帰を避けるべきであろう。
0373デフォルトの名無しさん
2015/08/19(水) 08:25:28.68ID:8XFwGYsL言語が再帰を別のアルゴリズムに変更することを保証しているなら、
使っても良いだろう。
しかし保証しないのであれば、使うべきではない。
例えば、一般的なケースでは大丈夫 → これは使うな、攻撃者は一般的なケースで攻撃してこない。
再帰下降法について擁護するものは、大体一般的な例を述べるが、攻撃者は
最悪のケースで攻撃してくる。
0374デフォルトの名無しさん
2015/08/19(水) 08:27:48.29ID:8XFwGYsL大抵のコンパイラがループに展開する → これは使うべきではない、言語が保証しない限り
使ってはいけない。
0375デフォルトの名無しさん
2015/08/19(水) 08:32:59.75ID:cBcKF4Irいやだから末尾再帰は確かにループに展開されるけど
普通の再帰は展開されない(余再帰とかいうあれ)
val one:Stream[Int] = 1#::one
0376デフォルトの名無しさん
2015/08/19(水) 08:38:24.50ID:8XFwGYsLじゃあ使うなよ。
再帰がヒープに展開されるなら、現状では使っても良いとするしかないだろう。
現在のコンピュータにはその程度の安全性しかない。
一方、マシンスタックが消費されるなら、これは使ってはいけない。
言語が保証できるかどうかはこういう話。
逆に言うと、保証できる言語は本質的に遅いから変えたほうが良いよ?
0377デフォルトの名無しさん
2015/08/19(水) 08:40:13.17ID:cBcKF4Irって言われてもな
一般化しすぎ
0378デフォルトの名無しさん
2015/08/19(水) 08:43:41.41ID:cBcKF4Ir遅延データ構造で余再帰使うなってあんた
0379デフォルトの名無しさん
2015/08/19(水) 08:47:34.95ID:cBcKF4Irそこで末尾再帰なんかしたらそれこそ危ない
0380デフォルトの名無しさん
2015/08/19(水) 08:58:49.14ID:8XFwGYsL遅延評価によってマシンスタック消費の抑制を保証できるのであれば、
使っても良いだろう。
しかし、保証するという事はどういうことが起きるのか、良く考えたほうが良い。
大抵のケースで保障できる → これは使ってはいけない、条件が付いた時点で保障できていない。
0381デフォルトの名無しさん
2015/08/19(水) 09:01:52.31ID:8XFwGYsL逆に言うと、再帰で説明する教科書は、既に古いので使うべきでない。
20世紀の教科書。
0382デフォルトの名無しさん
2015/08/19(水) 09:04:29.34ID:8XFwGYsL議論を避けている。
結論が出るまで使わないほうが良い。
0383デフォルトの名無しさん
2015/08/19(水) 09:36:58.20ID:3Ipmhs8Y0384デフォルトの名無しさん
2015/08/19(水) 10:38:04.52ID:qmnFr7bU関数型言語なんて再帰キチガイが再帰を正当化するために作り出した言語で
あって、逆に言えば関数型言語でない限り再帰に正当性は一切ない。
再帰キチガイは再帰に問題がありまくることを知っているからこそ、再帰を
満喫するために関数型言語なんていうキチガイ非効率言語を作ったんだから、
そこに収容されていて、一般論のスレに出てくるな。
0385デフォルトの名無しさん
2015/08/19(水) 10:55:26.78ID:N4waeMow0386デフォルトの名無しさん
2015/08/19(水) 11:13:42.96ID:h1yQg/qV0387デフォルトの名無しさん
2015/08/19(水) 11:17:04.81ID:irPHrK71そうですね。
>>383
最近のライブラリが歳入可能性に言及するのは、スレッド安全に関連する話です。
関係ない話題をうまく混ぜ込むのが最近のトレンドですが、ム板でやると
馬鹿だと思われますよ。
0388デフォルトの名無しさん
2015/08/19(水) 11:19:08.64ID:irPHrK71関数型言語は言語が再帰を避けてくれるから安全だと言いたいんですよね？
言語が避けてくれるのは、再帰が危険だからですよね？
0389デフォルトの名無しさん
2015/08/19(水) 11:22:24.20ID:irPHrK71威勢の良い宣伝は良くあります。
それはどの言語でも経験したことです。
例えばJavaはC/C++のおよそ20倍高速だった時代もあったのです。
現在は、関数型言語がC/C++のおよそ100倍高速なのです。
従っていずれ1/100になるでしょう。
0390デフォルトの名無しさん
2015/08/19(水) 11:28:11.15ID:irPHrK71これがC++が使われるようになった理由の一つです。
Objective-Cは逆に、Cの二倍速く、Cの二倍省メモリーだったのです。
従ってその時点でObjective-Cは負けていました。
過剰な宣伝が通用するのは、誰も使っていなかったからなのです。
関数型言語がC/C++の100倍まで高速化したのは、本当の本当に誰も使っていないからでしょう。
0391デフォルトの名無しさん
2015/08/19(水) 12:45:01.27ID:yS+hRb+Cうまいことを言う！
これコピーして保存しとくぜ。
0392デフォルトの名無しさん
2015/08/19(水) 23:06:26.12ID:EEfFXLQD0393デフォルトの名無しさん
2015/08/20(木) 06:59:05.01ID:cFwOLAtjうんこは食べ物ですって言うようなもん
0394デフォルトの名無しさん
2015/08/20(木) 10:35:31.02ID:PsQjKp/hここに「おはむぅ('ω'`)」って書きこんで
0395デフォルトの名無しさん
2015/08/20(木) 12:12:44.84ID:5WCLlVT00396デフォルトの名無しさん
2015/08/20(木) 17:13:17.66ID:5F2FSsFe0397デフォルトの名無しさん
2015/08/20(木) 17:14:14.66ID:5F2FSsFe0398デフォルトの名無しさん
2015/08/20(木) 17:42:02.04ID:vSASgIXr0399デフォルトの名無しさん
2015/08/20(木) 17:42:58.19ID:2qNm8QiI関数型でも単純再帰はgotoみたいなプリミティブな構造だから
構造プログラミングにおけるwhileやforに相当するrecursion schemes使えって言われてるじゃん
（例：catamorphismはfoldに相当するなど）
recursion schemes含めて再帰が有用というなら妥当するけど、どういう論旨で再帰が有用とおっしゃる？
0400デフォルトの名無しさん
2015/08/20(木) 20:45:39.40ID:5WCLlVT0foldやmap使えってのを素人向けに強調するのは構わんが、行き過ぎるのも愚劣
0401デフォルトの名無しさん
2015/08/20(木) 21:03:03.09ID:2qNm8QiIなぜなら再帰で書いた関数は変更に弱いから
おもちゃみたいなコードしか書かないなら別だがね
0402デフォルトの名無しさん
2015/08/20(木) 22:00:29.18ID:5WCLlVT0>なぜなら再帰で書いた関数は変更に弱いから
>おもちゃみたいなコードしか書かないなら別だがね
はあ？
0403デフォルトの名無しさん
2015/08/21(金) 00:21:00.76ID:IS5nxfT5迷惑だから社会に出てくんなよ
0404デフォルトの名無しさん
2015/08/21(金) 00:25:28.79ID:D+2gPP3C基本的には再帰よりも高階関数というか型クラスに定義してある汎用的な関数を使ったほうがいい
同じ事ができるならより弱い力のものを使ったほうがいいし(monadよりapplicative,applicativeよりfunctor)
が型クラスのインスタンス作る時に再帰で実装する時はあるよ
0405デフォルトの名無しさん
2015/08/21(金) 00:31:28.66ID:D+2gPP3Cwhile、再代入、ダウンキャストしまくりでとても関数型プログラミングとは言えない
利用者にとってはライブラリが関数型プログラミングで実装してあるかどうかよりも
それを使って関数型プログラミングできる方が重要なんだからいいけど
0406デフォルトの名無しさん
2015/08/21(金) 03:02:31.30ID:wrsjniww普通の再帰で書くことは少なくないしお互いに読みやすい
fold厨とポイントフリー厨は同じ箱
0407デフォルトの名無しさん
2015/08/21(金) 09:15:46.95ID:TIO5PnJE何のお仕事？
0408デフォルトの名無しさん
2015/08/21(金) 12:24:12.68ID:+b9Sq2ljhaskellで探索アルゴリズムも書けない奴はhaskellをいじるのはまだ早い
0409デフォルトの名無しさん
2015/08/21(金) 16:54:57.68ID:0U24jQiQ0410デフォルトの名無しさん
2015/08/21(金) 17:05:56.55ID:cNm3l2b6インターネットが普及してない時代に
C言語で実装したことがあるからなぁ。
わざわざ言語変えて実装するまでもないかな。
0411デフォルトの名無しさん
2015/08/21(金) 19:59:06.06ID:sO1LNJ7K凄いと思えるやつに会ったことがない
ただの手段で目的じゃねーからな
目的を達成するために適したものを選んで使うのが道具
0412デフォルトの名無しさん
2015/08/21(金) 20:11:40.29ID:D0T0zJ3M普通だったらもっと高級言語使って、再帰も拘らず自由に使って
楽しようとするでしょう。
0413デフォルトの名無しさん
2015/08/21(金) 20:23:54.14ID:DXj+sr9Dフィボナッチ数列を例にとると、初項から順番にループを使って計算させることは簡単だけど、
そこから f(n) = f(n-1) + f(n-2) という数式に落とすのが苦手という感じ
0414デフォルトの名無しさん
2015/08/21(金) 20:25:32.36ID:106+9rwN0415デフォルトの名無しさん
2015/08/21(金) 20:29:42.52ID:DXj+sr9D直接計算した方が速いよ
でも抽象化はバグを作り込みにくくすることを目的にしてるからね
目的が違うとしか言いようがない
ガベージコレクタだってそうさ
プログラマにメモリ管理をやらせないようにしてバグの源を減らしているんだが、
ガベージコレクタが走ってる間は固まってしまうというデメリットがある
0416デフォルトの名無しさん
2015/08/21(金) 20:37:23.27ID:106+9rwN0417デフォルトの名無しさん
2015/08/21(金) 21:25:21.72ID:w5MKuYb1GUIならJavascriptの時代だし、サーバーサイドならHaskell一択。
まあそんな時代。
そういうわけで、ウェブブラウザをHaskellで、ウェブサーバをJavascriptで
書いてみよう。
プロの皆、頼んだよ。
0418デフォルトの名無しさん
2015/08/21(金) 22:11:12.63ID:uW+oAt+Bサーバーをscalaで書こう
0419デフォルトの名無しさん
2015/08/21(金) 22:17:46.51ID:gulw8KQa0420デフォルトの名無しさん
2015/08/21(金) 22:22:10.87ID:MAihWaWVブラウザをHaskellで書こう。
0421デフォルトの名無しさん
2015/08/21(金) 22:29:51.21ID:XU9Q1w5tバカはお前だハゲ。
再帰のプログラム見てみろよ。
while (l < h) {
if (arr[l] < piv) {
l++;
} else if (arr[h] >= piv) {
h--;
} else {
swap(arr,l,h);
}
}
思いっきりループ使ってんじゃねえかｗｗｗｗ
0422デフォルトの名無しさん
2015/08/21(金) 22:31:45.44ID:XU9Q1w5tスタックを使って何が悪い。
ループとスタックこれがハードボイルド。
再帰はただのチンカス。
0423デフォルトの名無しさん
2015/08/21(金) 23:18:43.29ID:kMLZ+IBAスタック使っといて再帰ダメとはなんだ！！！
とか思ったんじゃないの。
0424デフォルトの名無しさん
2015/08/21(金) 23:36:53.53ID:D+2gPP3Cアドテク
0425デフォルトの名無しさん
2015/08/22(土) 00:38:22.30ID:xKKBKjQeリソースの上限見積もりをしない事が問題なんだよな
再帰使ってもリミッタかけて上限界保障すれば別にいいけど
上限下限当ててくと見積もりにくさやパフォーマンスの超劣化が表面化してくるんだよなぁ
0426デフォルトの名無しさん
2015/08/22(土) 01:32:21.16ID:B3Y3H6bu> 言語、ツール、OS、デザインパターンみたいな道具や手法に拘るやつで
> 凄いと思えるやつに会ったことがない
単にお前が凄いやつにあったこと無いだけだろｗ
お前の言う凄いやつが誰か知らないから、
有名人でいいや。
凄いやつで、言語、ツール、OS、デザインパターンに
拘らないと言ってる奴いるか？
0427デフォルトの名無しさん
2015/08/22(土) 08:06:55.74ID:qggPju080428デフォルトの名無しさん
2015/08/22(土) 08:46:01.92ID:4IPZDgMf>>411は会った事がない。と言ってるだけで、存在しないとは言ってない。
言いがかりつけないように。
0429デフォルトの名無しさん
2015/08/22(土) 09:04:25.73ID:xKKBKjQe製品の性能重視したほうがいいよ
バグ発生率、実行性能、メモリサイズ、消費電力、メンテナンスコスト
こーいうの数値化して客観的に比較して現実と向き合ったほうがいいよ
0430デフォルトの名無しさん
2015/08/22(土) 09:42:53.71ID:P/XTDL5mただ、すごい人はこだわりを外れたとこでもやっぱりすごいんだけど
0431デフォルトの名無しさん
2015/08/22(土) 11:28:59.69ID:B3Y3H6buだから、あったことがないだけだろ。って
書いてあるだろ。
例えば、俺だってシューズに拘るやつで
凄いと思えるマラソンランナーに会ったことがない。
0432デフォルトの名無しさん
2015/08/22(土) 11:31:34.10ID:B3Y3H6bu> バグ発生率、実行性能、メモリサイズ、消費電力、メンテナンスコスト
> こーいうの数値化して客観的に比較して現実と向き合ったほうがいいよ
そんなことはわかってる。
どうやってそれを数値化し、どうやってそれを解決するか。
それを口に出して言うことが重要だ。
で、君は、どうやればいいと思う？
「根性で頑張る」は手法ではないよ。
0433デフォルトの名無しさん
2015/08/22(土) 15:57:53.79ID:gOdxnhpvクソどもが
0434デフォルトの名無しさん
2015/08/22(土) 15:58:17.75ID:Nzlin5Sx0435デフォルトの名無しさん
2015/08/22(土) 16:17:27.41ID:4AYLR5mV鉄則！プログラミングの初歩の初歩！
再帰を気にせずに使ってしまうのは
ただの趣味プログラマ。
0436デフォルトの名無しさん
2015/08/22(土) 19:12:47.71ID:KyZWN2Ugツリーコントロールにバインドするデータは再起で扱うしかないだろ
0437デフォルトの名無しさん
2015/08/22(土) 19:57:12.11ID:4IPZDgMf0438デフォルトの名無しさん
2015/08/22(土) 22:48:47.92ID:8n3Hy4+Y0439デフォルトの名無しさん
2015/08/22(土) 22:51:07.69ID:XZXv5ALV0440デフォルトの名無しさん
2015/08/22(土) 23:39:22.15ID:Nzlin5Sx見積れないなら危険だから使わないか例外吐くようにするべき
ループと等価だからループで置き換えろっていう人もいるが
ループにしたからと言って危険が0になる訳ではなく
どのみち例外を吐く必要がある
0441デフォルトの名無しさん
2015/08/22(土) 23:45:35.99ID:XZXv5ALV0442デフォルトの名無しさん
2015/08/23(日) 00:46:58.86ID:cJWS/2ha数学的論理的思考を欠いている。
情報処理のまともな思考力があれば
ループにし、かつ危険を０にしたコードを作成すべき。
0443デフォルトの名無しさん
2015/08/23(日) 01:57:15.79ID:vCSJ96fF0444デフォルトの名無しさん
2015/08/23(日) 01:59:37.69ID:myL1fwDZ0445デフォルトの名無しさん
2015/08/23(日) 03:53:30.61ID:dUB2+H1B0446デフォルトの名無しさん
2015/08/23(日) 08:40:52.24ID:F/ISrncw手間は別としてループと条件分岐に置き換えられないわけがない
ループのほうが常に簡単って言ってるやつは
もっと深いアーキ寄りの事を考えてるから簡単と感じるんだろ
抽象化や数学レベルの話ではない
0447デフォルトの名無しさん
2015/08/23(日) 09:09:45.85ID:hZLJ7+aOそもそも等価なんだから
機械的に置き換える万能な方法があるから
「簡単だ」って言ってるんじゃね
0448デフォルトの名無しさん
2015/08/23(日) 09:36:44.01ID:4UX4HcJnそれより上位層になると人間様が読み書きし易い再帰で（最適化は底辺に任せる）。
もっと上位になるとループも再帰も使わず、誰かが用意した高階関数を使うだけ。
ってので合ってる？
自分で高階関数書くときは、ほとんどループで、たまに再帰。
0449デフォルトの名無しさん
2015/08/23(日) 09:47:58.57ID:dUB2+H1B> もっと深いアーキ寄りの事を考えてるから簡単と感じるんだろ
そんなのは本来は機械にまかせること
高級言語はそういう考えを排除するようにできてきたんだからね
アーキのこと考えてやるならアセンブラ使ってレジスタのことでも考えておけばいい
0450デフォルトの名無しさん
2015/08/23(日) 09:53:47.88ID:F/ISrncw理論上最高性能の高級関数を作ることを要求される最底辺が居てな
オプソの大半は環境依存なくしてぬるく作ってあるから
実装としてはまだ最底辺ではないよ
0451デフォルトの名無しさん
2015/08/23(日) 09:58:49.19ID:btbbls/X0452デフォルトの名無しさん
2015/08/23(日) 10:35:42.23ID:hZLJ7+aO0453デフォルトの名無しさん
2015/08/23(日) 15:29:52.83ID:vCSJ96fF0454デフォルトの名無しさん
2015/08/23(日) 15:51:18.07ID:FI0qqD1g最近は動的にスタック領域増えたりしないの？
0455デフォルトの名無しさん
2015/08/23(日) 16:21:24.92ID:nWiiCp/4再帰だろうとgotoだろうとかまへんよ
0456デフォルトの名無しさん
2015/08/23(日) 17:58:27.10ID:2tV8XcQZ0457デフォルトの名無しさん
2015/08/23(日) 19:17:08.80ID:myL1fwDZ計算論の話なら抽象的なレジスタマシンでミニマルな計算可能関数のセットを
作り上げた後はレジスタマシンのことはまったく気にしないものだけどな
0458デフォルトの名無しさん
2015/08/23(日) 20:04:00.55ID:5Eh/eQsv破壊的代入を毛嫌いするのは経験が足りない
0459デフォルトの名無しさん
2015/08/23(日) 20:16:52.93ID:c9xDZ4H5どっちつかずのタマムシ野郎はやる気が足りない？
0460デフォルトの名無しさん
2015/08/23(日) 20:17:46.05ID:c9xDZ4H5あれクイック詐欺だからな
？？
でも，再帰は非再帰よりも遅いかもしれないようだね‥意外だ
http://codepad.org/4B8PijgI 再帰
http://codepad.org/AGfYeUmV ループ
0462デフォルトの名無しさん
2015/08/23(日) 23:08:33.07ID:c9xDZ4H5だぁかぁらぁ再帰でループ使ってんじぇねえぞカスこら
for (;;) {
while (f(pi, pivot) < 0)
pi += size;
while (f(qi, pivot) >= 0)
qi -= size;
if (qi < pi)
break;
swap(pi, qi, t, size);
}
全部再帰で実装しろや卑怯者
0463デフォルトの名無しさん
2015/08/23(日) 23:18:14.86ID:cJWS/2haプログラミングの常識を欠き過ぎ。
ニ方向に再帰する構造をループに書くのは大変だな‥
平衡ニ分木なんかどうすればいいのだろう‥
0465デフォルトの名無しさん
2015/08/24(月) 00:02:19.68ID:lwCfvpYiFreeBSDもLinuxも.NETもJavaも二分探索木(赤黒木)はループで実装されとりますがな
0466デフォルトの名無しさん
2015/08/24(月) 00:21:55.88ID:rSFKQba3こういうバカ
0467デフォルトの名無しさん
2015/08/24(月) 09:13:29.48ID:pjiRa/zc0468デフォルトの名無しさん
2015/08/24(月) 09:13:40.03ID:X6qu577Dスタックに積むコストを舐めすぎている
0469デフォルトの名無しさん
2015/08/24(月) 10:54:15.45ID:r4N2Q7ijそのコードじゃ重くて当然だと思うが
1処理単位のmalloc呼び出しが再帰は3回、ループは1回
そこ同じ数に直せばほぼ変わらないと思う
0470デフォルトの名無しさん
2015/08/24(月) 13:27:36.75ID:nAv/Kj8Z途中の処理でメモリの確保・開放をしないことで、望ましい高速処理が実現される。
0471デフォルトの名無しさん
2015/08/24(月) 15:15:24.35ID:zrEdzFeoなるほど
ループ版（再掲載）http://codepad.org/xvNqmIcZ
若干再帰版の方が早いようだ，スタックポインタはレジスタ一個で管理できるから軽いんだね
0474デフォルトの名無しさん
2015/08/24(月) 21:55:55.71ID:nAv/Kj8Z1処理単位のmalloc呼び出しを無しにできることなんだから
あってはダメ
0475デフォルトの名無しさん
2015/08/25(火) 00:51:04.35ID:uonxIY7X再帰は問題をより小さい問題に分割することによってアルゴリズムを分かりやすくして
バグを混入しにくくすることが目的なんだから、速度はハナから求めてないしね
0476デフォルトの名無しさん
2015/08/25(火) 01:42:50.39ID:pfa9oRBxわかりやすくならないなら使う意味もないし、
単に速度が遅くなるってだけなわけさ。
0477デフォルトの名無しさん
2015/08/25(火) 01:53:24.89ID:bwlYR2I5リストに関して言えば、リンクリストは重いので配列を使う
配列を使うと自ずとループ処理が多くなるわな
0478デフォルトの名無しさん
2015/08/25(火) 03:17:22.19ID:36oEPfesデータ構造としての性質がぜんぜん違う
0479デフォルトの名無しさん
2015/08/25(火) 03:47:16.58ID:dXp7EQvt0480デフォルトの名無しさん
2015/08/25(火) 07:19:29.79ID:bwlYR2I5そのとおり
ほとんどの場合で配列の方が早い
だから配列を使う
0481デフォルトの名無しさん
2015/08/25(火) 09:33:09.51ID:36oEPfesなんでマトモにプログラム書いたこともないような奴ばっかりなんだ
0482デフォルトの名無しさん
2015/08/25(火) 09:47:35.65ID:zI10HmeAバカはおまえだけ
0483デフォルトの名無しさん
2015/08/25(火) 15:43:56.61ID:YISO+qUP0484デフォルトの名無しさん
2015/08/25(火) 19:31:30.11ID:eVT/tzv+いやそれはおかしい例えだろ
そこで師範代から正しい呼吸法を学ぶ流れだぞ
0485デフォルトの名無しさん
2015/08/25(火) 20:16:14.30ID:YISO+qUP0486デフォルトの名無しさん
2015/08/25(火) 20:34:31.94ID:bwlYR2I5リンクリスト使わずに配列使っとけば良いってこと
配列使っとけば、ループ処理に再帰を使おうって、
考えも浮かばなくなる
ほとんどの場合で良好なパフォーマンス
可読性もバッチリ
0487デフォルトの名無しさん
2015/08/25(火) 20:44:07.68ID:uonxIY7Xここは違うよね
ループを使うということは手続きを追わないといけない
再帰なら定義をそのまま書ける
どちらが可読性がいいかどうかは言わずもがな
0488デフォルトの名無しさん
2015/08/25(火) 20:52:22.67ID:zI10HmeA非実用的な再帰方式は採用できないのだから
実用的なループ方式を使うしかない。
ループ方式のコードは、より複雑になるとしても
読むことが困難なものではない。
プログラマに少し経験があれば、
再帰方式から安全で高速処理のできるループ方式に
自分で変更できるレベル。
0489デフォルトの名無しさん
2015/08/25(火) 20:55:10.03ID:bwlYR2I5配列のループに再帰を使うのwwwww
それって読みやすいわけ？
0490デフォルトの名無しさん
2015/08/25(火) 20:57:06.79ID:uonxIY7X> 再帰方式から安全で高速処理のできるループ方式に
> 自分で変更できるレベル。
変更できてもその結果バグを埋め込んだりしたら無意味
そうならないために可読性は重視されるんだから
0491デフォルトの名無しさん
2015/08/25(火) 21:02:19.58ID:bwlYR2I5俺はリンクリストなんぞ使わずに配列使えっていってるわけで
ランダムアクセスできて便利
0492デフォルトの名無しさん
2015/08/25(火) 21:05:07.20ID:bwlYR2I5range-based for が有るのに、
何でわざわざ再帰で書くwww
0493デフォルトの名無しさん
2015/08/25(火) 22:16:19.86ID:zI10HmeAプログラマに少し経験があれば、
分かりやすくループ方式に直せるはず。
バグを埋め込まないレベルで
埋め込まれたバグが同僚が発見しやすいレベルで
0494デフォルトの名無しさん
2015/08/25(火) 22:36:15.41ID:JZwUbwZbc/c++はくそいんだけど
どうせガチの実装するときだからあっても使わないどころか
ユニットで固めるから可読性とメンテナンス性はガン無視だわ
0495デフォルトの名無しさん
2015/08/26(水) 01:11:58.96ID:fE8RXalP0496デフォルトの名無しさん
2015/08/26(水) 01:31:34.12ID:5P6ATqZc同じ理論が成り立つから無意味だ
0497デフォルトの名無しさん
2015/08/26(水) 01:34:29.40ID:fE8RXalP0498デフォルトの名無しさん
2015/08/26(水) 01:52:36.91ID:eIiWuCWx0499デフォルトの名無しさん
2015/08/26(水) 03:45:39.29ID:tWuWD3CH>>473 でみたように，クイックソートのような再帰アルゴリズムをループ処理で記述すると malloc()/new の発生は回避できない
0500デフォルトの名無しさん
2015/08/26(水) 03:46:52.92ID:tWuWD3CH>>473 でみたように「ループ処理の方が早い」とは必ずしもいえない．
再帰で記述したほうが速度が出る場合も結構あるのでは？
0501デフォルトの名無しさん
2015/08/26(水) 03:49:21.29ID:tWuWD3CH最近急に「std::vector 一択だ！」論者が増えているようで‥
0502デフォルトの名無しさん
2015/08/26(水) 05:07:16.18ID:CDX3RzQSぼけ！
まだ書き直してねえじゃねえか。
さっさと１処理毎のメモリ確保解放をしない
ループ処理の通常版に直せ。
これを知らんのはお前が病的な世界にいるからだ。
0503デフォルトの名無しさん
2015/08/26(水) 07:31:12.39ID:pCUEXLgh呼び出しオーバーヘッド削り込む実装しなきゃ
ループのほうがはやくはならんよ
OSSでもまともなのはそーいう実装になってるよ
0504デフォルトの名無しさん
2015/08/26(水) 07:39:26.46ID:nL2sda9W> >>473 でみたように，クイックソートのような再帰アルゴリズムをループ処理で記述すると malloc()/new の発生は回避できない
回避できるでしょ？
最初っから必要になる最大メモリを確保すればいいんだよ。
最大がわからないなら、
そのサイズはスタックの最大メモリと同じ量でいい。
0505デフォルトの名無しさん
2015/08/26(水) 07:45:06.17ID:tWuWD3CHちゃんと，処理の頭と終わりで malloc()/free() するだけの構造にしたよ
ニ方向に再帰するクイックソートで，処理中にスタックに出し入れするから，
その分の malloc()/free() を使うのは不可避
>>503
まあそういうことだ‥
このスレのはじめのほうでは再帰のオーバーヘッドはかなり高いことになっていたが，
実はそうでもない
0506デフォルトの名無しさん
2015/08/26(水) 07:45:54.80ID:tWuWD3CH＞スタックの最大メモリ
ってなんだい？C で説明してくれ
0507デフォルトの名無しさん
2015/08/26(水) 08:06:15.93ID:CDX3RzQS＞ニ方向に再帰するクイックソートで，処理中にスタックに出し入れするから，
＞その分の malloc()/free() を使うのは不可避
その分の malloc()/free() を使うなボケ
処理毎のメモリ確保解放をしないのが業界標準だ
極端に低レベルなコードを作り出してソートを語るな
0508デフォルトの名無しさん
2015/08/26(水) 09:03:59.69ID:nL2sda9Wスタックオーバーフローしたときの
スタックで使用しているメモリ量のことだよ。
0509デフォルトの名無しさん
2015/08/26(水) 15:30:14.05ID:3EJSkE06https://ja.wikipedia.org/wiki/分割統治法
0510デフォルトの名無しさん
2015/08/26(水) 20:04:00.33ID:1FIsj9f5ループを使えば高速化できる
トレードオフなだけだよね
高速化が必要ならループ使えばいいし、そうでもないなら再帰で分かりやすく書けばいい
前提条件がないのにどっちがいいとか決められる話じゃない
0511デフォルトの名無しさん
2015/08/26(水) 20:57:30.21ID:tWuWD3CHその常識を覆す結果，すなわち
・再帰を使うほうが全般的に軽い，
・ループは分かりやすくない上におもったより重い
という結果が出ているんだよ
0512デフォルトの名無しさん
2015/08/26(水) 21:01:56.66ID:nL2sda9W訂正
再帰を使えば分かりやすく書けることもある。
ループを使ったほうがわかりやすいことも有る。
ループを使えば高速化できる。
0513デフォルトの名無しさん
2015/08/26(水) 21:27:00.60ID:CDX3RzQSそんなバカ言ってるのはお前だけ。
さっさと世間で使われているクイックソートのアルゴリズムがどうなっているのか学習しろ。
このスレでさんざん多くのレスで非難されているのに、現実を理解できないお前は重病。
0514デフォルトの名無しさん
2015/08/27(木) 00:24:39.98ID:D5iVdV3D分割で要素数減ったら別アルゴに切り替えるでしょ
だから関数呼び出しのオーバーヘッドの影響が小さくなるのよ
それもデータ多いと遅いから
ミッションクリティカルに大量のソート回す場合は
パラのradixマージじゃないのか
おれはこう思ってたんだけど俺の認識間違ってる？
0515デフォルトの名無しさん
2015/08/27(木) 02:53:00.07ID:rEYgAb/Rまともなループ版のクイックソート使えばいいのに
0516デフォルトの名無しさん
2015/08/27(木) 03:36:13.50ID:4wYo+P+Yクィックソートするのに，データ数の前提をたててその分のメモリを先に確保するのか？
それが世間でやっていることなのか？
Cのライブラリ関数 qsort() で行われていることなのか？
0517デフォルトの名無しさん
2015/08/27(木) 03:40:39.00ID:zsRIAfpU入れ替えしか行ってないのに、
なんで別にメモリを確保しなきゃいかんのだ？
0518片山博文MZ ◆T6xkBnTXz7B0
2015/08/27(木) 03:48:48.52ID:oqQcnINPint f(int x,int y) {
if (x > 0)return f(x-1,y)-1;
if (y > 0)return f(x+1,y-1)+3;
return 1;
}
さて、f(3,8)はいくつ？
0519片山博文MZ ◆T6xkBnTXz7B0
2015/08/27(木) 03:52:04.42ID:oqQcnINP0520デフォルトの名無しさん
2015/08/27(木) 10:07:26.43ID:1OqAD7+dソースコードとその処理結果の組み合わせを見るもの
実用的なプログラミングにはＣ＋＋とか他の言語を使う
0521デフォルトの名無しさん
2015/08/27(木) 23:36:19.60ID:3Gk4WjfjMISRA-C だの 2chコーディング規約だのと叫んでた人達はどこに行ったの？
>>516
gcc qsort.c
でググれば出てくるから見てみたらどうかな。
0522デフォルトの名無しさん
2015/08/27(木) 23:44:42.40ID:3Gk4Wjfjhttps://github.com/lattera/glibc/blob/master/stdlib/qsort.c
0523デフォルトの名無しさん
2015/08/28(金) 00:07:34.86ID:X6i2EJ+Kでググればいいらしい。
0524デフォルトの名無しさん
2015/08/28(金) 01:56:03.91ID:5JQ0ubd6再帰処理をループにしても読みにくくならないって言う人は、竹内関数を再帰呼び出し無しで書いてみること。
書けない人は議論に参加する資格無し。
0525デフォルトの名無しさん
2015/08/28(金) 02:00:35.89ID:k07is2fO実際にもっとも使われるデータ構造は配列です
配列のループに再帰を使うのはナンセンスです
0526デフォルトの名無しさん
2015/08/28(金) 05:01:09.44ID:Ox2JHydAまだ勘違いしてるの？
ループでも簡単なものを
わざわざ再帰で書くんじゃねーよって
話をしてるんだが。
0527デフォルトの名無しさん
2015/08/28(金) 06:01:37.78ID:uG+DCu7fman ばかりでてくるんだけど‥
0528デフォルトの名無しさん
2015/08/28(金) 10:15:07.18ID:McJH/vOCわざわざ実用性のない再帰で書く
再帰キティ害は、どこまで病的なんだか・・
0529デフォルトの名無しさん
2015/08/28(金) 21:21:58.14ID:5JQ0ubd6ループで簡単に書ける問題でも
再帰で「もっと」簡単に書けるなら再帰で書くよ
0530デフォルトの名無しさん
2015/08/28(金) 21:27:38.78ID:McJH/vOC脳みそ腐ってる
再帰のベンチマークでいつまでも遊んでろ
0531デフォルトの名無しさん
2015/08/28(金) 21:30:07.36ID:5JQ0ubd6GOTOで簡単に書ける問題でも関数使うのと同じだよ
0532デフォルトの名無しさん
2015/08/28(金) 21:33:32.50ID:k07is2fO配列のループに再帰を使うのはナンセンスです
0533デフォルトの名無しさん
2015/08/28(金) 21:35:35.21ID:5JQ0ubd6木の探索にループを使うのはナンセンスです
0534デフォルトの名無しさん
2015/08/28(金) 21:35:43.99ID:p8e2JvhL0535デフォルトの名無しさん
2015/08/28(金) 21:36:22.40ID:5JQ0ubd6木です
0536デフォルトの名無しさん
2015/08/28(金) 21:37:14.01ID:k07is2fO0537デフォルトの名無しさん
2015/08/28(金) 21:38:08.70ID:5JQ0ubd6それは単価の安いエンジニアだからです
0538デフォルトの名無しさん
2015/08/28(金) 21:38:50.59ID:p8e2JvhL問題によってデータ構造を選ぶのが適切
0539デフォルトの名無しさん
2015/08/28(金) 21:39:52.00ID:k07is2fO>木です
これの面白い点は、
通常パーサで再帰下降型など再帰が使われることは無いということです
0540デフォルトの名無しさん
2015/08/28(金) 21:42:13.29ID:5JQ0ubd60541デフォルトの名無しさん
2015/08/28(金) 21:43:36.30ID:k07is2fOもっともよく使われるデータ構造は、配列だと言っているだけです
もっともよく使われるデータ構造である配列のループに
再帰を使うのはナンセンスです
配列を良く使うことと、ループ分を良く使うことは、同義と言って良いでしょう
配列はよく使われるので、ループも良く使われます
0542デフォルトの名無しさん
2015/08/28(金) 21:46:23.84ID:5JQ0ubd60543デフォルトの名無しさん
2015/08/28(金) 21:48:29.35ID:3pAHpuiu0544デフォルトの名無しさん
2015/08/28(金) 21:58:33.93ID:k07is2fO文字列の表現には配列が適しています
つまり、配列はとても沢山使われるということです
配列の操作にはループ文が適しています
配列で表現された文字列に対して、
strlenなどの文字列操作を再帰で実装するのはナンセンスです
つまり、ループ文はとても沢山使われるということです
0545デフォルトの名無しさん
2015/08/28(金) 22:03:28.46ID:5JQ0ubd60546デフォルトの名無しさん
2015/08/28(金) 22:23:58.40ID:bBNOiFa3正しくはなに？
0547デフォルトの名無しさん
2015/08/28(金) 23:01:39.79ID:p8e2JvhLちなみにScalaとかでは配列を使うのはパフォーマンスを求めるときぐらい
ふつうに順序づけられた集合を表すのはList(という名のリンクリスト)だよ
0548デフォルトの名無しさん
2015/08/28(金) 23:10:55.11ID:bBNOiFa30549デフォルトの名無しさん
2015/08/28(金) 23:14:12.40ID:p8e2JvhLTwitterとか、日本でもドワンゴとかね
0550デフォルトの名無しさん
2015/08/28(金) 23:14:42.73ID:bBNOiFa30551デフォルトの名無しさん
2015/08/28(金) 23:15:03.90ID:cjHddNQ+業務でぇとか、しみったれたこと言うなよ。
0552デフォルトの名無しさん
2015/08/28(金) 23:15:34.96ID:bBNOiFa30553デフォルトの名無しさん
2015/08/28(金) 23:19:28.80ID:p8e2JvhLちょっと調べれば出てくる
0554デフォルトの名無しさん
2015/08/28(金) 23:25:39.66ID:cjHddNQ+ただしループは認める。やはりスタックが...
0555デフォルトの名無しさん
2015/08/28(金) 23:32:38.56ID:bBNOiFa3githubのランキングを見たが少なかったぞ。
そんなデータ信用できねーよと言うのなら、
それはそれでいいが、それなら君が信用できて
誰でも検証可能なデータを示すべきだ。
0556デフォルトの名無しさん
2015/08/28(金) 23:48:40.83ID:k07is2fOリンクリストはランダムアクセスが出来ないので不便
なので、配列の方が、より、汎用性のあるデータ構造といえます
使い勝手のいいデータ構造を採用する事は、可読性に繋がります
一般に配列は、挿入、削除、リサイズが遅いとされていますが、
単に、そういう風に対立構造にして、場合に応じて使い分ける風に言ったほうが、
かっこいいから、そう言っている、というだけです
例えば、クリエイティブならMac、という紹介文章みたいなもんです
リンクリストにも華を持たせてあげましょう、というだけです
配列の挿入、削除、リサイズは、そこまで遅いわけではありません
memcpy memmoveはカリカリにチューニングしてあり、とても速いです
CPUのキャッシュに乗りやすい処理であるのもポイントです
最近のPCのメモリ帯域を確認してください
対して、リンクリストのランダムアクセスは、とても重いです
CPUのキャッシュに乗りにくい処理です
0557デフォルトの名無しさん
2015/08/29(土) 00:15:20.73ID:hP/roqxQ0558デフォルトの名無しさん
2015/08/29(土) 00:41:01.81ID:bUE2FMpc処理中にメモリ確保・解放しまくるデータ構造は、とんでもなく重い。
0559デフォルトの名無しさん
2015/08/29(土) 00:44:15.53ID:haT66cVyメモリ確保・解放してるからなぁ。
0560デフォルトの名無しさん
2015/08/29(土) 00:52:02.37ID:abZzEG6qよかったら、「blngs」で検索してみて！
0561デフォルトの名無しさん
2015/08/29(土) 02:02:43.87ID:TLrhTEktせやろか？
俺の経験では処理の遅さはメモリ確保の回数よりも
メモリのサイズに比例する。
0562デフォルトの名無しさん
2015/08/29(土) 02:06:54.96ID:g5UyIGYz処理の重さはメモリ「開放」の回数に比例する
無論C/C++のfree/deleteの話だが
0563デフォルトの名無しさん
2015/08/29(土) 02:32:09.50ID:haT66cVy指定したメモリを毎回確保・解放してるわけじゃないからな。
ある一定サイズをどかんと確保して、
ちょこちょこ割り当てて使用している。
0564デフォルトの名無しさん
2015/08/29(土) 02:45:20.83ID:g5UyIGYzWindowsならVirtualAlloc これは速い
mallocなどドカンと確保して、ちょこちょこ割り当てる、これが全く重い
正確には割り当てるのは速い 解放がとてつもなく遅い
0565デフォルトの名無しさん
2015/08/29(土) 03:55:56.31ID:VNb5NXe3もちろん、そこまで考えなきゃいけない分野はあるし、そういう分野で再帰を使うのは間違ってると
思うけど、一般の人間はそこまで考えなくていいからね
0566デフォルトの名無しさん
2015/08/29(土) 06:20:13.75ID:sPvi53Zpプログラマとしてまともな仕事を扱うこともなく
任されることもない、
いい加減なコードを書くだけで信用も期待もされない。
これ一般じゃあない。
0567デフォルトの名無しさん
2015/08/29(土) 06:48:33.39ID:e0Hg3/HLポインタがあるだけだ
0568デフォルトの名無しさん
2015/08/29(土) 06:54:58.07ID:hP/roqxQ0569デフォルトの名無しさん
2015/08/29(土) 13:05:13.99ID:VNb5NXe3そこまで考えなきゃいけない分野があるのは事実だが、それをマニュアルでやる分野はレア
マニュアルでやってたら絶対バグるから、モダンな言語にはガベージコレクタなどの技術が
採用されてるんだしね
0570デフォルトの名無しさん
2015/08/29(土) 13:57:09.93ID:7eeJLuGb0571デフォルトの名無しさん
2015/08/29(土) 17:10:01.35ID:g7aWBHc90572デフォルトの名無しさん
2015/08/29(土) 18:43:39.65ID:g7aWBHc9アドレス演算≠ポインタ演算
0573デフォルトの名無しさん
2015/08/30(日) 14:09:15.19ID:PCX+Z6xEcalloc?…
0574デフォルトの名無しさん
2015/08/30(日) 14:09:53.80ID:PCX+Z6xEごめんなさい誤爆しました
0575デフォルトの名無しさん
2015/09/01(火) 01:14:01.81ID:t91IYFQ3いやいや
スクリプト言語だと配列という名前でもハッシュだったりするし
最近は配列を多用するのはc/c++(c++あんま知らんけど)くらいだと思うんだけど
javaでもなるべくコレクション使うようにするし
0576デフォルトの名無しさん
2015/09/01(火) 01:16:56.25ID:t91IYFQ3immutableに向いてないからキツイ
0577デフォルトの名無しさん
2015/09/01(火) 02:05:52.14ID:DJMTd98bでググったら、とっても残念なページを見つけてしまった。
素人ならまだしも、T 大学の N 先生、あなたがそんなことじゃだめでしょう。
クイックソートがスタックオーバーフローするのは recursive call のせいではありませんよ。
0578デフォルトの名無しさん
2015/09/01(火) 02:14:07.76ID:6K59ZHF3その人、たぶん、なんでデータの追加や削除の効率が悪いのかもわかってないのでは、と。
0579デフォルトの名無しさん
2015/09/01(火) 03:08:24.61ID:ucFEbRDOその人、たぶん、配列＝メモリに連続して固定長のデータが並んでいるもの
それ以外は認めない。という間違った考え方をしてる。
0580デフォルトの名無しさん
2015/09/01(火) 03:11:38.75ID:Uqk8gU8Precursive call のせいですよ
0581デフォルトの名無しさん
2015/09/01(火) 03:12:23.69ID:Uqk8gU8P間違ってないですよ
0582デフォルトの名無しさん
2015/09/01(火) 03:14:38.29ID:ucFEbRDOやっぱり固定長データが連続で並んでるものしか
認めないと思ってるのかｗ
明らかに間違ってるぞ。
C言語以外の言語の話をしようか？
0583デフォルトの名無しさん
2015/09/01(火) 03:29:20.63ID:6K59ZHF3アドレスマッピングの方法を使ってる言語なんかあるの？
0584デフォルトの名無しさん
2015/09/01(火) 03:29:25.49ID:Uqk8gU8PC言語以外じゃないと都合が悪いのか？
じゃあC言語でお願いします
0585デフォルトの名無しさん
2015/09/01(火) 03:30:24.33ID:ucFEbRDOあ、C言語限定じゃないと困るんだｗ
0586デフォルトの名無しさん
2015/09/01(火) 03:32:07.57ID:Uqk8gU8Pはい、基本C言語でお願いします
よろしくお願いいたします
配列=固定長データが連続で並んでる
これでいいですね
0587デフォルトの名無しさん
2015/09/01(火) 03:32:28.71ID:Uqk8gU8P0588デフォルトの名無しさん
2015/09/01(火) 03:32:41.75ID:6K59ZHF3そしてそれは（データ構造としての）配列ではない。
0589デフォルトの名無しさん
2015/09/01(火) 03:33:05.52ID:C9NG6GGp否
真にそう言えるのは1ビットのみである
0590デフォルトの名無しさん
2015/09/01(火) 03:40:53.92ID:ucFEbRDOC言語においては、配列は固定長データが連続で並んでる。
その他の言語ではそうとは限らない
だから"配列"だけで断定することは出来ない。
これでいいですよ。
0591デフォルトの名無しさん
2015/09/01(火) 03:44:11.25ID:Uqk8gU8PC言語はプログラム言語です
つまり、プログラムにおいて配列とは固定長データが連続で並んでるものなんです
0592デフォルトの名無しさん
2015/09/01(火) 04:07:30.08ID:ucFEbRDOプログラム言語 というカテゴリの中に
・C言語
・Perl
・PHP
・Ruby
・その他
などが含まれます。
その中で、C言語では配列とは固定長データが連続で並んでるものなんです
0593デフォルトの名無しさん
2015/09/01(火) 04:14:14.53ID:Uqk8gU8PC言語以外では困るのでC言語でお願いしますと言いました。
いいですか、私はC言語以外では困るんです。
あなたは私を困らせたいのですか？困らせたくないでしょう。
私に同情してください。
配列=固定長データが連続で並んでる
これでいいですね。
0594デフォルトの名無しさん
2015/09/01(火) 04:19:55.14ID:C9NG6GGpスクリプトだらけなんだが…
0595デフォルトの名無しさん
2015/09/01(火) 04:24:44.91ID:6K59ZHF30596デフォルトの名無しさん
2015/09/01(火) 04:33:56.34ID:ucFEbRDO配列だからって、実装まで決まらない証拠。
0597デフォルトの名無しさん
2015/09/01(火) 04:37:44.81ID:Uqk8gU8Pふうむ、たとえば二分探索木の実装に赤黒木やスプレーツリーがあるように
データ構造にも抽象的なものとより具体的なものがあるわけっしょ。
つまり、抽象データ構造としての配列とより具体的なデータ構造としての配列があり、
抽象データ構造としての配列に連想配列が含まれ、より具体的な連想配列のデータ構造として
ハッシュテーブルがあるってことでしょね。
0598デフォルトの名無しさん
2015/09/01(火) 04:57:20.77ID:6K59ZHF3そういう緩い意味で「配列 array」は使わないことがわかるよ。
0599デフォルトの名無しさん
2015/09/01(火) 04:58:46.51ID:6K59ZHF30600デフォルトの名無しさん
2015/09/01(火) 05:04:47.15ID:6K59ZHF3array data typeはその実装がリストでもいい。
だから、効率性を云々する時のarrayはarray data typeではなくて
array data structureの話じゃなきゃいけない。そしてarray data structureは
インデックスからアドレスへの容易な算術演算によって（典型例が
データの連続配置）、O(1)アクセスを可能にするデータ構造。
0601デフォルトの名無しさん
2015/09/01(火) 06:38:20.62ID:lctJDoUSarray data structureがO(1)でなければならないというのなら
それを定義したのはどれかを言ってくれればいい。
おそらく無いからそれをごまかすために説明してるんだろうと思ってるけどねｗ
0602デフォルトの名無しさん
2015/09/01(火) 07:30:15.06ID:CkpgYLyfうわあ、これはマジモンでヤバい人だ…
0603デフォルトの名無しさん
2015/09/01(火) 08:00:49.42ID:/DoXUIG10604デフォルトの名無しさん
2015/09/01(火) 08:05:00.21ID:/DoXUIG1OS自体にその手の機能が存在してるべきなんだよ
速度をそこまでガチで求めない場合の簡易版で良い
0605デフォルトの名無しさん
2015/09/01(火) 08:11:25.32ID:KtW8DmAo逆に再帰関数はforやwhileに書き換えできる？ 出来るならそっちにしたいレベル
0606デフォルトの名無しさん
2015/09/01(火) 08:25:26.84ID:vcgHCiFQあれってなんか解決策あるんですかね……
怠惰なインスタンス化のように無限再帰を回避する方法ならあるけど
0607デフォルトの名無しさん
2015/09/01(火) 12:55:10.42ID:4i2DmfPVまず無い。
再帰でベンチマーク作るのでなければ。
0608デフォルトの名無しさん
2015/09/01(火) 13:38:18.55ID:DJMTd98b君に理解できる話じゃないよ。
クイックソートのスタックオーバーフローを防ぐためと称して
非再帰化しろだのスタックサイズを増やせだのと、
君程度の人なら言うかもしれないが、大学の先生がそんなことじゃ困る。
空間計算量の最適化を教えなさいよという話だ。
それ無しに非再帰化だのスタックサイズだのと言われる学生さんが可哀想だ。
0609デフォルトの名無しさん
2015/09/01(火) 13:48:33.08ID:4i2DmfPV君ごときの無能にそんなことじゃ困るなんて言われる
先生がかわいそうだ。
0610デフォルトの名無しさん
2015/09/01(火) 15:23:42.04ID:6K59ZHF3data typeじゃなくて data structureとしてのarrayなら下にあるけど？
常識なんで、定数アクセスじゃないadsがあるというならむしろそっちが実例挙げてね
https://en.wikipedia.org/wiki/Array_data_structure
0611デフォルトの名無しさん
2015/09/01(火) 19:15:05.37ID:jZfLWulg大学の先生の技術レベルがやばいのは経験してるでしょ
いまさら騒ぐ事でもねーよ
0612デフォルトの名無しさん
2015/09/02(水) 00:47:36.69ID:kkVdXJxG0613デフォルトの名無しさん
2015/09/02(水) 17:48:58.50ID:pfz+JPDHそうじゃないけど並んでるように見えるのは
あんまり配列とは呼びたくないでござる。
0614デフォルトの名無しさん
2015/09/02(水) 19:19:55.89ID:DAe+xWqL0615デフォルトの名無しさん
2015/09/03(木) 02:22:06.78ID:APM+2rA2Rubyの配列はRuby用語
0616デフォルトの名無しさん
2015/09/03(木) 11:36:04.16ID:hDY8eKzgみんな配列が大好きだね
人気者の配列のループには繰り返し文を使うから
繰り返し文は不滅だね
0617デフォルトの名無しさん
2015/09/03(木) 11:44:10.96ID:HOkCudGKわかる。配列とコレクションは別だよな。
0618デフォルトの名無しさん
2015/09/03(木) 12:12:06.19ID:dGS6eFW00619デフォルトの名無しさん
2015/09/03(木) 12:26:06.74ID:hDY8eKzg具体的にどんな感じで？
0620デフォルトの名無しさん
2015/09/03(木) 14:27:45.88ID:9nQXwra1head, tail, append さえあれば普通のリストとほぼ変わらん
0621デフォルトの名無しさん
2015/09/03(木) 15:43:06.69ID:dGS6eFW0hoge(input, output){
if (size(input) == 0) {
return;
}
return hoge(tail(input), output.append(dosomething(tail(input))));
}
こんなかんじ
0622デフォルトの名無しさん
2015/09/03(木) 18:02:46.75ID:IwEVB15/ちゃんとループで書く技術を身につけるべき。
0623デフォルトの名無しさん
2015/09/03(木) 18:37:19.10ID:dGS6eFW0最近はどの言語も範囲forがあるから、まだいいんだが
0624デフォルトの名無しさん
2015/09/03(木) 19:27:47.89ID:FSKtVBgWあんまりないな。いつも書き方一緒だし。
それ以外の書き方をしていれば「？」となる。
0625デフォルトの名無しさん
2015/09/03(木) 19:39:17.92ID:6KaE3e8w0626デフォルトの名無しさん
2015/09/03(木) 19:55:45.70ID:Fz3Ka6Ixしょーもないミスをしないためにも再帰は覚えておくべきだね
使いドコロはケース・バイ・ケースだけど
何が何でも再帰を避けるようなことさえしなければいいんじゃない？
0627デフォルトの名無しさん
2015/09/03(木) 20:37:42.86ID:FSKtVBgWforは範囲forで対応できるけど、
再帰は、範囲再帰ってあるの？ｗ
再帰のほうがしょーもないミス多いよね。
終了条件ミスってスタックオーバーフローｗ
0628デフォルトの名無しさん
2015/09/03(木) 21:22:18.75ID:qp+WFxZLなんでもできてしまうforよりかは
畳み込み、map,foreach, filterなんかで使いわけたほうがいい
0629デフォルトの名無しさん
2015/09/03(木) 21:23:50.62ID:qp+WFxZL0630デフォルトの名無しさん
2015/09/03(木) 22:32:32.63ID:FSKtVBgW> 範囲forに対応するものは高階関数になるんでね？
そんなわけない。
範囲だろうが範囲じゃなかろうがforはfor。
0631デフォルトの名無しさん
2015/09/03(木) 22:52:40.78ID:qp+WFxZLある程度抽象的だから
whileと同じような単純な構文であるforと同じだって言われると微妙な気持ちになる
オブジェクト指向ありきみたいな
0632デフォルトの名無しさん
2015/09/03(木) 22:55:55.75ID:K5TdrWRE便利だけど単なるシンタックスシュガー
なにより副作用のために使うものだから
関数型的ではない。
0633デフォルトの名無しさん
2015/09/03(木) 23:50:51.54ID:LEFvEBeedynamic programmingでやることにしても、最初の明快だけど遅い関数を書くときは再帰が多い。
そっからチューンしていったものが正しいかを検証したいとかよくある。
ので、再帰もループもどっちもある程度便利に使える言語は便利よ。
0634デフォルトの名無しさん
2015/09/04(金) 07:55:30.31ID:iLm0cn850点。
0635デフォルトの名無しさん
2015/09/04(金) 09:21:42.12ID:QpES+Y0P例えば以下の関数定義、手続き的に素直に書こうとするともっと長くなるはずだが、こう書かれても理解できない人もいるかもしれない。
f(n) =
| 0 (n = 0 のとき)
| n + f(n - 1) (n > 0 のとき)
| -f( |n| ) (n < 0 のとき)
なお、n は整数。
俺は宣言的な書き方が好き。
0636デフォルトの名無しさん
2015/09/04(金) 10:16:03.02ID:qqcvyIbf0637デフォルトの名無しさん
2015/09/04(金) 13:15:00.48ID:YC3FOSdxプログラミングでもっとも良く使うデータ構造は配列ですし、
配列のループ処理を再帰とみなす必要は無いですし、
繰り返し文であふれるのは自然だね
0638デフォルトの名無しさん
2015/09/04(金) 17:32:01.47ID:45GRgS6i理由書いてないので無視するｗ
0639デフォルトの名無しさん
2015/09/04(金) 18:34:45.30ID:FR19Rjgq0640デフォルトの名無しさん
2015/09/04(金) 20:04:17.17ID:RgFRqfXr数学的に突き詰めれば自然数だって帰納的に定義されるものなんだから、
ループは必ず再帰に置き換えられるね(もちろん逆もまた真)
したがって意味がないことはない
あとはどっちが読みやすいかだけの話
モダン言語の流れは手続き的なループをなくして、再帰や高階関数を使う
方向のようだけどね
0641デフォルトの名無しさん
2015/09/04(金) 20:31:46.45ID:K7Q0EkNO手順をスタックしてるかどうかでしょ
まぁループと再帰を別に考えてる(と言うか感じてる)時点で三流くささがするのだけど
0642デフォルトの名無しさん
2015/09/04(金) 20:32:19.95ID:FR19Rjgq0643デフォルトの名無しさん
2015/09/04(金) 20:55:16.54ID:RgFRqfXr最近はマシンスペックが上がってるからね
性能より抽象的な書き方ができるのを求めるようになってるんだよ
性能カリカリに求めたい場合だけCとか使っておけばいい世界
0644デフォルトの名無しさん
2015/09/04(金) 21:38:09.28ID:vuZU5Hwi> 再帰とループの違いはなに？
ループ・・・小学校で習う（1から10までの数字を足し算しょう等）
再帰・・・高校で習う。（1からnまでの自然数の和を計算式で表す）
0645デフォルトの名無しさん
2015/09/04(金) 21:49:10.66ID:q06Od88zまったく理解できてない……
0646デフォルトの名無しさん
2015/09/04(金) 21:49:46.26ID:vuZU5Hwi「間違ってる」とは言わないんだなｗ
0647デフォルトの名無しさん
2015/09/04(金) 21:54:59.88ID:K7Q0EkNO0648デフォルトの名無しさん
2015/09/04(金) 21:59:29.06ID:vuZU5Hwiつまりループと再帰ではループのほうがわかりやすいんだよね。
単純なループじゃない場合は、再帰のほうがいい場合もある。
だけどループでいいのならば、ループのほうがわかりやすい。
それは小学生でもループを理解していることからわかる。
（小学生にループというのは、nにn-1を足すのを0になるまで繰り返すとか言ってもわからない）
0649デフォルトの名無しさん
2015/09/04(金) 22:17:32.25ID:6Rt4goII単に言語開発のネタ切れしてるだけじゃねぇの
開発サイドの人間が必死こいて宣伝してるんだったら気持ちもわかるが
ユーザーだったらもっとマシな言語あるでしょとしか言えない
0650デフォルトの名無しさん
2015/09/04(金) 22:24:44.42ID:q06Od88z根底から間違ってる、って言えばよかったの？
まず、(((((((((1+2)+3)+4)...+10) は典型的な再帰構造。ループでもなんでもない。
そして和の公式 n*(n+1)/2 は再帰でも何でもない閉じた式表現
（というか、再帰を使わない式にすることこそがその眼目だ）。
0651デフォルトの名無しさん
2015/09/04(金) 23:01:37.97ID:vuZU5Hwi小学生に言って、そんな式書く奴いないなｗ
普通は
1 + 1 = 2
2 + 2 = 4
4 + 3 = 7
7 + 4 = 11
って計算するんだぜ。
これを10まで繰り返す。
まさにループ
0652デフォルトの名無しさん
2015/09/04(金) 23:20:57.61ID:q06Od88zそれ全然ループじゃないから。
0653デフォルトの名無しさん
2015/09/04(金) 23:24:17.87ID:q06Od88z再帰以外のなにものでもないんだけど、基礎論触ったことないとわかんないかもね。
0654デフォルトの名無しさん
2015/09/04(金) 23:26:41.39ID:yf6WF608わかったところでカスだけどな。
再帰っていうのは木偶の坊の代名詞。
0655デフォルトの名無しさん
2015/09/04(金) 23:28:22.98ID:kQbi8Wuv0656デフォルトの名無しさん
2015/09/04(金) 23:29:28.63ID:vuZU5Hwiループじゃんｗ
書けば理解できるのか？
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
これをステップ実行したのが>>651
0657デフォルトの名無しさん
2015/09/04(金) 23:30:53.74ID:K7Q0EkNO0658デフォルトの名無しさん
2015/09/04(金) 23:33:40.85ID:vuZU5Hwi9月にそれを言うってことは
お前大卒（もしくは在籍）じゃないのか？
0659デフォルトの名無しさん
2015/09/04(金) 23:43:51.99ID:RgFRqfXr分かったなら再帰が役に立つことぐらい簡単に理解できそうなもんだけどなー
理解できないならわかってないんだよ
0660デフォルトの名無しさん
2015/09/05(土) 00:20:19.44ID:LWQiKMu8ループの方が100億万倍やくに立つ。
再帰は数学に憧れてるだけで数学できない出来損ない野郎が使う。
0661デフォルトの名無しさん
2015/09/05(土) 00:45:04.95ID:j+vMQGdO0662デフォルトの名無しさん
2015/09/05(土) 00:56:03.07ID:dKM7sd/0b. ループは不要
c. どっちも欲しい
d. 言語に合わせる
aとb(いるのか？)に精神病患者がいるせいで、
cの人の投げた話題を勝手にa(あるいはb)の人間の主張と見なして攻撃するのがおかしい。
aに反駁したらループ不要派だとレッテルを貼られ、
bに反論したら再帰理解できない馬鹿とレッテルを貼られるが、そもそもnot a != bだしnot b != aだからな。
再帰関数を作る時は、頭に保持しなきゃならない情報が少ないのがいいよ。
f(n)の定義を使ってf(n)を定義できるイメージ。場合分けだけで済む。
古典的なインデックスを使うforループより、要素を1つずつ取り出すっていうのが明確なforeachが好まれるのも似た理屈だと思う。
0663デフォルトの名無しさん
2015/09/05(土) 01:09:05.88ID:dKM7sd/0例えばリストの要素を2つ以上必要とする処理を書くとき、OCamlだと
let rec foo acc xs = match xs with
| x :: y :: rest -> foo (do_something x y acc) y::rest)
| _ :: [] | [] -> finish_something
みたいに書けて楽。ループだとインデックスの範囲とか終了条件とか色々考慮しなきゃならんので手間がかかる。
0664デフォルトの名無しさん
2015/09/05(土) 01:13:53.21ID:LWQiKMu8パターンマッチは邪道
ナローイングなキャストを誤魔化してるだけ
0665デフォルトの名無しさん
2015/09/05(土) 01:22:40.76ID:9u1zKCQdこれを邪道とか言ってるのはCとかにどっぷり漬かった人間のただの負け惜しみ
0666デフォルトの名無しさん
2015/09/05(土) 04:48:42.79ID:Bq/cKCjDただし再帰のを話題にするなら、一回その楽な書き方で書いてから、正しい書き方に直すような前提の話になる
CPUやメモリを隠してる状態でこの話は有り得ない
再帰かどうかと言うのは、CPUとメモリの使いかた (の人間的な概念) を指すものだから。
この手の話題を出す限りは、Pythonが仕様書兼動作テストで、それを手動最適化して直したのが Cの実装 なんてのも十分有り得る
ま、さらに深くまで考慮するとまったく区別のしようがない同じ物なんだけどね。
ちょっと前に Rubyでしか使えないRuby用語の配列を、まるで本物の配列のように思い込んでた人がいたね。
再帰も再帰でそれと同じ。もちろんループも。
特定の言語内部だけの話ならそちらのスレにどうぞ。
0667デフォルトの名無しさん
2015/09/05(土) 06:52:05.04ID:BDvTAHGXCTMCP(ガウディ本)読んで、計算モデル理解した方が良いよ。
0668デフォルトの名無しさん
2015/09/05(土) 06:56:36.26ID:ReU+9sFg理解したよ。それでいいたことは何かな？
0669デフォルトの名無しさん
2015/09/05(土) 06:59:39.65ID:Bq/cKCjDまぁ俺も同じことを聞こうか
>>667
それで言いたいことはなにかな？
0670NAS6 ◆n3AmnVhjwc
2015/09/05(土) 07:33:00.36ID:zGjt7Ia9おま、戻り値を使いまわしたら基本的に再帰じゃないの？。。。
0671デフォルトの名無しさん
2015/09/05(土) 07:42:48.23ID:Bq/cKCjD馬鹿しかいねぇ
0672デフォルトの名無しさん
2015/09/05(土) 07:45:22.49ID:Bq/cKCjD0673NAS6 ◆n3AmnVhjwc
2015/09/05(土) 08:00:20.87ID:zGjt7Ia9int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
戻り値の使いまわしは基本的に再帰
0674デフォルトの名無しさん
2015/09/05(土) 08:50:03.58ID:Bq/cKCjDでもあえてそこで決めるのならば(その話に乗るのならば)、手順 (もしくはそれに相当するもの) を覚えている物が再帰。
sum = sum + i;
これは現在の状態しか保持しない。
構造を検索するもの、…例えばディレクトリとファイル検索で
whileだけを使ったとしても、
出てきたそれぞれのファイル対し、そのアドレスを記録したら、
それは処理における必要資源量の理論最低値は再帰と等価
0675NAS6 ◆n3AmnVhjwc
2015/09/05(土) 08:53:27.64ID:zGjt7Ia90676NAS6 ◆n3AmnVhjwc
2015/09/05(土) 08:59:50.82ID:zGjt7Ia9とかの全検索は、どうやっても再帰
もちろんＡ＊も再帰
0677デフォルトの名無しさん
2015/09/05(土) 09:02:33.33ID:Bq/cKCjD0678NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:03:26.20ID:zGjt7Ia90679NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:05:10.34ID:zGjt7Ia9これがスコープのスタック保存だろ
0680デフォルトの名無しさん
2015/09/05(土) 09:06:13.64ID:Bq/cKCjDfor(int i = 1; i <= 10; i++) {
sum = sum + i;
}
これを再帰って言ったでしょうに。
これはスタックの保存じゃなくて上書きっつーの
0681NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:13:54.31ID:SH0QgRhIsum+iのsumはスタック保存
0682NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:20:33.46ID:SH0QgRhI0683デフォルトの名無しさん
2015/09/05(土) 09:21:52.97ID:Bq/cKCjDa = 0;
a = a + 1;
a = a + 2;
以上の三行は再帰とは呼ばない
再帰と言うのは最終段階の55の瞬間に今までの経緯を覚えてて
そこで初めて再帰と必要資源量の (理論最低値の) 釣り合いが取れます。
例えば配列に 1, 2, 4, 7, 11,… と記録したらそこで初めてある側面で再帰と同じ資源量
0684デフォルトの名無しさん
2015/09/05(土) 09:25:47.84ID:Bq/cKCjD必要がないもくそもない
0685NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:26:38.87ID:zGjt7Ia9sum+iのsumはスタック保存値
sum=のsumがスタック保存（＋上書き）
こういうのはループでも全然いいけど
スコープスタックを保存する必要があるなら、完全に再帰しかない
0686デフォルトの名無しさん
2015/09/05(土) 09:29:04.79ID:Bq/cKCjD0687NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:40:47.32ID:zGjt7Ia9必要がないもくそもない
だから、スコープスタックを保存する必要がある時に、再帰を使う必要があるんですってば
0688NAS6 ◆n3AmnVhjwc
2015/09/05(土) 09:57:57.73ID:zGjt7Ia9は
>>673
な感じなんだろ
ループは、スコープスタックを保存しなくていい時
再帰は、スコープスタックを保存しなければいけない時
再帰の文字通り、手順の戻り道を、覚えている必要があるかどうかだよ
0689デフォルトの名無しさん
2015/09/05(土) 10:00:34.66ID:ReU+9sFgスタックというものは、
値のプッシュ（スタックに積む）と
値のポップ（スタックから取り出す）を
行うためのデータ構造です。
これをしていないものは、当然
スタックではありません。
0690NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:01:42.56ID:zGjt7Ia90691デフォルトの名無しさん
2015/09/05(土) 10:01:59.54ID:ReU+9sFgスタックはコンピュータで用いられる基本的なデータ構造の1つで、
データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で
保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
0692デフォルトの名無しさん
2015/09/05(土) 10:02:49.88ID:ReU+9sFg> バカは知りませんが関数呼び出しはコールスタックです
どこの話をしてるんですか？
0693デフォルトの名無しさん
2015/09/05(土) 10:03:52.96ID:ReU+9sFg自分自身の関数を呼び出すもののことです。
これをやっていないものは
当然再帰ではありません
0694NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:12:58.37ID:zGjt7Ia9int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
これは全部、スタックに保存されてるよ
だから、
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
これに比べて、スタック保存分、オーバーロードしているけどね
ユニットの移動範囲とか、画像のフィリングとか、
ある点の周囲探索は、スタック保存の再帰関数にするのが一番いいだろ
0695NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:16:27.86ID:zGjt7Ia9ループだけしか使わないバカがいるのか？
0696デフォルトの名無しさん
2015/09/05(土) 10:19:30.35ID:Bq/cKCjD会話するの難しいだろ
0697デフォルトの名無しさん
2015/09/05(土) 10:21:37.41ID:ReU+9sFgお前は知らないだろうけどね。
関数ないのローカル変数っていうのは
全部スタックに保存されるんだよ。
スタックにデータを保存すれば
再帰という理屈であれば、
ローカル変数がある関数はすべて
再帰ってことになってしまう。
もちろんそんなことはありえない。
0698NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:21:49.47ID:zGjt7Ia9ループだけしか使わないで作れるなら作ってみろよ
ニヤニヤしながら見ててやるから
0699NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:26:03.39ID:zGjt7Ia9え？コールスタックが再帰じゃないの？
それじゃ、関数を呼び出した後、元の位置に戻れないぞ
0700デフォルトの名無しさん
2015/09/05(土) 10:26:17.15ID:ReU+9sFg閉空間の塗りつぶしだね？
検索したあったよ。
もちろん再帰は使っていない
> この改良版アルゴリズムはスキャンライン・シード・フィル アルゴリズム(Scanline Seed Fill Algorithm)と呼ばれています。
http://fussy.web.fc2.com/algo/algo3-1.htm
0701デフォルトの名無しさん
2015/09/05(土) 10:27:24.93ID:ReU+9sFg> え？コールスタックが再帰じゃないの？
ぷぷぷ。こいつマジでわかってなかったんだｗ
お前理屈だと、すべての関数呼び出しが再帰ってことになってしまう。
再帰は、関数が自分自身の関数を呼び出している場合のみ。
お前が言ってるのは、単なる関数呼び出しだ。
0702NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:34:15.27ID:zGjt7Ia9呼び出し元に復元（リターン）できなければ、
プログラムじゃねえよ
0703デフォルトの名無しさん
2015/09/05(土) 10:36:14.02ID:ReU+9sFg自分が言っていたことが間違っていたことがわかったから
恥ずかしくなったんでしょうねｗ
0704NAS6 ◆n3AmnVhjwc
2015/09/05(土) 10:46:29.34ID:SH0QgRhI関数が元に戻れてスタック内容も変わらない
コールスタックを実装したら、当然再帰関数呼び出しも実装したことになる
0705デフォルトの名無しさん
2015/09/05(土) 10:47:55.97ID:ReU+9sFgすべての関数は再帰である。
>>704はそう言っているのです。
生暖かい目で見てあげましょう。
お兄ちゃん！関数使えるようになった！
私、再帰使いこなしてる！
0706NAS6 ◆n3AmnVhjwc
2015/09/05(土) 11:00:37.95ID:zGjt7Ia9の
ttp://nas6.main.jp/NAS6_tree_clct.h
//再帰構文例1
//再帰構文例2
は俺は両方再帰だと思って作ったけどな
>>700
みたいのは
//再帰構文例1
の構造だろ
0707NAS6 ◆n3AmnVhjwc
2015/09/05(土) 11:05:54.33ID:zGjt7Ia9頭が固いんじゃないの？
0708NAS6 ◆n3AmnVhjwc
2015/09/05(土) 11:10:08.71ID:zGjt7Ia9関数の自分自身を呼ばないと再帰処理じゃないっていうのは
頭が固いんじゃないの？
//再帰構文例1
は関数の自分自身を呼んでないけど、どう見ても再帰処理
0709デフォルトの名無しさん
2015/09/05(土) 11:23:13.73ID:Bq/cKCjD今ひとつピンと来たものがある。
よくよく思い出すと「再帰処理」と「再帰関数」と言う似てるけど別の概念がある。
それを失念していた。
なおスレタイは再帰関数である。
0710NAS6 ◆n3AmnVhjwc
2015/09/05(土) 11:27:58.33ID:SH0QgRhIコールスタックは再帰処理だよ
0711デフォルトの名無しさん
2015/09/05(土) 11:34:56.98ID:Bq/cKCjD100のうち俺の失念であろう1だ
会話が成り立ってなさすぎるからどうでもいいんだが
>コールスタックを実装したら、当然再帰関数呼び出しも実装したことになる
0712デフォルトの名無しさん
2015/09/05(土) 11:38:41.59ID:IJjvRwCO//再帰構文例2
> は俺は両方再帰だと思って作ったけどな
お前が間違ってるんだからお前が書いたコードきて
これが再帰なんだとか主張しても意味が無い。
0713デフォルトの名無しさん
2015/09/05(土) 11:42:04.89ID:IJjvRwCO再帰（さいき）とは、あるものについて記述する際に、記述しているもの
それ自身への参照が、その記述中にあらわれることをいう。
定義において、再帰があらわれているものを再帰的定義という。
なるほどね。自分自身への参照が必須なんだ。
0714NAS6 ◆n3AmnVhjwc
2015/09/05(土) 11:55:26.05ID:zGjt7Ia9だからクラスの関数呼び出しなんて、ほとんど
this->が省略されているだけなんだが・・・
0715デフォルトの名無しさん
2015/09/05(土) 11:57:10.38ID:IJjvRwCO関係ないよ。
0716デフォルトの名無しさん
2015/09/05(土) 12:03:39.85ID:9u1zKCQd頭が固いもなにも、それが再帰関数の定義なんだが…
0717NAS6 ◆n3AmnVhjwc
2015/09/05(土) 12:09:24.27ID:zGjt7Ia9基本的にスタックでしか動かないし
ttp://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node65.html
再帰呼び出し、スタック
0718NAS6 ◆n3AmnVhjwc
2015/09/05(土) 12:13:43.89ID:zGjt7Ia9def xn2(N) {
XN = 0;
for (I=0; I<N; I++) {
XN = 2*XN+1;
}
return(XN);
}
0719NAS6 ◆n3AmnVhjwc
2015/09/05(土) 12:25:42.76ID:zGjt7Ia9for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
な、これは再帰だろ、頭が悪いんだから、教授に迷惑をかけるなよ
0720NAS6 ◆n3AmnVhjwc
2015/09/05(土) 12:44:51.30ID:zGjt7Ia90721NAS6 ◆n3AmnVhjwc
2015/09/05(土) 12:56:18.37ID:zGjt7Ia9のも
新たなシードを決める際には、バッファ中のどのピクセルを選んでもよいのですが、
新しい順か、古い順かのどちらかに統一するのが普通でしょう。
バッファをスタック構造にすれば新しい順、キューにすれば古い順に自然に決まります。
これを読んでいないのか再帰じゃないと思ってるんだろ
0722デフォルトの名無しさん
2015/09/05(土) 13:11:58.86ID:IJjvRwCO違う
0723NAS6 ◆n3AmnVhjwc
2015/09/05(土) 13:14:58.05ID:zGjt7Ia9だから、戻り値を使って再帰呼び出ししているのと同じ事だろ
0724デフォルトの名無しさん
2015/09/05(土) 13:16:02.36ID:a9CPEVg5戻り値を使い回すのはDP(動的計画法)という立派な名前が付いてるんだが
0725デフォルトの名無しさん
2015/09/05(土) 13:16:18.51ID:IJjvRwCOすぐに見つかった。
>>719をアセンブリレベルにすると
見ての通りスタックも関数呼び出しもない。
単なるループ
http://mm.ahs.kitasato-u.ac.jp/~lm00000/sim/ueyama_ip/software/add10asm.html
次の例は １ から １０ まで （実は １０ から １ まで） の整数を加算するプログラムです。
ラベル 命令コード オペランド コメント文
LD B, 10 ; レジスタ B に 10 を代入する
LD A, 0 ; レジスタ A に 0 を代入する
LOOP: ADD A, B ; A に B を加える。加算結果はレジスタ A に。
DEC B ; B の値から 1 を引く
JR NZ, LOOP ; 引いた結果が 0 でなければ LOOP に分岐する
STOP: JR STOP ;プログラム終了。 加算結果はレジスタ A に残る。
0726デフォルトの名無しさん
2015/09/05(土) 13:16:42.20ID:IJjvRwCOぜんぜん違う
0727NAS6 ◆n3AmnVhjwc
2015/09/05(土) 13:22:00.75ID:zGjt7Ia9>>717
のリンクで
正式には再帰で書くけど、
最適化してループで書くってようなことが書いてあるだろ
0728NAS6 ◆n3AmnVhjwc
2015/09/05(土) 13:26:52.77ID:zGjt7Ia9のリンクでも
>>694
でも
＞これに比べて、スタック保存分、オーバーロードしているけどね
こういうわけで再帰をループに最適化するわけ
0729デフォルトの名無しさん
2015/09/05(土) 13:34:34.79ID:a9CPEVg5ねえ、そろそろ無知を晒すのやめない？恥ずかしくないか？
0730NAS6 ◆n3AmnVhjwc
2015/09/05(土) 13:41:26.99ID:zGjt7Ia9//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
で、最適化されたのしか、教わらないし、理解できないのかな？
0731NAS6 ◆n3AmnVhjwc
2015/09/05(土) 13:48:39.57ID:zGjt7Ia9//等差数列
//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (; 1 < n; n--, t += s) r = r + t;
return r;
}
0732NAS6 ◆n3AmnVhjwc
2015/09/05(土) 14:03:25.65ID:SH0QgRhIsigmaは「漸化式」の定義に基づいた再帰法
0733NAS6 ◆n3AmnVhjwc
2015/09/05(土) 14:09:21.37ID:zGjt7Ia9参照する必要があるのならば
動的計画法を用いることはできない
0734デフォルトの名無しさん
2015/09/05(土) 14:18:04.33ID:bMqKfWg+http://codepad.org/pUWGRddj
どこを見れば等差数列だと分かるようになるのでしょうか？
0735デフォルトの名無しさん
2015/09/05(土) 14:20:40.72ID:IJjvRwCO> 正式には「再帰で書くけど 最適化して（再帰ではなく）ループで書く」
ですね！？
最適化してループで書いたのだから
それは再帰ではないということです。
0736NAS6 ◆n3AmnVhjwc
2015/09/05(土) 14:42:48.35ID:zGjt7Ia9ああ、ごめんね
sigmaだから1〜nまでの等差数列の和だよ
漸化式の全ての項を使う
→全てのノードを使う時は動的計画法で最適化できないんよ
そのケースは、ある点からの周囲の経路を探索する場合
ディレクトリ探索だったり、塗りつぶしだったり、つまり全検索をかける場合
こういうのは再帰を使うだろうに
0737NAS6 ◆n3AmnVhjwc
2015/09/05(土) 14:44:53.85ID:zGjt7Ia9こういうのは再帰を使うだろうに
0738デフォルトの名無しさん
2015/09/05(土) 14:56:44.42ID:IJjvRwCO誰も再帰を絶対に使わないで書けとか言ってなくて、
ループで簡単にかけるようなものを
わざわざ再帰で書くなよ（笑）って
話なんだけど。
0739NAS6 ◆n3AmnVhjwc
2015/09/05(土) 14:57:36.94ID:zGjt7Ia9sigmaだから1〜n-1までの等差s数列の和
s=3なら
sigma=3+6+9+12+・・・
0740NAS6 ◆n3AmnVhjwc
2015/09/05(土) 15:08:23.80ID:zGjt7Ia9//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (; 1 < n; n--, t += s) r = r + t;
return r;
}
べつにどっちで書けって言われても
項をスタックするかしないだけの違いだけど？
0741デフォルトの名無しさん
2015/09/05(土) 15:10:18.45ID:IJjvRwCOそれよりも重要な違いは、
自分の関数自身を呼ぶかどうかだよ。
自分自身を呼ぶのが再帰、
そうでないのは再帰じゃない。
0742デフォルトの名無しさん
2015/09/05(土) 15:16:46.56ID:dKM7sd/0クソコテは速やかにNG入れるといいよ。ラーメンが好きかどうかの話をしている中でお茶漬けもラーメンだと強弁するような、話題に入ることができない人だから。
0743デフォルトの名無しさん
2015/09/05(土) 15:18:48.81ID:ygimYbNM0744NAS6 ◆n3AmnVhjwc
2015/09/05(土) 15:19:27.30ID:zGjt7Ia9再帰：書けない漸化式はない、項をスタックするからメモリを消費する
ループ：項の参照が少ない漸化式のみ書ける、項をスタックしないからメモリ使用量は少ない
そんだけ
0745デフォルトの名無しさん
2015/09/05(土) 15:23:23.93ID:ygimYbNMループと再帰は厳密に完全互換ですよ
0746NAS6 ◆n3AmnVhjwc
2015/09/05(土) 15:31:56.99ID:zGjt7Ia9ノード検索とか再帰のノード全てメモしてループするとか
素直に再帰を使っちゃいかんのかいな
0747デフォルトの名無しさん
2015/09/05(土) 15:35:58.97ID:ygimYbNM可否の話をしただけ
>>744で可能性に対する言及が間違っているから、それを指摘したにすぎない
forでかけるものは、再帰でもかけるし
再帰でかけるものは、forでもかける
0748デフォルトの名無しさん
2015/09/05(土) 15:38:08.67ID:1TQgpEDy自分がほんまモンの馬鹿であるという自覚が全くないバカ
ま、見てる分には面白いけど他人に迷惑掛けんなよ
他人に迷惑を掛けるとなんとかキューゼットとかいう奴みたいに嫌われ者になっぞ
0749デフォルトの名無しさん
2015/09/05(土) 15:42:58.31ID:gAQxPGKS0750NAS6 ◆n3AmnVhjwc
2015/09/05(土) 18:40:37.54ID:zGjt7Ia9再帰：書けない漸化式はない
項をスタックするからメモリを消費する
ループ：項の参照が少ない漸化式のみ書ける
あるいは項をメモする必要がある
項をスタックしないからメモリ使用量は少ない
そんだけ
0751デフォルトの名無しさん
2015/09/05(土) 19:01:21.79ID:tTlkULNNスタックしない再帰があれば最強じゃん
0752デフォルトの名無しさん
2015/09/05(土) 19:32:52.27ID:6bqI6s7Iループは再帰処理の一種だ。
0753デフォルトの名無しさん
2015/09/05(土) 19:37:09.10ID:Bq/cKCjD再帰は自己よ呼び出す関数だ。当然実行中の処理手順は無条件にスタックされる。
そして都合よく「再帰」と「ループ」を分けて見たり、全部再帰と言って見たり挙動不審なことをするのもやめれよ。
もはや会話が成り立たん。
ちなみに俺の場合は、一番最初の冒頭のレスで「極論的には再帰もループも同じ」
とした上で、その後は一貫して再帰とループを区別してんだよ。
すなわちCの状態のように関数とスタックの抽象化が出来てる状態で初めてループと再帰があるんだ。
君がやってることは犬小屋も本棚もどっちも「木」で出来てるから同じと言って見たり、
犬小屋と本棚は別物のように書いて見たり、
木の状態を指してこれは「犬小屋」と言って見たり、
「本棚」を指して「犬小屋」と言って見たり、
そもそもなんの話をしてるか分からなくなって見たり。
0754デフォルトの名無しさん
2015/09/05(土) 19:40:47.01ID:CMLBJgqr0755NAS6 ◆n3AmnVhjwc
2015/09/05(土) 20:00:58.23ID:zGjt7Ia9double t = 1.0;
if (s == 1) t = 2.0;
if (n == 1) return r;
return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI2() {
double sse = 0.00000000000001; double a = 0.125;
double b = sqrt(a); double c = 1.0 + 3.0 * b;
double d = sqrt(c); double e = 0.625;
double f = d - e; d = 2 * d;
b = f - b; c = c + f;
double npow = 4;
do {
npow = 2 * npow; f = (c + d) / 2;
d = sqrt(c * d); f = f - d;
d = 2 * d; b = b - f; c = f + d;
} while (sse < f);
f = f * f / 4; c = c + d;
return (c * c - f - f / 2) / (c * b - f) / npow;
}
どっちが簡単だと思う？
0756NAS6 ◆n3AmnVhjwc
2015/09/05(土) 20:25:21.94ID:zGjt7Ia9double t = 1.0;
if (s == 1) t = 2.0;
if (n == 1) return r;
return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
while (1 < n) {
t = (t * s / (2.0 * s + 1.0));
r = r + t;
s += 1;
n -= 1;
}
return 2.0 * r;
}
意地悪が過ぎたが、今度はマジ
どっちが可読性があるの？
0757NAS6 ◆n3AmnVhjwc
2015/09/05(土) 20:34:20.88ID:zGjt7Ia92(1+(1/3)+(1/3)(2/5)+(1/3)(2/5)(3/7)+...)
だからね
0758NAS6 ◆n3AmnVhjwc
2015/09/05(土) 20:49:22.97ID:zGjt7Ia9double calcPI(double r, double s, double n) {
double u = 1.0;
if (s == 1) u = 2.0;
if (n == 1) return r;
return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
double u = 2.0;
while (1 < n) {
t = (t * s / (2.0 * s + 1.0));
r = r + t;
s += 1;
n -= 1;
}
return u * r;
}
0759NAS6 ◆n3AmnVhjwc
2015/09/05(土) 21:09:08.26ID:zGjt7Ia9double calcPI(double r, double s, double n) {
double u = 1.0;
if (s == 1) u = 2.0;
if (n == 0) return r;
return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
double u = 1.0;
while (0 < n) {
t = t * s / (2.0 * s + 1.0);
r = u * (r + t);
s += 1;
n -= 1;
}
u = 2.0;
return u * r;
}
0760NAS6 ◆n3AmnVhjwc
2015/09/05(土) 21:16:59.43ID:zGjt7Ia90761デフォルトの名無しさん
2015/09/05(土) 21:27:52.93ID:tTlkULNNJavaできる？
Javaで2つのint型配列を結合する処理を再帰で書いてみて
0762NAS6 ◆n3AmnVhjwc
2015/09/05(土) 21:55:59.06ID:zGjt7Ia9#include <iostream>
void init(int * p, int n) {
for (; 0 < n; n--) p[n] = 0;
}
void disp(int * p, int n) {
std::cout << std::endl;
for (int i = 0; i < n; i++) std::cout << p[i] << " ";
std::cout << std::endl;
}
int recUnit(int i, int j, int *a, int na, int *b, int nb) {
if (i < na && j < nb) a[i] = b[j];
else return i;
return recUnit(i + 1, j + 1, a, na, b, nb);
}
void unit(int *a, int na, int *b, int nb, int *c, int nc) {
int i;
i = recUnit(0, 0, a, na, b, nb);
recUnit(i, 0, a, na, c, nc);
}
0763NAS6 ◆n3AmnVhjwc
2015/09/05(土) 21:56:37.35ID:zGjt7Ia9int i, j;
for (i = 0, j = 0; j < nb; i++, j++) if (i < na)a[i] = b[j];
for (j = 0; j < nc; i++, j++) if (i < na)a[i] = c[j];
}
int main()
{
int a[10], b[5] = { 0, 1, 2, 3, 4 }, c[5] = { 5, 6, 7, 8, 9 };
init(a, 10); unit(a, 10, b, 5, c, 5); disp(a, 10);
init(a, 10); unit2(a, 10, b, 5, c, 5); disp(a, 10);
return 0;
}
0764NAS6 ◆n3AmnVhjwc
2015/09/05(土) 22:03:28.78ID:zGjt7Ia9#include <iostream>
void init(int * p, int n) {
for (; 0 < n; n--) p[n - 1] = 0;
}
void disp(int * p, int n) {
std::cout << std::endl;
for (int i = 0; i < n; i++) std::cout << p[i] << " ";
std::cout << std::endl;
}
int recUnit(int i, int j, int *a, int na, int *b, int nb) {
if (i < na && j < nb) a[i] = b[j];
else return i;
return recUnit(i + 1, j + 1, a, na, b, nb);
}
void unit(int *a, int na, int *b, int nb, int *c, int nc) {
int i;
i = recUnit(0, 0, a, na, b, nb);
recUnit(i, 0, a, na, c, nc);
}
0765デフォルトの名無しさん
2015/09/05(土) 22:07:56.87ID:tTlkULNN∩＿＿__∩
／ ＼
./ ● ● .', C++やねー ありがとー
l ( _●_) l
彡､ |∪| ミ
i"./ ヽノ ',ヽ
ヽi iﾉ
', /
ヽ ／ /
', i! /
（___／ ＼___）
0766NAS6 ◆n3AmnVhjwc
2015/09/05(土) 22:24:32.63ID:zGjt7Ia9void unit2(int *a, int na, int *b, int nb, int *c, int nc) {
int i, j;
for (i = 0, j = 0; j < nb; i++, j++) if (i < na) a[i] = b[j];
for (j = 0; j < nc; i++, j++) if (i < na) a[i] = c[j];
}
int main()
{
int a[10], b[4] = { 0, 1, 2, 3 }, c[6] = { 4, 5, 6, 7, 8, 9 };
init(a, 10); unit(a, 10, b, 4, c, 6); disp(a, 10);
init(a, 10); unit2(a, 10, b, 4, c, 6); disp(a, 10);
return 0;
}
0767NAS6 ◆n3AmnVhjwc
2015/09/05(土) 22:31:18.83ID:zGjt7Ia9漸化式定義に忠実で書きやすいのが再帰だよ
0769NAS6 ◆n3AmnVhjwc
2015/09/05(土) 22:47:45.27ID:zGjt7Ia9int recFor(int i, int n, int a) {
if (n <= i) return i;
recForFunc();
return recFor(i + a, n, a);
}
std::cout << recFor(0, 10, 2) << std::endl;
for (i = 0; i < 10; i += 2) recForFunc();
std::cout << i << std::endl;
ループと再帰の違いは
スコープスタックを保存しているかしていないかだけ
0770NAS6 ◆n3AmnVhjwc
2015/09/05(土) 22:57:11.75ID:zGjt7Ia9forはpopしながら戻る機能はない
0771デフォルトの名無しさん
2015/09/05(土) 22:59:40.11ID:IJjvRwCO自分の関数自身を呼び出しているかだけ。
反論あるならどうぞ？
0772NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:03:39.21ID:zGjt7Ia9if (n <= i) return i;
//pushしたiを使う時はここに処理
recForFunc();
i = recFor(i + a, n, a);
//popしたiを使う時はここに処理
return i;
}
0773NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:14:34.40ID:SH0QgRhIめっちゃ適当に書くけどこれも再帰
class A{
public:
A* func(){...return this;}
};
A* crnt;
while(true){
crnt = crnt->func();
//crntへの再帰処理＆NEXT処理
}
0774NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:19:20.41ID:zGjt7Ia9ttp://nas6.main.jp/sptr.cpp
ttp://nas6.main.jp/NAS6_cntn_ptr.h
ttp://nas6.main.jp/NAS6_tree_clct.h
実例は↑の
//再帰構文例1
//再帰構文例2
とか
0775NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:24:29.51ID:zGjt7Ia9みたいに書くのがノード検索を
なんも考えないで書ける
0776デフォルトの名無しさん
2015/09/05(土) 23:30:27.24ID:htzS6HSTそれに近いコードを
「再帰」だって主張している
ページを見つけてきてね（大爆笑）
0777デフォルトの名無しさん
2015/09/05(土) 23:32:10.40ID:htzS6HSTfuncの中でfuncを呼び出していないから
再帰ではない。
0778NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:36:14.88ID:zGjt7Ia9の
template<typename T>
void disp_NAS6_tree_clct(NAS6_tree_clct<T>* root);
template<typename T>
void disp_NAS6_tree_clct_key(NAS6_tree_clct<T>* root, string fk);
とか、ノード検索をなんも考えないでノード検索が出来ちゃう
0779NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:38:50.80ID:zGjt7Ia9ttp://msdn.microsoft.com/ja-jp/library/Cc429242.aspx
win32api
FindNextFile()
0780デフォルトの名無しさん
2015/09/05(土) 23:38:57.11ID:tTlkULNN0781デフォルトの名無しさん
2015/09/05(土) 23:40:03.04ID:htzS6HST「再帰」って書いてないね。
やっぱり再帰じゃなかったね。
逆の証拠を見つけてくれてあがとう（大爆笑）
0782デフォルトの名無しさん
2015/09/05(土) 23:41:35.40ID:htzS6HSTアホのオレオレ定義だよなぁ（大爆笑）
0783NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:45:35.82ID:zGjt7Ia9FindNextFile 再帰
0784デフォルトの名無しさん
2015/09/05(土) 23:48:34.61ID:htzS6HSTお前がググって
自分で証拠を見つけ出すんだよ（大爆笑）
自分の仕事を（出来ないからって）
他人にやらせるな。
0786デフォルトの名無しさん
2015/09/05(土) 23:53:43.47ID:tTlkULNNうむ、再帰構造と再帰処理を混同しておられるとしか思えぬ。
0787デフォルトの名無しさん
2015/09/05(土) 23:54:28.66ID:htzS6HST言葉が足りないぞ？（大爆笑）
>>784
>>783
の検索結果のほぼ全てに
FindNextFileを使って再帰を使ったコードが有ります。
再帰というのは自分の関数自身を呼び出すものなので、
大概そのようになっています。
つまり、検索の一番目だと、このコメントの部分が再帰です。
（FindNextFileの行には再帰とは書いていない）
void searchDir(char *lpszDir,HWND hwLst) { /* サブディレクトリ探索 */
省略
if ((fFind.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)!=0 &&
lstrcmp(fFind.cFileName,".")!=0 &&
lstrcmp(fFind.cFileName,"..")!=0){ /* サブディレクトリの処理 */
省略
searchDir(lpszSDir,hwLst); /* 再帰呼び出し */
}
while (FindNextFile(hSearch,&fFind)) { /* 全ファイルを処理 */
省略
searchDir(lpszSDir,hwLst);
}
}
FindClose(hSearch);
}
0788NAS6 ◆n3AmnVhjwc
2015/09/05(土) 23:54:52.90ID:zGjt7Ia9お前あほ杉
なんも分かってないなら書き込むな
0789デフォルトの名無しさん
2015/09/05(土) 23:55:51.09ID:htzS6HSTわかってるから書き込んでいる。
これも「再帰」（大爆笑）
0790デフォルトの名無しさん
2015/09/05(土) 23:57:07.95ID:m0Ws+Wye話が再帰してる（大爆笑）
0791デフォルトの名無しさん
2015/09/06(日) 00:00:00.32ID:aj7iBxVG「Xは再帰」「Yは再帰」「Zは再帰」って、いくらコードを書いても根拠にならないのは分かってる？
お前が書かなきゃならんことは「Xが再帰であることの根拠」であるのだから、お前の頭の中にしかない「再帰関数の定義」を書かないといけない。
もしオレオレ定義じゃないなら>>741や>>713の再帰関数の定義に、お前の書くコードがどう当てはまるのか書かないといけない。
そんで結局NAS6 ◆n3AmnVhjwcの主張は何なの？再帰関数が好きなの嫌いなの？
スレ違いも大概にしなさいよ。
0792デフォルトの名無しさん
2015/09/06(日) 00:01:55.86ID:8kAWPtv+719 名前：NAS6 ◆n3AmnVhjwc [] 投稿日：2015/09/05(土) 12:25:42.76 ID:zGjt7Ia9 [22/59]
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
な、これは再帰だろ、頭が悪いんだから、教授に迷惑をかけるなよ
0793NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:02:26.01ID:miXQ60MgそのsearchDirの書式を簡単にして
ttp://nas6.main.jp/sptr.cpp
の
template<typename T>
void disp_NAS6_tree_clct(NAS6_tree_clct<T>* root);
template<typename T>
void disp_NAS6_tree_clct_key(NAS6_tree_clct<T>* root, string fk);
とか、ノード検索をなんも考えないでノード検索が出来ちゃう
0794デフォルトの名無しさん
2015/09/06(日) 00:02:42.93ID:8kAWPtv+>>719を再帰で書き直すことができる
0795デフォルトの名無しさん
2015/09/06(日) 00:03:42.83ID:8kAWPtv+今は再帰かどうかの話をしてるんだが？（大爆笑）
searchDir の中で searchDir を読んでるから再帰。
FindNextFileを使ってるもの全てが再帰になるわけじゃない。
0796NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:07:36.08ID:miXQ60Mgこれをコンソールアプリでビルドしてみ
ノード検索されてるから
で、forとかループに対応するものと言うから
再帰「関数」ではなく再帰「処理」を書いてる
0797デフォルトの名無しさん
2015/09/06(日) 00:09:15.40ID:8kAWPtv+今は再帰の定義をしている。
全ての再帰はループで処理できる。
ループでノード検索しているから
それは再帰でない証拠（大爆笑）
ttp://nas6.main.jp/secret/ContainerPtr.htm
これをコンソールアプリでビルドしてみ
再帰使わずにノード検索できてるから
あ、ちなみに、このコードは俺が書いたんだよ？
0798NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:13:16.02ID:miXQ60Mgその振る舞いが決定されるから
ttp://nas6.main.jp/sptr.cpp
の
template<typename T>
void disp_NAS6_tree_clct(NAS6_tree_clct<T>* root);
template<typename T>
void disp_NAS6_tree_clct_key(NAS6_tree_clct<T>* root, string fk);
こう書いたんだよ
0799NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:16:13.79ID:miXQ60Mgなにこのカス
0800NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:22:17.38ID:miXQ60Mgじゃあ、デストラクタがどう呼ばれるか説明してみ
つうか、俺のサイトにお前がアップしたの？
0801片山博文MZ ◆T6xkBnTXz7B0
2015/09/06(日) 00:29:02.94ID:0zNPIayW0802NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:31:05.32ID:CQ0buOj1数時間で↑のデストラクタの振る舞いが読めたら褒めちゃいます
0803NAS6 ◆n3AmnVhjwc
2015/09/06(日) 00:48:13.59ID:CQ0buOj1さっぱり分からんと思うけどね
0804デフォルトの名無しさん
2015/09/06(日) 01:09:59.10ID:laHESI+60805NAS6 ◆n3AmnVhjwc
2015/09/06(日) 01:12:42.58ID:miXQ60Mg_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
メモリリークゼロ
0806NAS6 ◆n3AmnVhjwc
2015/09/06(日) 01:15:51.45ID:miXQ60Mgint *p = new int;
#ifdef _MSC_VER
って書くと、int分４バイトだけリーク
0807デフォルトの名無しさん
2015/09/06(日) 01:32:13.72ID:aj7iBxVGそれができないなら自分のサイトに引きこもっていろ。
0808NAS6 ◆n3AmnVhjwc
2015/09/06(日) 01:37:20.23ID:miXQ60Mg再帰「関数」ならば、それで完結した書き方を
書かなきゃならなくて適宜運用に不向き
0809デフォルトの名無しさん
2015/09/06(日) 01:41:27.92ID:aj7iBxVG0810デフォルトの名無しさん
2015/09/06(日) 01:43:51.10ID:Zg6i8dH9普通は再帰関数で行う処理のことを再帰処理って言うんだと思うよ。
0811NAS6 ◆n3AmnVhjwc
2015/09/06(日) 01:48:22.86ID:CQ0buOj1for,while使うの嫌いで基本的に再帰多用するんだが、だめなの？
皆から敬遠されてる気がする
for,whileって言うから、それに対応するものは
スレタイの再帰「関数」じゃなくて、再帰「処理」だからだよ
0812NAS6 ◆n3AmnVhjwc
2015/09/06(日) 01:55:27.64ID:CQ0buOj1再帰的定義
0813デフォルトの名無しさん
2015/09/06(日) 01:56:17.98ID:8PjODHJ70814NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:08:49.81ID:miXQ60Mg//再帰構文例1
template<typename T>
void recHoge1(NAS6_tree_clct<T>* root, string fk) {
bool parent = false;
if (&root->recursiveInit() == nullptr) return;
NAS6_tree_clct<T>* crnt = root;
//crnt = root; の時のcrntに適用の処理
//or : //if (crnt->conformkey(crnt, fk) != string::npos) //{...} //キー検索の時
while (!crnt->recursiveIsEnd(root)) {
//「再帰的定義: "再帰的定義"を参照」
parent = false;
crnt = &(crnt->recursiveNext(root), parent);
//or : //crnt = &(crnt->recursiveKeyNext(root, fk, parent));
//if(!parent) //{...} //crnt = Next; の時のcrntに適用の処理
//else //{...} //親に戻った時の処理
}
} 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)
0815NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:14:12.46ID:miXQ60Mgparent = false;
crnt = &(crnt->recursiveNext(root), parent);
//or : //crnt = &(crnt->recursiveKeyNext(root, fk, parent));
左辺のcrntは、右辺のcrntの子ノードに遷移してんの
0816デフォルトの名無しさん
2015/09/06(日) 02:17:05.47ID:aj7iBxVG>>719を再帰だ、などという戯言が通らなくて癇癪起こしているだけじゃないか。
で、>>812の定義に>>719がどう当てはまっているんだ？俺には分からない。
もしもsum = sum + iが再帰的定義なんだと思っているなら、それは単なる代入だから違うぞ。
0817NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:20:56.64ID:CQ0buOj1ああ、こっちはキーの一致の次のノードで子とは限らんけど
再帰だからもちろん親のノードにも最下層まで行ってから帰ってくるよ
0818デフォルトの名無しさん
2015/09/06(日) 02:21:09.18ID:8PjODHJ7なんか無言で言ってることを切り替えてるようだけど。
0819NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:24:47.62ID:miXQ60Mgf(n+1) = f(n) + i;
sum = sum + i;
0820デフォルトの名無しさん
2015/09/06(日) 02:26:17.85ID:8PjODHJ70821NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:28:04.25ID:CQ0buOj10822デフォルトの名無しさん
2015/09/06(日) 02:32:22.07ID:8PjODHJ7ただそれは迷惑だからそのへんも考えれるようになればいいね
0823NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:33:09.17ID:CQ0buOj1f(n+1) = f(n) + i;
sum = sum + i;
左辺はn+1項で、右辺はn項
0824NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:40:59.21ID:CQ0buOj1>>656
おま、戻り値を使いまわしたら基本的に再帰じゃないの？。。。
最初に書きました
戻り値の使い回しは基本的にn+1項の定義
0825NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:52:22.91ID:CQ0buOj1「再帰的定義: "再帰的定義"を参照」
f(n+1) = f(n) + i;
sum = sum + i;
左辺はn+1項までの和で、右辺はn項までの和
0826NAS6 ◆n3AmnVhjwc
2015/09/06(日) 02:53:55.79ID:miXQ60Mg0827NAS6 ◆n3AmnVhjwc
2015/09/06(日) 03:05:39.93ID:miXQ60Mg0828デフォルトの名無しさん
2015/09/06(日) 03:21:13.07ID:Zg6i8dH9君は他の人が言う再帰をどう読んでたの？
0829デフォルトの名無しさん
2015/09/06(日) 03:21:47.38ID:aj7iBxVG一方のfは、初期値も含めて正確に表せばf(n) = if n = 0 then 0 else f(n-1) + 1となっていて、fを定義するのにf自身が必要。
これが再帰的定義。
0830NAS6 ◆n3AmnVhjwc
2015/09/06(日) 03:30:27.61ID:miXQ60Mg0831NAS6 ◆n3AmnVhjwc
2015/09/06(日) 03:33:43.48ID:CQ0buOj10832NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:00:23.70ID:g2NsvO1D初項：f(n = 0) = 0
f(1) = 0 + i
f(2) = f(1) + i = i + i
f(3) = f(2) + i = 2 * i + i
...
f(n + 1) = f(n) + i
0833デフォルトの名無しさん
2015/09/06(日) 04:17:34.08ID:aj7iBxVGint sum = 0とした後にどう更新しようが再帰的とは呼ばないんだよ。
百歩譲ってこれを再帰的定義と呼ぶのなら、当てはまる例が多すぎて何の価値もない概念になる。i++も再帰になるし
int y = 1;
int x = 2;
x = y
としたら偶々x = x/2をという処理になるからこれもお前の言う再帰的定義になるよな。
そんな馬鹿なもんにわざわざ名前を付ける意味も無いし、好き嫌いも語れんよな。
0834NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:18:39.27ID:g2NsvO1Dでは、理系の学部を卒業するのは奇跡だろ
0835NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:20:59.76ID:CQ0buOj10836NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:30:52.77ID:CQ0buOj1ゆとりって、そんなヒドイの？
0837NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:34:02.41ID:CQ0buOj10838NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:39:58.28ID:miXQ60Mg学部で習わなかった？
0839NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:45:55.83ID:miXQ60Mg理系ならば情報処理の単位で
漸化式からの再帰定義は
カリキュラムに多分あるはずだけど？
0840デフォルトの名無しさん
2015/09/06(日) 04:54:07.46ID:8PjODHJ7自信満々に書き込んでる内容自体が全部ずれてるからね。
で、仮にそれが再帰だとして言いたいことはなんだ？
0841NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:55:04.91ID:miXQ60Mg>>757
>>759
0842NAS6 ◆n3AmnVhjwc
2015/09/06(日) 04:58:01.28ID:CQ0buOj1みたいなのを自分でやらずに
コピペ提出したんだろ
0843デフォルトの名無しさん
2015/09/06(日) 05:05:14.35ID:8PjODHJ7つーか再帰の定義を世間のプログラマと同じにしたらどうだ
0844NAS6 ◆n3AmnVhjwc
2015/09/06(日) 05:25:54.12ID:g2NsvO1Ddouble calcPI(double r, double s, double n) {
double u = 1.0;
if (s == 1) u = 2.0;
if (n == 0) return u * ( r + (r * s / (2.0 * s + 1.0)));
return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
double u = 1.0;
while (0 <= n) {
t = t * s / (2.0 * s + 1.0);
r = u * (r + t);
s += 1;
n -= 1;
}
u = 2.0;
return u * r;
}
0845NAS6 ◆n3AmnVhjwc
2015/09/06(日) 05:31:14.68ID:CQ0buOj1>>759
0846デフォルトの名無しさん
2015/09/06(日) 09:07:19.68ID:8kAWPtv+> sumを定義するのにsumを使っていないから駄目で、sum = sum + iは定義じゃなくて単なる更新だから再帰的定義ではない。
> int sum = 0とした後にどう更新しようが再帰的とは呼ばないんだよ。
ホントその通り。
頭の悪さがにじみ出てるよねｗ
0847デフォルトの名無しさん
2015/09/06(日) 10:34:04.98ID:DHZQ2m5W0848NAS6 ◆n3AmnVhjwc
2015/09/06(日) 11:30:18.37ID:miXQ60Mg初項：f(n = 0) = 0
f(1) = f(0) + i = 0 + i
f(2) = f(1) + i = i + i
f(3) = f(2) + i = 2 * i + i
...
f(n + 1) = f(n) + i
sum = sum + i
>>846
どう見ても漸化式通りの振る舞い
0849デフォルトの名無しさん
2015/09/06(日) 11:31:06.67ID:8kAWPtv+関数が自分自身の関数を
呼び出していることって書いてあった。
0850NAS6 ◆n3AmnVhjwc
2015/09/06(日) 11:36:22.64ID:miXQ60Mgヒントってか答え
初項：f(n = 0) = 0 i(n = 0) = 1
i(n + 1) = i(n) + 1
f(1) = f(0) + i(0) = 0 + i(0)
f(2) = f(1) + i(1) = i(1) + i(0)
f(3) = f(2) + i(2) = i(1) + i(0) + i(2)
...
f(n + 1) = f(n) + i(n)
sum = sum + i
>>846
どう見ても漸化式通りの振る舞い
0851デフォルトの名無しさん
2015/09/06(日) 11:40:30.06ID:8kAWPtv+関数が自分自身の関数を
呼び出していることらしいね。
0852NAS6 ◆n3AmnVhjwc
2015/09/06(日) 11:54:16.59ID:miXQ60Mgn-1 までの和に n を足せば nまでの和が得られる、という原理に忠実な計算なんで
再帰以外のなにものでもないんだけど、基礎論触ったことないとわかんないかもね。
656 ：デフォルトの名無しさん：2015/09/04(金) 23:29:28.63 ID:vuZU5Hwi
>>652
ループじゃんｗ
書けば理解できるのか？
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
0853NAS6 ◆n3AmnVhjwc
2015/09/06(日) 11:57:27.68ID:miXQ60Mgi(n + 1) = i(n) + 1
f(1) = f(0) + i(0) = 0 + i(0)
f(2) = f(1) + i(1) = i(1) + i(0)
f(3) = f(2) + i(2) = i(1) + i(0) + i(2)
...
f(n + 1) = f(n) + i(n)
↓が↑こういう漸化式になってるのが理解できないのか？
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
0854デフォルトの名無しさん
2015/09/06(日) 12:02:33.74ID:8kAWPtv+誰も漸化式であることを否定していない。
漸化式をとく問題を
ループで書くか再帰で書くかって話をしている。
再帰で書くとスタックを消費する。
場合によってはスタックオーバーフローを起こす。
だからスタックオーバーフローを気にするならば
ループで書く。そして多くの場合ループのほうが速い。
という話をしている。
0855NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:02:46.10ID:CQ0buOj1i(n + 1) = i(n) + 1
f(1) = f(0) + i(0) = 0 + 1
f(2) = f(1) + i(1) = i(1) + i(0)
f(3) = f(2) + i(2) = i(0) + i(1) + i(2)
...
f(n + 1) = f(n) + i(n)
↓が↑こういう漸化式になってるのが理解できないのか？
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
0856デフォルトの名無しさん
2015/09/06(日) 12:04:50.09ID:5yTvo1pNNAS6は自分で新しい言葉を定義するのが好きな精神障害者だろ
こういうのは「言語新作」と言って統合失調症特有の症状
要するに脳内はドーパミンドハドバ出まくりで覚せい剤を決めてるような感じになってるわけだ
これは統合失調症の陽性症状
ただ統合失調症はそんなに甘くなく「バッドトリップ」、すなわち陰性症状もひどい
だから2chに書き込みしてない時は死にたくなってるんじゃね
これじゃまともな日常生活を送れるわけがない
廃人みたいな私生活なんだろうな
なんでム板には精神異常者が多いんだろうねえ
0857デフォルトの名無しさん
2015/09/06(日) 12:07:52.59ID:8kAWPtv+コミュ障であることは明らか
0858NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:09:07.82ID:CQ0buOj1それは再帰の最適化だから
ループの再帰なんだけど？
再帰「関数」にせよ、ループ再帰にせよ
再帰（帰納）定義を実装しなければならない
0859デフォルトの名無しさん
2015/09/06(日) 12:13:50.10ID:n7lw0XxH末尾再帰じゃないと再帰じゃないっつってんだろ
0860NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:16:12.34ID:CQ0buOj1i(n + 1) = i(n) + 1
f(1) = f(0) + i(0) = 0 + 1
f(2) = f(1) + i(1) = i(1) + i(0)
f(3) = f(2) + i(2) = i(0) + i(1) + i(2)
...
f(n + 1) = f(n) + i(n)
↓が↑こういう漸化式になってるのが理解できないのか？
int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
それは再帰の最適化だから
ループの再帰なんだけど？
再帰「関数」にせよ、ループ再帰にせよ
再帰（帰納）定義を実装しなければならない
勝利 Ｖ（ブイ）！！
0861NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:20:43.70ID:miXQ60Mgおま、こうしか書けなくて
int hoge(){
//処理
return hoge();
}
こう書けないの？
int hage(){
//再帰push処理
int i = hage();
//再帰pop処理
return i;
}
0862デフォルトの名無しさん
2015/09/06(日) 12:25:45.01ID:5yTvo1pNハイの時間が長いほどローの時間が長くてひどいのは君が一番よく知ってるだろう
0863NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:29:41.96ID:miXQ60Mg0864デフォルトの名無しさん
2015/09/06(日) 12:33:58.57ID:8PjODHJ7こういっちゃなんだが、そう思ってるのは君だけだろう。
誰もがそれを逆に見てると思う。
0865NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:36:27.22ID:miXQ60Mg0866デフォルトの名無しさん
2015/09/06(日) 12:37:41.03ID:8PjODHJ7最初から読んだけど都合のいいことばっか書いたり読み飛ばしたり話変えたりってのが多いと思うよあなた
0868デフォルトの名無しさん
2015/09/06(日) 12:39:49.40ID:8PjODHJ70869デフォルトの名無しさん
2015/09/06(日) 12:40:45.30ID:8PjODHJ70870NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:46:22.23ID:miXQ60Mgfor(int i = 1; i <= 10; i++) {
sum = sum + i;
}
左辺のn+1項までの和を右辺のn項までの和を使って再定義します
他にどう読める？
0871デフォルトの名無しさん
2015/09/06(日) 12:49:12.16ID:8PjODHJ70872NAS6 ◆n3AmnVhjwc
2015/09/06(日) 12:50:45.59ID:CQ0buOj10873デフォルトの名無しさん
2015/09/06(日) 12:53:54.77ID:o0S33vFB0874NAS6 ◆n3AmnVhjwc
2015/09/06(日) 13:04:05.67ID:miXQ60Mg再帰関数講義pdf
0875デフォルトの名無しさん
2015/09/06(日) 13:15:58.86ID:VTGxMrVAあからさまに>>870は再帰じゃないって書いてあるが
0876デフォルトの名無しさん
2015/09/06(日) 13:22:34.79ID:1eGH5HCM現実を直視することって大切だよなって思いました
0877デフォルトの名無しさん
2015/09/06(日) 13:37:10.03ID:8kAWPtv+for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
これは明らかに再帰じゃないなｗ
これを再帰と説明しているページがアレば
いってくれ。
ないなら、黙ってろ。
0878デフォルトの名無しさん
2015/09/06(日) 13:38:20.61ID:8kAWPtv+>>877に対してだけだだ。
別に>>877と関係ないことを話すのは構わない（笑）
0879デフォルトの名無しさん
2015/09/06(日) 13:45:24.53ID:VTGxMrVAなのでそれを伴う会話、論理、もしくはそれ以前に単語の意味が理解出来ない
0880NAS6 ◆n3AmnVhjwc
2015/09/06(日) 13:46:24.96ID:miXQ60Mg再帰関数講義pdf
>>877
数列の和の再帰実装の項目が読めないの？
つづけて、
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，
どちらを使うべきだろうか?
両方使える場合は繰り替えし文を使うべきである．
計算速度も早いし，メモリの消費も少ないからである．
ではどこで，再帰関数の登場機会があるのか．
単純な問題であれば繰り替えし文の方が良いが，
複雑な問題となると再帰関数で記述はできるが，
繰り替えし文ではプログラムが大変困難な場合がある．
0881デフォルトの名無しさん
2015/09/06(日) 13:48:14.91ID:8kAWPtv+これのことだろうけど、
普通に、sumの中でsumを使っており、
そのsumの部分に再起するって書いてある。
/ / =========================
25 / / ユーザー定義関数 sum
26 / / =========================
27 i n t sum ( i n t n ) {
28
29 i f ( n == 1 ){
30 r e t u r n 1 ;
31 } e l s e {
32 r e t u r n sum ( n?1) + n ; / / 再帰する
33 }
34
35 }
0882デフォルトの名無しさん
2015/09/06(日) 13:49:21.03ID:8kAWPtv+2.1 再帰関数の例
自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．言葉の定義はともかく，具体的な例を見て
みよう．
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，どちらを使うべき
だろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリ
の消費も少ないからである．で
0883デフォルトの名無しさん
2015/09/06(日) 13:51:10.04ID:VTGxMrVA両方使える場合はループだの、複雑なことは再帰だのになんだよ。
言ってることが支離滅裂。
0884NAS6 ◆n3AmnVhjwc
2015/09/06(日) 13:57:22.43ID:miXQ60Mgそれはスコープスタックを
ループは保存しないで行ったっきり
再帰関数はpushして最下ノードまで行って
popして戻りつつ新たな下ノードのpush&pop検索をするからだよ
0885デフォルトの名無しさん
2015/09/06(日) 14:00:39.98ID:VTGxMrVAこの方法にしとけ
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
「これは再帰関数です」とか「これは再帰ではありません」とか明示的に書いてあるやつがいい
それなら理解出来るだろ
あと再帰やループの制御構造は、forやwhileや関数の呼び出しだからな。
決してsimではない
0886デフォルトの名無しさん
2015/09/06(日) 14:01:24.37ID:VTGxMrVA保存しないのがループなんだろうが
0887NAS6 ◆n3AmnVhjwc
2015/09/06(日) 14:07:04.25ID:miXQ60Mgクイックソート
そんなに言うならループで書いてみてよ
0888デフォルトの名無しさん
2015/09/06(日) 14:20:43.68ID:VTGxMrVA0890デフォルトの名無しさん
2015/09/06(日) 14:22:35.47ID:VTGxMrVA頭大丈夫か？
で？ルールで書けってことは「ループじゃない物」があるってことだよな？
それをここにいるほぼ全ての人は再帰と読んでるわけだが
0891NAS6 ◆n3AmnVhjwc
2015/09/06(日) 14:28:26.07ID:miXQ60Mg>両方使える場合はループだの、複雑なことは再帰だのになんだよ。
>言ってることが支離滅裂。
>両方使える場合はループだの、複雑なことは再帰だのになんだよ。
これが支離滅裂と思うんなら、クイックソートをループで書いてごらん
0892デフォルトの名無しさん
2015/09/06(日) 14:47:29.00ID:LToipCL/俺はループと再帰の区別してるから。
再帰はループとは別にあるし、再帰が良いと思った時は再帰だ。俺はな。
そして支離滅裂なのはそのURLじゃなくておまえだ。
おまえは区別しないなら全部同じ書き方でかけ。
ループと再帰と言う単語すら使うな。区別しないなら徹底的に区別するな。
それ以前に
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
これが再帰と書かれたサイトなり資料なり探し終わるまで黙っとけ。多数に言われてんだから。
0893デフォルトの名無しさん
2015/09/06(日) 14:51:28.16ID:pbpREKnW>>891
ループで書いた
http://peace.2ch.net/test/read.cgi/tech/1434079972/8
0894デフォルトの名無しさん
2015/09/06(日) 14:53:47.20ID:LToipCL/おまえはループと書くな。区別しないのだから
0895NAS6 ◆n3AmnVhjwc
2015/09/06(日) 14:55:26.13ID:miXQ60Mgクイックソートのループ実装はムチャ振りだから
0896デフォルトの名無しさん
2015/09/06(日) 14:57:32.04ID:LToipCL/関係ない話なら「後から」付き合うけど？
ごちゃごちゃ言ってないでさっさと探して来い。
0897NAS6 ◆n3AmnVhjwc
2015/09/06(日) 14:59:58.98ID:miXQ60Mgpush&popって、わざわざ作ってループにするくらいなら
素直に再帰関数使えよ
push&popのループは実装にもよるけど再帰関数とほぼ同じ
0898デフォルトの名無しさん
2015/09/06(日) 15:00:49.47ID:LToipCL/ふーーん
ま、これについても探してきてから相手してやるか
0900デフォルトの名無しさん
2015/09/06(日) 15:03:20.65ID:LToipCL/単語が必要になった時点でな
0901デフォルトの名無しさん
2015/09/06(日) 15:03:29.78ID:JSf18249ループで実装しとけばpopの過程で残りの処理やらんでいいわってときに
処理を打ち切れるんだよ。そういう意味では再帰をループで実装する意味はあるかと。
0902NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:03:31.85ID:miXQ60Mg>>884
push&pop実装してループすりゃ良いけど、それなら素直に再帰関数使え
0903デフォルトの名無しさん
2015/09/06(日) 15:04:44.43ID:8kAWPtv+2.1 再帰関数の例
自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．言葉の定義はともかく，具体的な例を見て
みよう．
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，どちらを使うべき
だろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリ
の消費も少ないからである．で
0904デフォルトの名無しさん
2015/09/06(日) 15:05:50.49ID:JSf18249再帰よりもループのが都合いいことあるんよ
関数呼び出しを途中で打ち切ること出来ぬでしょ
0905デフォルトの名無しさん
2015/09/06(日) 15:06:30.03ID:JSf18249これ。
0906NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:06:41.80ID:miXQ60Mg再帰関数に強制終了フラグを渡して
再帰呼び出しの直後にそのフラグをチェックすれば
強制終了できるけど？
0907デフォルトの名無しさん
2015/09/06(日) 15:09:02.09ID:LToipCL/pushとpopでループさせるなんて一言も言ってないし、
再帰使わないとも一言も言ってないし、
どうゆう会話の繋がり構造してんだ？
本気で頭大丈夫か？
しかもそれ完全にループと再帰分けて考えてるよな
0908NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:09:21.10ID:miXQ60Mgpush&popを実装するなら、正直、コンパイラに任せたほうが早いかもよ
0909デフォルトの名無しさん
2015/09/06(日) 15:10:20.50ID:LToipCL/馬鹿じゃねぇの
それは再帰として使ってるとは言わん
普通ではない事態だ
0910デフォルトの名無しさん
2015/09/06(日) 15:11:18.97ID:LToipCL/それをお前はあたかもそうではないような書き込みしてたよな
0912デフォルトの名無しさん
2015/09/06(日) 15:16:40.15ID:LToipCL/それと言葉に詰まると全く意味の分からない安価書くのやめれ
0913デフォルトの名無しさん
2015/09/06(日) 15:17:02.84ID:JSf18249アプリケーションを強制終了？
ちょっとそれはクソすぎると思うよ
0914デフォルトの名無しさん
2015/09/06(日) 15:20:07.58ID:LToipCL/sum = sum + i;
}
それとこれが再帰っつーのがお前の主張だからね。
話散らすのに一生懸命なようだけど。
0915NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:22:44.17ID:miXQ60Mg>>904
の振りだから
>>906
だろ
int recHoge(bool& esc){
int i;
//push処理
i=rechoge(esc);
if(esc) return i;
//pop処理
return i;
}
0916デフォルトの名無しさん
2015/09/06(日) 15:27:09.64ID:LToipCL/あんな、出来る出来ないじゃなくて
関数として扱われるえき概念を、処理中の内部からスタック操作なんてしねぇんだよ
0917デフォルトの名無しさん
2015/09/06(日) 15:31:29.36ID:LToipCL/ループや再帰と言う単語を用いないとできないわけだね。
ふーーん
0918NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:33:09.34ID:miXQ60Mgint recHoge(bool& esc){
int i;
//再帰のスタックがpushされている時の処理をここに書く
i=rechoge(esc);
if(esc) return i;
//再帰のスタックがpopされている時の処理をここに書く
return i;
}
0919デフォルトの名無しさん
2015/09/06(日) 15:34:42.95ID:LToipCL/0920NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:34:48.30ID:miXQ60Mgこれが俺の主張だというならアンカくれ
0921デフォルトの名無しさん
2015/09/06(日) 15:37:06.65ID:LToipCL/しかし一つや二つではない
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
より確実なのはこっち
0923NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:40:50.25ID:miXQ60Mg探せないなら
ループと再帰を区別しない
これはおれの主張じゃないからね
sumについては
>>855
0924デフォルトの名無しさん
2015/09/06(日) 15:42:44.84ID:LToipCL/その話題の発端は俺じゃないからそこについて続ける気もしない。
0925デフォルトの名無しさん
2015/09/06(日) 15:44:30.52ID:LToipCL/0926デフォルトの名無しさん
2015/09/06(日) 15:45:19.69ID:LToipCL/0927デフォルトの名無しさん
2015/09/06(日) 15:47:23.50ID:JSf182491個は末尾再帰なので単純にループでいいかと
https://ideone.com/r1BBhE
0928NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:51:29.03ID:miXQ60Mg漸化式
数列または関数列のいくつかの要素の間に成り立つ一般的な関係式
公比rの等比数列a1,a2,...,an,...におけるan+1=ranの類
「再帰的定義: "再帰的定義"を参照」
an+1=ran
0929デフォルトの名無しさん
2015/09/06(日) 15:51:35.63ID:8kAWPtv+大学のテキストだから書いてあることの
信頼性は高いだろう。
再帰関数講義pdf
http://akita-nct.jp/saka/lecturenote/2010/2e/text/recursive.pdf
2 再帰関数とは
2.1 再帰関数の例
自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．言葉の定義はともかく，具体的な例を見て
みよう．
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，どちらを使うべき
だろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリ
の消費も少ないからである．で
0930デフォルトの名無しさん
2015/09/06(日) 15:55:01.72ID:LToipCL/そんな広辞苑は捨てな
しかもそれプログラム用語の再帰じゃないから。
そんなことも分かってないようだけど。
0931NAS6 ◆n3AmnVhjwc
2015/09/06(日) 15:59:49.39ID:miXQ60Mg再帰処理
0932デフォルトの名無しさん
2015/09/06(日) 16:00:19.25ID:JSf18249同じ語句であっても文脈に応じて意味が変わるのよね。
再帰という同じ言葉であっても概念が異なっているのは明らかっすね。
変数への再帰的な代入と関数の再帰呼び出しとは違うものっすね。
プログラムで再帰といったときは関数の再帰呼び出しが一般的かな。
0933NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:02:09.24ID:miXQ60Mgあるものが定義されている場合，
その定義の中に，更にその定義されるべきものが，
簡単化されて，含まれているとき，
それは「再帰的である」と言われます。
循環論法に似ていますが，少し違います。
再帰的はその部分に含まれるものが全く同じものではなくて，
簡単になったもので，最終的終了条件が明示されているものです。
0934デフォルトの名無しさん
2015/09/06(日) 16:02:41.93ID:LToipCL/現場でそんな使い方してる人間なんていないだろよ
0935NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:07:43.63ID:miXQ60Mg0936NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:12:02.55ID:miXQ60Mg0937デフォルトの名無しさん
2015/09/06(日) 16:13:02.94ID:LToipCL/自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．
関数として抽象化されいてそのように扱う人間がいて、
その上でその内部から自身を呼び出すものが再帰。
プログラムにおいて漸化式は再帰と関係ない。
そしてその主張をするメリットもそのように使用するメリットもなく、そのように単語を使う習慣ももメリットもない。
0938デフォルトの名無しさん
2015/09/06(日) 16:14:07.91ID:LToipCL/0939893
2015/09/06(日) 16:21:21.57ID:uhlPSgY9＞単純にループでいいかと
うん，そのつもりだったんだが
さて >>927 で 配列 {3, 3, 5} をソートしてみてくれないか？
0940デフォルトの名無しさん
2015/09/06(日) 16:23:38.18ID:JSf18249会話をするときは相手がどういう概念を
述べているのか理解するようにしないと
言葉の表面から別の概念を連想して相手が間違いだと言っても
話が噛み合わないだけっすよ。
0941NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:25:07.28ID:miXQ60Mgこの場合は、
再帰「関数」とループで、ほぼ等価な処理を書いたのだが
この処理は、どちらも再帰処理だよ
定義に忠実な書き方と、最適化された書き方で
ほぼ等価な漸化式の処理であって、これらの何が気に食わないの？
0942デフォルトの名無しさん
2015/09/06(日) 16:25:30.37ID:fH7ggWtR脳の一部は正常に機能しているようだけど、他の部分が完全に機能していない
そういうのを普通「発達障害」「アスペ」「ADHD」とか言うんだけどな
好きなのを取れ
要するに一生何をしてもこのままです
0943デフォルトの名無しさん
2015/09/06(日) 16:25:40.08ID:8kAWPtv+http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Recursive.html
★再帰を使わない例
この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，
実際にこのようなプログラムを書く必要はありませんが。）
Function Kaijyou(n)
If n = 0 then
Kaijyou = 1
Else
Kaijyou = Kaijyou(n-1)*n
End if
End Function
となります。しかし，実は階乗関数は，再帰を使わなくても，
次のように実現することが出来ます。
Function Kaijyou(n)
F = 1
For i = 1 to n
F = F * i
Next i
Kaijyou = F
End Function
↑再帰を使わなくても，次のように実現することが出来ます。
0944デフォルトの名無しさん
2015/09/06(日) 16:28:08.20ID:LToipCL/その発想がすでに狂ってる。
0945デフォルトの名無しさん
2015/09/06(日) 16:29:29.10ID:JSf18249やってみた。次は何をやればいい？服はもう脱いだ。
https://ideone.com/1x5POb
0946デフォルトの名無しさん
2015/09/06(日) 16:30:15.65ID:LToipCL/そんな話は一切していない
0947デフォルトの名無しさん
2015/09/06(日) 16:36:31.57ID:fH7ggWtR脳が狂っている度合いがひどければひどいほど、傍からみて「あ、こいつ完全におかしい」と
分かるようになるんだが、本人は1ミリも狂っているとは思っていない
病識が全くないわけだ
軽症だと治りやすいよ
でも末期のガンとか生まれつき片手がないとかはどうしようもないだろう
この後者に相当するのがこいつ
0948NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:37:24.66ID:miXQ60Mg0949デフォルトの名無しさん
2015/09/06(日) 16:38:50.50ID:fH7ggWtRな、ほらそうだろ？お前、無職だろ？こんな奴雇う会社日本にねえよ
アメリカにでも行って一芸を買ってもらうこったな
でも見てたらその一芸すら怪しいようだが
0950NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:39:04.92ID:miXQ60Mgこの場合は、
再帰「関数」とループで、ほぼ等価な処理を書いたのだが
この処理は、どちらも再帰処理だよ
定義に忠実な書き方と、最適化された書き方で
ほぼ等価な漸化式の処理であって、これらの何が気に食わないの？
さて？これのどこがどう狂っているのか説明してくださいな
0951デフォルトの名無しさん
2015/09/06(日) 16:39:14.91ID:LToipCL/だからこうゆう展開になってしまう
0952デフォルトの名無しさん
2015/09/06(日) 16:40:05.81ID:LToipCL/そこに結びつける発想。
0953デフォルトの名無しさん
2015/09/06(日) 16:40:52.39ID:fH7ggWtRもうその発言だけで完全に狂ってると分かっちゃうよ
0954NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:42:56.55ID:miXQ60Mg0955デフォルトの名無しさん
2015/09/06(日) 16:43:54.24ID:LToipCL/普通の人にはしないような備考をわざわざ付けたのに、それでも勝手に勘違いしてるだろ
それを指して狂ってるって言ってんだよ
だから何も会話が成り立ってない。関係ない思うを関係あると思う。
そして概念のつながりである論理のやりとりが出来てないのに自分が出来てないと気づかない。
0956デフォルトの名無しさん
2015/09/06(日) 16:45:18.24ID:fH7ggWtR感情的にはまったくなっておりません
むしろ感情的になっているのはそちらの方だと思います
こういうのを「感情転移」と言います
もう少し言うと「投影機制」と言います
自分が感情的になっているのを認められないので、相手が感情的になっていると
錯覚してしまうのです
電車に乗ってて隣の電車が発車すると、自分の乗ってる電車が逆方向に動き出した
と錯覚するだろ？それとよく似ている
0957デフォルトの名無しさん
2015/09/06(日) 16:47:03.14ID:JSf18249それはこっちのセリフです！牛さんのように反芻してください!!
どうこれ？
0958デフォルトの名無しさん
2015/09/06(日) 16:48:22.69ID:LToipCL/いまは至って冷静だ
0959NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:48:38.17ID:miXQ60Mgこの場合は、
再帰「関数」とループで、ほぼ等価な処理を書いたのだが
この処理は、どちらも再帰処理だよ
定義に忠実な書き方と、最適化された書き方で
ほぼ等価な漸化式の処理であって、これらの何が気に食わないの？
だから↑がどう論理的に狂ってるか具体的にかけよ
0960デフォルトの名無しさん
2015/09/06(日) 16:49:14.49ID:LToipCL/その発想だって言ってんだろ
0961893
2015/09/06(日) 16:49:40.04ID:uhlPSgY9よくわかるが，今回の場合は反駁側も切れ味が悪い，揚げ足を取りきれていない
篭手狂人は「行っていることが正しい」可能性はないわけではない
問題は「不正確な表現」，百歩譲っても「表現が独特すぎて伝わっていない」
0962デフォルトの名無しさん
2015/09/06(日) 16:50:18.66ID:fH7ggWtRあららここまでひどいとただの投影じゃなくて投影性同一視が入ってるみたいですね
境界性パーソナリティ障害とか自己愛性パーソナリティ障害も併発してるようです
投影性同一視とは他人を利用した自己嫌悪です
本当は自分を嫌悪したいのですがどうしてもそれが嫌なのでまともな他人を嫌悪します
これはしばしば犯罪に発達します
危険ですよ
0963デフォルトの名無しさん
2015/09/06(日) 16:51:40.98ID:fH7ggWtRだとすればまあちょっとは自覚があるんじゃないですかね
そうなると治療すれば治る可能性もあるのに惜しいですね
このまま人生を棒に振っちゃうようで
0964デフォルトの名無しさん
2015/09/06(日) 16:53:01.63ID:fH7ggWtR「俺は悪くない！悪いのは社会だ！」
裁判所でそれ叫んでみてくださいよ
誰も認めちゃくれませんから
0965デフォルトの名無しさん
2015/09/06(日) 16:57:12.75ID:LKKBkxwK0966片山博文MZ ◆T6xkBnTXz7B0
2015/09/06(日) 16:57:13.89ID:0zNPIayW情報科学で漸化式は再帰的定義であると言える。
しかし、プログラミングでプログラムに書いた漸化式を「再帰処理」と言うと、
初心者にとって混乱極まりない上に迷惑であり、不適切な表現である。
0967NAS6 ◆n3AmnVhjwc
2015/09/06(日) 16:59:16.85ID:miXQ60Mgで
>>759
のようにほぼ等価な処理が書けるのに
再帰「関数」で実装されたもののみが「再帰処理」だとしたら
ループで最適化実装されたものは「ループ処理」で
再帰処理とは違う処理なのですか？
0968デフォルトの名無しさん
2015/09/06(日) 17:00:59.76ID:LToipCL/それ自体が関係ないのになぜその書き込みを引っ張る？
その処理が気に食う気に食わないの話はどっから出てきた？
なんで急に脈絡なくその書き込みの話をする？
漸化式は関係ないからって言われた直後、なんでその相手に自慢げに漸化式の話をする？
定義に忠実がなんだ？だからどうなんだ？満たされるのはお前の自己満足だけだろ
しかも自分の思い込みだけで狂ったように連呼する定義。
最適化？誰がそんなの望んだ？誰がそんな話した？噛み合ってないよな。
狂ってるんだよ
狂ったものは論理と最も遠い。
論理じゃないものに対して論理では答えられない。
0969デフォルトの名無しさん
2015/09/06(日) 17:05:43.20ID:aWMMHCvXそう。
そしてさらに、関数は処理だけを指すものではない。
人間側が関数を関数と言う概念として扱い、そのように人間が振舞うことで初めて関数は関数になる。
当然それと同等の物が再帰にある。
普通はこんな説明不要だが、お前はこの説明も受けておく必要がある。
0970デフォルトの名無しさん
2015/09/06(日) 17:05:55.81ID:8kAWPtv+再帰とは何かを勉強した方がいい。
http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Recursive.html
★再帰を使わない例
この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，
実際にこのようなプログラムを書く必要はありませんが。）
Function Kaijyou(n)
If n = 0 then
Kaijyou = 1
Else
Kaijyou = Kaijyou(n-1)*n
End if
End Function
となります。しかし，実は階乗関数は，再帰を使わなくても，
次のように実現することが出来ます。
Function Kaijyou(n)
F = 1
For i = 1 to n
F = F * i
Next i
Kaijyou = F
End Function
↑再帰を使わなくても，次のように実現することが出来ます。
0971NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:06:58.08ID:miXQ60Mg>なんでその相手に自慢げに漸化式の話をする？
漸化式から再帰処理コードを組み立てる
スタックオーバーロードがあるから、再帰関数は奥の手で
ループで書けるならそれに越したことはない
ループでひどく複雑になるようなときに、再帰関数で書く
0972デフォルトの名無しさん
2015/09/06(日) 17:08:24.25ID:8kAWPtv+大学のテキストだから書いてあることの
信頼性は高いだろう。
再帰関数講義pdf
http://akita-nct.jp/saka/lecturenote/2010/2e/text/recursive.pdf
2 再帰関数とは
2.1 再帰関数の例
自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．言葉の定義はともかく，具体的な例を見て
みよう．
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，どちらを使うべき
だろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリ
の消費も少ないからである．で
0973デフォルトの名無しさん
2015/09/06(日) 17:08:25.12ID:aWMMHCvXだからその発想が狂ってる。
そんな話はしていない。
だから論理にならない
0974NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:13:29.91ID:miXQ60Mg>>759
あのさ、このπを求めるコードで、まず関数入出力を見て
実装が、再帰関数実装とか、ループ実装とか、
普通、いちいち、そこまでこだわらないと思うんだけど
こだわるのは、精査検証が必要なときだけだろ
精査検証なら
>>971
0975デフォルトの名無しさん
2015/09/06(日) 17:14:49.58ID:fH7ggWtR酒買ってきた
まさにこれだよな
「論理的じゃないものに対して論理では答えられない」
狂ってる奴が「論理的に反駁してください」と言っているのを聞くと笑いそうになる
あのさあ・・・まず先に論理的に話すべきなのはそちらじゃないかね、って
でもそれが全く出来ない
だから発達障害なんだよ
0976デフォルトの名無しさん
2015/09/06(日) 17:15:55.83ID:fH7ggWtR×>>958
○>>968
>狂ってるんだよ
>狂ったものは論理と最も遠い。
>論理じゃないものに対して論理では答えられない。
俺が言いたい事と全く同じ
0977片山博文MZ ◆T6xkBnTXz7B0
2015/09/06(日) 17:16:46.42ID:0zNPIayW0978デフォルトの名無しさん
2015/09/06(日) 17:17:41.58ID:8kAWPtv+反論ができなくなってしまっているようだなｗ
http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Recursive.html
★再帰を使わない例
この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，
実際にこのようなプログラムを書く必要はありませんが。）
Function Kaijyou(n)
If n = 0 then
Kaijyou = 1
Else
Kaijyou = Kaijyou(n-1)*n
End if
End Function
となります。しかし，実は階乗関数は，再帰を使わなくても，
次のように実現することが出来ます。
Function Kaijyou(n)
F = 1
For i = 1 to n
F = F * i
Next i
Kaijyou = F
End Function
↑再帰を使わなくても，次のように実現することが出来ます。
0979NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:17:44.80ID:miXQ60Mg再帰は使うべきか
このように見てくると，再帰プログラムは効率の良くないプログラムと思うかもしれません。
実はある意味ではその通りです。それでは使う必要のないものなのでしょうか？
これも使わなくて良ければと言う前提に立てばその通りです。
一般に次のことが言えます。
•再帰プログラムは計算機に負荷をかけるプログラムである。
•時によっては，膨大な負荷をかけることもある。
•簡単に非再帰プログラムとして書けるものは再帰プログラムを使うべきではない。
それでも，再帰プログラムが基本的であると言われるのは何故でしょうか。
それは再帰プログラムが大きな力を秘めているからです。つまり
•再帰プログラムでは簡単に書けるが，非再帰プログラムはかなり複雑なプログラムになってしまうようなものがある。
ということです。
このような問題が意外とあるのです。再帰プログラム技法を，身につけたら，プログラミングを行う際，次のような視点で考えるのが良いかもしれません。
•まずは，非再帰プログラムで問題を考えてみる。
•難しいと判断した場合，再帰プログラムで考えてみる。
0980デフォルトの名無しさん
2015/09/06(日) 17:18:47.18ID:8kAWPtv+自分自身を呼び出したものが再帰なのだ。
大学のテキストだから書いてあることの
信頼性は高いだろう。
再帰関数講義pdf
http://akita-nct.jp/saka/lecturenote/2010/2e/text/recursive.pdf
2 再帰関数とは
2.1 再帰関数の例
自分自身を呼び出す関数を再帰関数 (recursive function) という．また，自分自身を呼び
出すことを再帰呼出し (recursive call) という．言葉の定義はともかく，具体的な例を見て
みよう．
2.2 なぜ，再帰関数なのか?
再帰関数と繰り返し文のどちらを使ってもプログラムが書ける場合，どちらを使うべき
だろうか? 両方使える場合は繰り替えし文を使うべきである．計算速度も早いし，メモリ
の消費も少ないからである．で
0981デフォルトの名無しさん
2015/09/06(日) 17:20:26.48ID:aWMMHCvXはいここでまた関係ない話になる。
今してる話は何が再帰か(定義と概念)、であって、
手段の問題ではない。
当然>>971もなんの関係もない。ただの手順。
そんな考えだから再帰中に再帰中の内部記憶を操作するとような発想を平気でする。
再帰を再帰として扱ってはいない。これは概念の問題。
再帰を扱う人がそれを再帰扱いしなければ、当然それは再帰ではない。
再帰かどうかと言うのはそういった所でも大きく区分けされる。
0983デフォルトの名無しさん
2015/09/06(日) 17:27:47.47ID:aWMMHCvXお前の再帰の定義が問題扱いされてるのに、
自分の正当性を得るために自分の定義を証明手段に使ってどうする
馬鹿なのか
0984デフォルトの名無しさん
2015/09/06(日) 17:28:54.74ID:1q8+1kZD自分が狂ってる事を正当化するために自分が書いた狂った定義を持ち出すのは
もはや負けを認めているのに等しいよな
0986デフォルトの名無しさん
2015/09/06(日) 17:32:05.22ID:1q8+1kZD今度は権威を使うのか
"虎の威を借る狐"
でもその虎が狂っていたらどうなる？ただの殺人虎だ
0987デフォルトの名無しさん
2015/09/06(日) 17:34:21.82ID:8kAWPtv+> >>931
> のリンクの大学教授の定義をコピペしたのが
> >>933
> だ
>>931のリンクってこれだよね？
http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Recursive.html
★再帰を使わない例
この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，
実際にこのようなプログラムを書く必要はありませんが。）
Function Kaijyou(n)
If n = 0 then
Kaijyou = 1
Else
Kaijyou = Kaijyou(n-1)*n
End if
End Function
となります。しかし，実は階乗関数は，再帰を使わなくても，
次のように実現することが出来ます。
Function Kaijyou(n)
F = 1
For i = 1 to n
F = F * i
Next i
Kaijyou = F
End Function
↑再帰を使わなくても，次のように実現することが出来ます。
0988デフォルトの名無しさん
2015/09/06(日) 17:34:24.36ID:aWMMHCvXそれは普通は使わない定義
0989NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:34:49.74ID:miXQ60Mg0990デフォルトの名無しさん
2015/09/06(日) 17:36:03.31ID:1q8+1kZDうはｗ
捏造入ってたのか
こりゃちゃんとリンク先見ないとな
>>989
何回でも言います
感情的になってるのはそっちです
0991デフォルトの名無しさん
2015/09/06(日) 17:37:16.64ID:1q8+1kZD0992NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:37:25.62ID:miXQ60Mg算数からやり直したらどう？
算数→数学→情報処理となって
再帰定義がなんぞやって定義されているんだよ
0993デフォルトの名無しさん
2015/09/06(日) 17:37:27.94ID:aWMMHCvX答えなくなったり話散らすね。
直接的に繋がりのある返答はかなり珍しい
他の人が増えてきて読みにくいんで終わり
0994デフォルトの名無しさん
2015/09/06(日) 17:38:07.17ID:uhlPSgY9おーうまくいくね>>983 では，これに苦心したんだが‥
0995デフォルトの名無しさん
2015/09/06(日) 17:38:14.61ID:aWMMHCvX数学用語とプログラム用語は別物だと言ったはずだ
0996NAS6 ◆n3AmnVhjwc
2015/09/06(日) 17:39:58.36ID:miXQ60Mgお前の中ではな
0997デフォルトの名無しさん
2015/09/06(日) 17:40:39.85ID:aWMMHCvX0998デフォルトの名無しさん
2015/09/06(日) 17:40:58.46ID:1q8+1kZDおやお前数学出来るのか
じゃあマクスウェルの方程式とかナビエ・ストークスの方程式の意味は説明出来るんだよな？
0999デフォルトの名無しさん
2015/09/06(日) 17:41:53.70ID:LZy823VQ1000デフォルトの名無しさん
2015/09/06(日) 17:42:12.67ID:1q8+1kZD自分を守るのが精一杯でちゃんと他人の質問に答えれなくなってるよな
1001１００１
Over 1000Threadもう書けないので、新しいスレッドを立ててくださいです。。。
レス数が1000を超えています。これ以上書き込みはできません。