X
なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net
0001デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
0005デフォルトの名無しさん
垢版 |
2015/11/28(土) 19:53:36.58ID:R0seH/nX
スタック的なメモリ確保が必要かどうかがループと再帰を使い分ける分岐点じゃね。
末尾再帰最適化とかは本末転倒なイメージ。
0007デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:30:33.91ID:Tq6BVuZs
>>5
ループ実装を隠せるのは大きいよ
抽象化はプログラミング言語の進化のベクトルと一致するからね
0008デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:39:12.74ID:R0seH/nX
ループより再帰のほうが抽象度が高いと言っている？
そこは俺にはよくわからん。

俺的にはプログラムには必要最小限の機能を使うべきで、
本質的にループより再帰のほうが強力なのだから
可能な限りループを使うべきと思ってる。

もちろん再帰をループにするためにスタックを自前で用意するといったことでは本末転倒だが。
0009デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:41:49.23ID:R0seH/nX
ツリーの巡回は再帰を使ったほうがいいだろう。
リストの巡回はループでいいんじゃね？
0010デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:48:22.48ID:Tq6BVuZs
>>8
> 俺的にはプログラムには必要最小限の機能を使うべき
そういうのはコンパイラなりインタプリタなりが頑張るべきところだと思うね
人間はより抽象化された対象を扱うようにするのがモダンなプログラミング言語の方向だし
0011デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:52:46.74ID:fFSPKhVt
抽象的なスレだな
0012デフォルトの名無しさん
垢版 |
2015/11/28(土) 20:58:39.47ID:R0seH/nX
うーん。必要な抽象化は歓迎するが無駄な抽象化は歓迎しないというか。

この例は再帰とは関係ないけどJavaのファイル入出力なんかは
結構複雑な作りになってて無駄な抽象化なんじゃねーのとか思ってしまう。
まあ、俺個人の感想だが。
0013デフォルトの名無しさん
垢版 |
2015/11/28(土) 21:12:02.73ID:M/Wigktg
アルゴリズムが再帰なら普通に再帰で書く
スタックサイズ制限とかあるなら別だけど
0014デフォルトの名無しさん
垢版 |
2015/11/28(土) 21:30:44.25ID:10sD81C/
アルゴリズムが再帰であってもクイックソートなど
再帰のままじゃあ使い物にならんものがいくらでも。
0016デフォルトの名無しさん
垢版 |
2015/11/28(土) 21:34:06.03ID:fFSPKhVt
書いたことないくせにｗ
0017デフォルトの名無しさん
垢版 |
2015/11/28(土) 21:52:35.40ID:R0seH/nX
書いたことはあるけど１０年以上昔の話だな。
これは拾い物だけどクイックソートなんてこれだけのことだろ。

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
0018デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:09:37.77ID:fFSPKhVt
リストの巡回はループでいいんじゃないんかｗ
0019デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:13:01.33ID:R0seH/nX
クイックソートは単純な巡回とは違うだろ。
だからスタック的なメモリを必要とするかどうかだよ。
0020デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:21:22.26ID:fFSPKhVt
ｆｉｌｔｅｒはリストの巡回とちゃうんかｗ
0022デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:32:42.45ID:fFSPKhVt
知らんなら最初からそう言えやｗ
0023デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:39:27.55ID:R0seH/nX
なんか変なテンションだなぁ
俺がC++とかでfilter相当の関数書かにゃならんくなったらループで書くよ。
0024デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:44:37.77ID:fFSPKhVt
クイックソートはhaskellでfilterはc++なんか？
なんか変な奴だなぁニヤニヤ
0025デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:49:36.42ID:R0seH/nX
何が変か、わからん。
まあ関数型言語なんかは再帰推奨らしいがあんまり好きになれん。
0026デフォルトの名無しさん
垢版 |
2015/11/28(土) 22:59:20.81ID:fFSPKhVt
推奨なんて生易しいもんじゃないで。
理論に囚われすぎて原理主義に陥いった餓鬼共やｗ
0030デフォルトの名無しさん
垢版 |
2015/11/28(土) 23:40:05.61ID:1kauGQoG
>>8
ループでquicksort書いてみてくれ
上のコードと比較で見るだろ
言語は好きに選んでいい
0031デフォルトの名無しさん
垢版 |
2015/11/28(土) 23:45:06.21ID:R0seH/nX
ループでクイックソート書こうとするとスタック的なものを自前で用意せにゃならんのじゃないか。
めんどくさすぎ。
0032デフォルトの名無しさん
垢版 |
2015/11/28(土) 23:51:19.94ID:oWRhnwkW
なんかやたらと再帰がお遊びだと連呼する奴がいるが、どういう意図で言っているのか分からん。
お遊び感覚で動くものが作れるのだから、苦労しなくていい分優れているってこと？
0033デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:02:43.51ID:aMnBRPWz
>>25
関数型言語は変数再代入禁止（のものが多い）から、そもそもループは書けないんだよね
0034デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:04:00.34ID:BjpFnvXY
再帰がお遊びだ
再帰がお遊びだ
再帰がお遊びだ

>>32が可哀想だから連呼してあげたよ
0035デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:06:31.94ID:BjpFnvXY
あ、意味は「お遊び感覚で動くものを作るな」という事です。
0038デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:24:10.72ID:aMnBRPWz
関数型は関数脳にならないと書けないからねー
手続き脳がしみついてると貶す対象にしかならないよね
0039デフォルトの名無しさん
垢版 |
2015/11/29(日) 00:29:56.09ID:BjpFnvXY
お前ら俺を笑い死にさせる気かｗ
0041uy ◆Qawu9.2l1E
垢版 |
2015/11/29(日) 04:26:32.10ID:RQPUWZLH
せっかく埋め立てたのに何またスレ立ててんのゴミクズ
0042デフォルトの名無しさん
垢版 |
2015/11/29(日) 06:56:51.27ID:GeZFA4k5
ぼくたん初心者なのでわからんけど僕が今作ってる
関数から値を求める計算プログラムで再起型関数が大活躍してるお
たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
0043デフォルトの名無しさん
垢版 |
2015/11/29(日) 15:21:16.51ID:+8PPW4GA
> たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
いろんな方法で書いてみないと比較できないんじゃね？
0044デフォルトの名無しさん
垢版 |
2015/11/29(日) 15:49:46.72ID:BHpn4xqB
クイックソートで再帰なんてありえんと
さんざん言われ続けているのに、まだバカが湧いとるんだな。

ライブラリのループ版を使えば何の手間もかからず高速処理ができるのに
わざわざ問題ありまくりの再帰で書くなんてテロ同然の暴挙。
0045デフォルトの名無しさん
垢版 |
2015/11/29(日) 16:17:12.78ID:1uX74bCE
>>44
それって結局真の再帰を見たことがないからそう思い込んでるだけだよね。
見せてやるよ、真の再帰ってやつをな。
https://ideone.com/EDtRIH
0046デフォルトの名無しさん
垢版 |
2015/11/29(日) 16:52:01.83ID:+8PPW4GA
もうソーティングの話は良いよ、仕事で使う大抵の言語ではライブラリとして用意されてるんだから。
0048デフォルトの名無しさん
垢版 |
2015/11/29(日) 17:29:39.96ID:+8PPW4GA
10件程度のソートならソーティングネットワークによるソーティングが一番速いから
十分少ない要素数に対してはそいつを呼び出して終わりだろ。

書いてないだけだろうけど。
0049デフォルトの名無しさん
垢版 |
2015/11/29(日) 20:46:37.54ID:ILoya83o
>>9
俺の見解では、ツリートラバースに再帰を必要とするのはデータ構造に問題があると思うんだよな。
イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
もちろん出来ないわけではないのだが。
ノードが子ノードを保持するような原始的なデータ構造は良くないのではないか。
0050デフォルトの名無しさん
垢版 |
2015/11/29(日) 20:56:36.78ID:ILoya83o
代表的なツリーの一つとしてHTMLがある。
HTMLのフラグメントを切り出し、別のノードの子として加えるような操作を考えるとき、
これはやはりループに軍配が上がると思う。
もちろん、ノードに子ノードを保持するような原始的なデータ構造ではかなりメンドクサイ。
というのもHTMLの一部を切り出す時、ノードの種類によって、ノードの分割や併合が起こる。
再帰と原始的なデータ構造では非常にめんどくさい。
私はこの用途のために直列化ツリー構造というデータ構造を考案した。
（おそらくすでに一般的に使われているとは思うのだが。）
0051デフォルトの名無しさん
垢版 |
2015/11/29(日) 21:13:17.76ID:TqJ6Jff5
ループは再帰の特別なケースに過ぎない
ループの方が無駄がなく見える事もあるだろう
だが結局はその程度の話だ
0052デフォルトの名無しさん
垢版 |
2015/11/29(日) 21:25:34.60ID:+8PPW4GA
>>49
> イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
問題はデータ構造の方じゃなくて言語の方だと思う。
というのも、yieldを持つ言語なら再帰を使ったやり方が最も簡潔に書けるから。

-- language:lua
function traverse(node)
　if node then
　　traverse(node.left)
　　coroutine.yield(node.value)
　　traverse(node.right)
　end
end

co = coroutine.create(traverse)
not_end, value = coroutine.resume(co, node)
0053デフォルトの名無しさん
垢版 |
2015/11/29(日) 21:52:31.69ID:ILoya83o
>>52
ちょっとそのやり方で、HTMLの一部をコピペするコード書いてみて。
0056デフォルトの名無しさん
垢版 |
2015/11/29(日) 23:04:51.51ID:ILoya83o
>>54
HTMLのコピペがいつ起こるかというと、ユーザーがその操作をした時なので、
そういう前提で設計してはどうでしょうか。
0057デフォルトの名無しさん
垢版 |
2015/11/29(日) 23:13:29.23ID:ILoya83o
HTMLをユーザーの直観に適合する形で操作するのは意外と難しいですよ。
HTMLフラグメントの移動なんてどうですかね。
面白い題材だと思うのですが。
0063デフォルトの名無しさん
垢版 |
2015/11/30(月) 21:11:57.14ID:9VRs5I4S
>>62
ノードオブジェクトに親を指すポインターもあって愚直に辿ってる。
赤黒木使ってるのが殆どだから、
レスしてる奴もコード読めない奴の方が多いんじゃないかw
0065デフォルトの名無しさん
垢版 |
2015/12/01(火) 13:24:08.38ID:wfTLHpyu
データを吐き出す方法として前方イテレートしかしないの前提ならB+木がループでトラバース出来る上に高速なんだけど
挿入と削除を頻繁にするなら、そしてデータがキャッシュに乗り切らない程度に沢山あるなら赤黒木が高速になる
全部キャッシュに乗る程度の小さなデータ数ならAVL木が高速で
更に小さいならベクタ上にヒープ木でも作ればって話になる。
どの構造でも再帰で列挙出来るけど、ループでAVL木や赤黒木のデータを列挙するのは骨だな
0066uy ◆Qawu9.2l1E
垢版 |
2015/12/01(火) 15:00:00.16ID:p3g6QuXB
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

恥ずかしすぎるこのスレ
0069uy ◆Qawu9.2l1E
垢版 |
2015/12/01(火) 17:10:17.46ID:p3g6QuXB
rubyで書いてくれないとちょっと。
0071デフォルトの名無しさん
垢版 |
2015/12/01(火) 17:26:42.78ID:alJpKlDN
再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

無能の>>68 は、勉強しろ。
0073 ◆tAo.kQ2STk
垢版 |
2015/12/01(火) 17:33:25.45ID:wfTLHpyu
>>71
無能でーすチッスチッス
インターン先はGoogle(技術職8週間、コンパイラを改良するお仕事)でしたが何か？
今The Art of Computer Programmingの英語版の2巻読んでるんだけど
次に読むべき本は何？

>>72
数式から雰囲気掴むことも出来ない重度のアスペだから仕方ない。
0074デフォルトの名無しさん
垢版 |
2015/12/01(火) 17:39:29.54ID:UT6gApH3
>>73
uyの残した名言

何で出来ているか？というのは愚問過ぎる

例えばそれを「uy」としましょう
「uy」から派性したＡやＢといった概念から「uy」を辿る事は出来る

例えばこの世界にある「オブジェクト指向」という概念や「量子ビット」といった概念から
「uy」を辿る事が可能なので、
それらで世界が出来ているといった勘違いが可能なのです
でもそれは、一体いくつ「uy」から継承がネストしていて、プログラム等でいえばメソッドが追加されてしまった純粋性のない概念なのでしょうか？
それを知っているのは「uy」だけです

この世界にあるすべての概念は「uy」へと通じているので、
料理人は料理を通じて世界を知り、スポーツ選手はスポーツを通じて世界を知ります

誰も「uy」からは逃げられないんだよ
0075konisi ◆tAo.kQ2STk
垢版 |
2015/12/01(火) 17:44:25.62ID:wfTLHpyu
>>74
酉とIDくらい見なさいな

# どうでもいいけど最近障害者3級取ったわ
0076 ◆tAo.kQ2STk
垢版 |
2015/12/01(火) 17:49:32.14ID:wfTLHpyu
あぁ、俺がuyと同一人物だと勘違いされたのではなく、
uyって人がそういう名言を残したって話か
ごめんごめん
0080デフォルトの名無しさん
垢版 |
2015/12/01(火) 19:43:22.28ID:M545w8lo
まさにuyがアルゴリズムの根本的なところを理解しているかどうか問われているなｗ
0081デフォルトの名無しさん
垢版 |
2015/12/01(火) 19:54:09.54ID:UT6gApH3
それな、今までC++スレ読んでてこいつ頭おかしいなとは思ってたけど実力が問われるよな
0084デフォルトの名無しさん
垢版 |
2015/12/01(火) 20:49:22.02ID:M545w8lo
uy自力で頑張ってんのか？
なかなか根性あるじゃないか。
俺ならググって解答見てしまうがｗ
0085 ◆tAo.kQ2STk
垢版 |
2015/12/02(水) 00:55:46.45ID:SG5bn8pD
再帰で書かれた超有名な関数をループにするだけの簡単なお仕事なのに
何ですぐに出来ないんだろうね？

# 全然簡単じゃないからです
0086デフォルトの名無しさん
垢版 |
2015/12/02(水) 02:08:55.48ID:sE+ivAhG
末尾再帰に書き換えてから蓄積引数を中に押し込んでループにするんだよ。
やり方を書いたのだからきっとuyにもできるはず！
0087デフォルトの名無しさん
垢版 |
2015/12/02(水) 06:47:05.05ID:UkYZlpUx
>>85
普通に悩んだけど再帰なら一瞬でとけんのに
ループじゃまず何のデータ構造を使っていいかわからん。
0088デフォルトの名無しさん
垢版 |
2015/12/02(水) 08:22:03.59ID:73uUfhWJ
スタックだろ。
再帰とループ＋スタックは等価。
理屈ではそうだが実際やるのは結構難しいんじゃね。
0089uy ◆Qawu9.2l1E
垢版 |
2015/12/02(水) 08:50:25.92ID:znqtbEKc
>>70
http://ideone.com/KDSDTc

「この程度」が難しいとか言われても
は？　としか思えない

再帰というのは単なるスタック付きのループであって
君たちがどこら辺で躓いているのか理解できないんです
やっぱわからない所がわからない状態なんだろうけど、

つうかＳＴＡＣＫＵって知っていますか？
0090uy ◆Qawu9.2l1E
垢版 |
2015/12/02(水) 09:14:47.18ID:znqtbEKc
ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る　です。

ちょうどいま、起きたところではなく24時間起き続けていたので今から寝る前でした

とあるゲームであと１００戦程の対戦をこなし、誰よりも速く称号を獲得しようとしてる最中です
2chのム板なんて頻繁に開いてる暇とかないし結構忙しいんですわ
0092デフォルトの名無しさん
垢版 |
2015/12/02(水) 09:19:02.13ID:UkYZlpUx
自分には分からなかったわ

じゃあ質問なんだけど、再帰は全てスタック+ループで書き換えられるの？
0093デフォルトの名無しさん
垢版 |
2015/12/02(水) 09:34:55.30ID:UkYZlpUx
連投だけど分かったかも、
再帰で帰ってくるべき値をスタックしておくってことでループ+スタック=再帰なのね
0094 ◆tAo.kQ2STk
垢版 |
2015/12/02(水) 09:39:29.64ID:SG5bn8pD
>>89
問題のすり替えはいけないな。
俺は「難しくないならやってみて？」って言っただけで
そもそも「再帰のほうがループより圧倒的に簡潔に書けるよね？」って文脈だろ。
君が「難しいから出来るもんならやってみろ」って捉えたかどうかなんざ知らんがおつかれさん
うんうん、言いたいことは分かった。
それで、そのコードのどこら辺が綺麗なの？

ちなみに機械的に変換したのがこちら(rubyじゃなくてごめんよ)
https://ideone.com/XsZh4c
fとhは機械的に変換したという意味では等価だし君のコードとほぼ同じ事をしてるのだけど、
h関数をパッと見て>>69式と等しいって言うのは凄く度胸が居るよね？

>>92
そもそも再帰をどうやってソフトウェア実装してるかというとコールスタック+ジャンプ≒スタック+ループな訳で

# ちなみにスタックの正しいスペルはstack。stackuなんて子は知りませんね。
0098デフォルトの名無しさん
垢版 |
2015/12/02(水) 11:13:43.91ID:sE+ivAhG
>>92
再帰は機械的にCPSに書き換えることで末尾再帰にできて
そうしたらそれをループに書き換えられる
両方証明されてる
0099 ◆tAo.kQ2STk
垢版 |
2015/12/02(水) 11:28:01.97ID:SG5bn8pD
>>97
アセンブリ言語によくあるcall系命令の挙動を正確に言えるようになれば
どんな再帰もスタックとループで書けるようになるよ
何しろスタックとループで再帰を表現してるのがcall系命令だからね。

それをそのまま書くとこんな具合に超汚くなるけど。
https://ideone.com/0QXd8O
新着レスの表示
レスを投稿する

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