X

なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net

0001デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
0165デフォルトの名無しさん
垢版 |
2015/12/19(土) 16:48:17.67ID:mZAnd63z
再帰と繰り返しは相互に変換可能なんだから、再帰で実行時間が読めないならば、繰り返しでも読めない。
こんなじょうしきも知らないの?
0166デフォルトの名無しさん
垢版 |
2015/12/19(土) 20:02:11.53ID:owy4KRbC
ごめん
0167デフォルトの名無しさん
垢版 |
2015/12/19(土) 20:16:05.69ID:hx9j/3Ds
再帰はシステムダウンの危険がある。
処理速度もはるかに遅くなる。

再帰の場合には、こうした実行時間が読めない特有の問題点がある。
0168デフォルトの名無しさん
垢版 |
2015/12/19(土) 22:02:48.92ID:EjHtX5K0
> 再帰はシステムダウンの危険がある。
そう言う環境ならば、システムダウンの可能性は繰り返しでもある。

> 処理速度もはるかに遅くなる。
ヘボが作った繰り返しは再帰よりはるかに遅い。
0173uy ◆Qawu9.2l1E
垢版 |
2015/12/20(日) 01:30:16.73ID:cCXQYS6+
# 1
def f
　if 条件
　　処理
　else
　　f()
　end
end

# 2
def f
　if 条件
　　f()
　end
end


# 3
def f
　case 条件
　when LABEL
　　f()
　end
end


末尾再帰されるパターンわからない奴ｗｗｗｗｗｗｗｗｗｗｗｗっうぃる？　
0175デフォルトの名無しさん
垢版 |
2015/12/20(日) 12:14:12.80ID:8RLYRFXT
>>175
漸化式
0177デフォルトの名無しさん
垢版 |
2015/12/20(日) 14:49:43.30ID:zNzoBoA2
ID:EjHtX5K0のような白痴ばかりだから
再帰厨だと馬鹿にされることになる。

再帰を愛して使うんだったら、
ループ版にはない深刻なデメリットがある事ぐらいちゃんと注意した上で、
効率や安全性を無視したプログラミングを楽しむべき。
0178デフォルトの名無しさん
垢版 |
2015/12/20(日) 17:18:50.85ID:37nsyMmy
繰り返しの唯一の利点は回数の制御が再帰よりも容易であること。
これ以外の利点はない。

バカにはそれが理解できないらしいが。
0180デフォルトの名無しさん
垢版 |
2015/12/20(日) 18:23:24.49ID:/qKlyz5E
ごめん
0181デフォルトの名無しさん
垢版 |
2015/12/20(日) 19:26:33.84ID:37nsyMmy
再帰はID:zNzoBoA2のように低知能には理解不能という弱点があるけど
ID:zNzoBoA2のような低知能の出現率は低いので全然問題無い
むしろ低知能者を検出試験としてのメリットの方が大きい
0182デフォルトの名無しさん
垢版 |
2015/12/20(日) 22:01:31.82ID:ywvYIxL3
再帰苦手だから何でもかんでもループ使ってすまん
0184デフォルトの名無しさん
垢版 |
2015/12/20(日) 22:51:10.83ID:zNzoBoA2
もし再帰が理解出来たつもりなら、ちゃんとループに直せるぐらいのプログラミング技術は備えなくちゃ。

最低でもそれくらいの技術や知能が無ければ
再帰を楽しむことはできないよ。
0185デフォルトの名無しさん
垢版 |
2015/12/21(月) 02:17:48.47ID:EKnooMo4
「再帰には深刻なデメリットがある」キリッ
なんて発言する低知能人は再帰を理解してるはずが無い、理解不能なものを怖れている。未開人と同じ。
0186デフォルトの名無しさん
垢版 |
2015/12/21(月) 09:54:25.69ID:S8kWm1db
ループを恐れるのは、ループにするだけの知識・経験を欠いているから。

その程度じゃあプログラミングの世界からすぐに消えるだけの存在。
再帰厨は、現実で満たされないのでスレで妄想を垂れ流すことしかできないクズ。
0187デフォルトの名無しさん
垢版 |
2015/12/21(月) 10:52:48.60ID:zel3cCjW
関数内にjmpも好き勝手にやるタイプだからどうとも言わんけど、
再帰否定派はまさか単一のアーキテクチャの話してないよな？
アルゴリズムとして再帰がイケてないって話だよな？
0188デフォルトの名無しさん
垢版 |
2015/12/21(月) 14:23:04.48ID:MyhUNItP
そうなのか？
0189デフォルトの名無しさん
垢版 |
2015/12/21(月) 14:51:29.83ID:EKnooMo4
>>186
必死で再帰を否定しているバカを弄っているだけで、繰り返しを否定しているわけでは無い

やっぱり低知能なんだな。
0190デフォルトの名無しさん
垢版 |
2015/12/21(月) 18:43:17.30ID:u4st+H+L
みなさん、これが「弄ってるって言いたいバカ」ですｗ
0191デフォルトの名無しさん
垢版 |
2015/12/22(火) 08:48:59.73ID:kujr6tD9
迷信を信じ込んで再帰を否定してるバカが
深刻なデメリット(爆笑)、例えば
> 処理速度もはるかに遅くなる。
を、実証すればスレ終了するのに。
0192デフォルトの名無しさん
垢版 |
2015/12/22(火) 11:16:51.41ID:4uBr+2Cy
>>191
そういう超基本的なプログラミング知識が無いのに
なんでプログラム板にいるの？

そもそもプログラミング経験無いだろ、お前。
0193 ◆tAo.kQ2STk
垢版 |
2015/12/22(火) 12:54:32.04ID:S5fGjlFA
異様に伸びてると思ったら深刻な問題祭りかい

いくらでも例外は挙げられるけど
再帰で書こうがループで書こうが計算時間や空間計算量はそんなに変わらんから
書きやすく、読みやすい方で書いたほうが良いんじゃない？

そんなに変わらないって言うのは十分大きな入力に対して精々2〜3倍以下に納まるって意味だからね。
1時間掛かる処理を20マイクロ秒速くする為にごちゃごちゃ書き換えるのは結構な事だけど。
0194デフォルトの名無しさん
垢版 |
2015/12/22(火) 14:08:14.84ID:dkSLpih8
はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。
0195デフォルトの名無しさん
垢版 |
2015/12/22(火) 17:31:14.37ID:qPz15M1W
>>193
いやね，絶対的に再帰でないと書けない，いや非常に書きにくいものはあるのは確かで．
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか？？」と逡巡してしまう．
こういう話題があまり発展しないのはどうしたわけですかね

関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題，誰か‥私は挫折した‥
0196uy ◆Qawu9.2l1E
垢版 |
2015/12/22(火) 18:25:40.50ID:/7VurpfC
再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事

なんの言語とは言わないけど
0197デフォルトの名無しさん
垢版 |
2015/12/22(火) 19:03:19.84ID:8Du/ashj
それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット
0198デフォルトの名無しさん
垢版 |
2015/12/22(火) 22:57:38.64ID:kujr6tD9
>>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。

「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。
0199uy ◆Qawu9.2l1E
垢版 |
2015/12/22(火) 23:43:59.28ID:qcwFiUkP
>>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな
0203デフォルトの名無しさん
垢版 |
2015/12/23(水) 01:25:49.85ID:zjRNfIWb
>>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。

fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
}
0204デフォルトの名無しさん
垢版 |
2015/12/23(水) 02:04:18.65ID:3NYqkGXc
>>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。
0205デフォルトの名無しさん
垢版 |
2015/12/23(水) 07:21:41.71ID:fM9ORKUP
>>201
必死で再帰否定してるバカは知能が低いというエビデンス乙

シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい
0206デフォルトの名無しさん
垢版 |
2015/12/23(水) 07:28:38.71ID:fM9ORKUP
Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。
0207デフォルトの名無しさん
垢版 |
2015/12/23(水) 08:47:35.90ID:2F8TsTF+
最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね
0208デフォルトの名無しさん
垢版 |
2015/12/23(水) 08:59:40.61ID:r+tlUph/
名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな

>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。
0211デフォルトの名無しさん
垢版 |
2015/12/23(水) 09:15:53.17ID:fM9ORKUP
>>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。

シェルスクリプトを持ち出した時点で「スタックは容量制限が厳しい(場合もある)リソース」
を自分で否定しちゃうところが再帰否定してるバカが低知能であるもう一つのエビデンス(笑)

(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。
0214デフォルトの名無しさん
垢版 |
2015/12/23(水) 11:25:42.60ID:r+tlUph/
そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。
0215デフォルトの名無しさん
垢版 |
2015/12/23(水) 11:53:11.24ID:/Snk+v/P
externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる
0217デフォルトの名無しさん
垢版 |
2015/12/23(水) 12:46:44.21ID:2bKYe5U2
>>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。
0219デフォルトの名無しさん
垢版 |
2015/12/23(水) 16:35:42.36ID:u0B3Sjd8
だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか？

処理件数が増えたら速度の差なんて、何万倍どころじゃないし。
0221uy ◆Qawu9.2l1E
垢版 |
2015/12/23(水) 16:45:18.40ID:uhnrlQdn
>>219
ファーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
0223デフォルトの名無しさん
垢版 |
2015/12/23(水) 17:15:03.86ID:2bKYe5U2
>>222
きったねえソースだな。どこの糞コード持ってきてんだ。
見せてやるよ、本気のクイックソートってやつをな。

void qsort(int a[], int left, int right)
{
　int i, last;

　if (left >= right)
　　return;

　swap(a, left, (left + right) / 2);

　last = left;

　for (i = left + 1; i <= right; i++)
　　if(a[i] < a[left])
　　　swap(a, ++last, i);

　swap(a, left, last);

　qsort(a, left, last - 1);
　qsort(a, last + 1, right);
}
0224デフォルトの名無しさん
垢版 |
2015/12/23(水) 17:27:00.65ID:fM9ORKUP
>>223
10000倍高速化の比較対象はそれでも良いぞ。
0226デフォルトの名無しさん
垢版 |
2015/12/23(水) 18:11:01.01ID:2bKYe5U2
>>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。
0227uy ◆Qawu9.2l1E
垢版 |
2015/12/23(水) 18:27:35.24ID:PjxVSF2U
アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・｀)


def qsort a , left , right
  return if left >= right
  swap a , left , (left + right) / 2
  last = left

  (left + 1).step(right) do |i|
    if a[i] < a[left]
        swap a , last+=1 , i
    end
  end
  swap a , left , last
  qsort a , left , last - 1
  qsort a , last + 1, right
end
0228デフォルトの名無しさん
垢版 |
2015/12/23(水) 18:50:34.28ID:fM9ORKUP
>>225
最低10000倍ね。笑

>>219
>処理件数が増えたら速度の差なんて、何万倍どころじゃないし。

あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑
0231デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:10:25.42ID:fM9ORKUP
ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。
0232デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:12:02.95ID:fM9ORKUP
万は間違いだったとしても、最低でも倍速は楽勝なんだろ。
0233デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:29:26.28ID:zjRNfIWb
>>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。
0234デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:33:54.64ID:QhR+qVh6
>>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK
0235デフォルトの名無しさん
垢版 |
2015/12/23(水) 22:55:30.83ID:zjRNfIWb
いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。
0236デフォルトの名無しさん
垢版 |
2015/12/23(水) 23:35:43.46ID:fM9ORKUP
>>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。
0237デフォルトの名無しさん
垢版 |
2015/12/23(水) 23:43:11.94ID:QhR+qVh6
>>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。
0238デフォルトの名無しさん
垢版 |
2015/12/23(水) 23:58:42.12ID:2bKYe5U2
>>237
あたりまえ
0242uy ◆Qawu9.2l1E
垢版 |
2015/12/24(木) 08:02:14.94ID:Ecjqx/Av
スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ
0243デフォルトの名無しさん
垢版 |
2015/12/24(木) 08:55:59.49ID:Q6U3kr4L
黒魔術師は再帰関数が大好き
0245デフォルトの名無しさん
垢版 |
2015/12/24(木) 11:57:48.07ID:2ShnOfV/
再帰を必死に否定しているバカの主張

1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
0246デフォルトの名無しさん
垢版 |
2015/12/24(木) 14:54:05.30ID:QIUsopJK
>>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。
0247デフォルトの名無しさん
垢版 |
2015/12/24(木) 16:38:25.55ID:2ShnOfV/
>>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。
0248デフォルトの名無しさん
垢版 |
2015/12/24(木) 17:26:51.73ID:ri4CJahT
最初期は再帰をサポートしてなかった計算言語があるらしい
0249デフォルトの名無しさん
垢版 |
2015/12/24(木) 18:44:44.88ID:W/SZtGXt
今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。
0250デフォルトの名無しさん
垢版 |
2015/12/24(木) 20:04:26.21ID:aanAAc0G
計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。
0251デフォルトの名無しさん
垢版 |
2015/12/24(木) 20:37:54.33ID:Hny3MC9I
10000倍だっておとなしいぐらい。

再帰だと落ちまくるから∞倍だって当たり前だろ。
0252デフォルトの名無しさん
垢版 |
2015/12/24(木) 20:46:14.21ID:W/SZtGXt
メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。
0253デフォルトの名無しさん
垢版 |
2015/12/24(木) 20:58:31.47ID:2ShnOfV/
これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
0254デフォルトの名無しさん
垢版 |
2015/12/25(金) 18:57:10.38ID:IqCVGu/8
＞再帰もループも変わらんだろ。

なんで試してみないんだ？
再帰とループでクイックソート

ループ方式なら、データが何千万件あろうと無問題
0256uy ◆Qawu9.2l1E
垢版 |
2015/12/26(土) 05:53:41.97ID:QzXIU7/C
覚えたての知識を使ってレスバトルするだけのスレなんていらねーから
0258デフォルトの名無しさん
垢版 |
2015/12/26(土) 10:19:35.68ID:EXUTS9i+
そういう初心者の遊び場もあっていいと思うけどなあ
0259デフォルトの名無しさん
垢版 |
2015/12/26(土) 12:54:13.38ID:KD7gR2Cz
>>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。
0260デフォルトの名無しさん
垢版 |
2015/12/26(土) 13:36:54.41ID:oIXuKyHb
>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。
0261デフォルトの名無しさん
垢版 |
2015/12/26(土) 13:40:32.70ID:6n5NtJkM
>>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ！
0262sage
垢版 |
2015/12/26(土) 15:02:23.21ID:Igcba1qr
>>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。
0263デフォルトの名無しさん
垢版 |
2015/12/26(土) 16:45:09.37ID:YV12MLKo
>>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく，という発想はないのかね？
0264デフォルトの名無しさん
垢版 |
2015/12/26(土) 16:59:02.38ID:oIXuKyHb
>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？
0265デフォルトの名無しさん
垢版 |
2015/12/26(土) 17:27:47.02ID:Igcba1qr
>>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。
新着レスの表示
レスを投稿する

ニューススポーツなんでも実況