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

**デフォルトの名無しさん** · 2015/11/28(土) 18:51:38.86

なあ、再帰関数好きな人いる？

**デフォルトの名無しさん** · 2015/11/29(日) 17:09:26.93

>>45
再帰じゃあ、１０件程度のソートに控えるという事なんだよな。

**デフォルトの名無しさん** · 2015/11/29(日) 17:29:39.96

10件程度のソートならソーティングネットワークによるソーティングが一番速いから
十分少ない要素数に対してはそいつを呼び出して終わりだろ。

書いてないだけだろうけど。

**デフォルトの名無しさん** · 2015/11/29(日) 20:46:37.54

>>9
俺の見解では、ツリートラバースに再帰を必要とするのはデータ構造に問題があると思うんだよな。
イテレータの実装を考えると再帰はちょっと無理があるんじゃないかと思う。
もちろん出来ないわけではないのだが。
ノードが子ノードを保持するような原始的なデータ構造は良くないのではないか。

**デフォルトの名無しさん** · 2015/11/29(日) 20:56:36.78

代表的なツリーの一つとしてHTMLがある。
HTMLのフラグメントを切り出し、別のノードの子として加えるような操作を考えるとき、
これはやはりループに軍配が上がると思う。
もちろん、ノードに子ノードを保持するような原始的なデータ構造ではかなりメンドクサイ。
というのもHTMLの一部を切り出す時、ノードの種類によって、ノードの分割や併合が起こる。
再帰と原始的なデータ構造では非常にめんどくさい。
私はこの用途のために直列化ツリー構造というデータ構造を考案した。
（おそらくすでに一般的に使われているとは思うのだが。）

**デフォルトの名無しさん** · 2015/11/29(日) 21:13:17.76

ループは再帰の特別なケースに過ぎない
ループの方が無駄がなく見える事もあるだろう
だが結局はその程度の話だ

**デフォルトの名無しさん** · 2015/11/29(日) 21:25:34.60

>>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)

**デフォルトの名無しさん** · 2015/11/29(日) 21:52:31.69

>>52
ちょっとそのやり方で、HTMLの一部をコピペするコード書いてみて。

**デフォルトの名無しさん** · 2015/11/29(日) 22:12:36.39

>>53
一部ってのはどういう風に探すのん？
特定の属性を持ってるタグを探す感じ？

**デフォルトの名無しさん** · 2015/11/29(日) 22:23:46.56

どういう風に探すか後から指定できる感じで。

**デフォルトの名無しさん** · 2015/11/29(日) 23:04:51.51

>>54
HTMLのコピペがいつ起こるかというと、ユーザーがその操作をした時なので、
そういう前提で設計してはどうでしょうか。

**デフォルトの名無しさん** · 2015/11/29(日) 23:13:29.23

HTMLをユーザーの直観に適合する形で操作するのは意外と難しいですよ。
HTMLフラグメントの移動なんてどうですかね。
面白い題材だと思うのですが。

**デフォルトの名無しさん** · 2015/11/29(日) 23:27:31.14

直列化ツリー構造kwsk

**デフォルトの名無しさん** · 2015/11/30(月) 00:13:02.74

>>53
書いてはみたけどウェブプログラミング初心者でごめんよ
https://ideone.com/KO4rFy

**デフォルトの名無しさん** · 2015/11/30(月) 11:10:04.73

>>59 乙

**デフォルトの名無しさん** · 2015/11/30(月) 14:51:10.36

>>52>>53を繰り返しで書ける人はいないみたいだね。

**デフォルトの名無しさん** · 2015/11/30(月) 20:27:21.92

そういやC++のstd::mapのイテレータとかってどうなってんるのん？

**デフォルトの名無しさん** · 2015/11/30(月) 21:11:57.14

>>62
ノードオブジェクトに親を指すポインターもあって愚直に辿ってる。
赤黒木使ってるのが殆どだから、
レスしてる奴もコード読めない奴の方が多いんじゃないかw

**デフォルトの名無しさん** · 2015/12/01(火) 00:02:40.17

赤黒木って難しいよね、結構。

**デフォルトの名無しさん** · 2015/12/01(火) 13:24:08.38

データを吐き出す方法として前方イテレートしかしないの前提ならB+木がループでトラバース出来る上に高速なんだけど
挿入と削除を頻繁にするなら、そしてデータがキャッシュに乗り切らない程度に沢山あるなら赤黒木が高速になる
全部キャッシュに乗る程度の小さなデータ数ならAVL木が高速で
更に小さいならベクタ上にヒープ木でも作ればって話になる。
どの構造でも再帰で列挙出来るけど、ループでAVL木や赤黒木のデータを列挙するのは骨だな

uy ◆Qawu9.2l1E · 2015/12/01(火) 15:00:00.16

再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

恥ずかしすぎるこのスレ

**デフォルトの名無しさん** · 2015/12/01(火) 16:04:55.52

f(0,b)=b+1
f(a,0)=f(a-1,1)
f(a,b)=f(a-1,f(a,b-1))

**デフォルトの名無しさん** · 2015/12/01(火) 16:39:12.55

>>66
>>67をループに変換するのは難しくないんだね？
ちょっとやってみせてよ。

uy ◆Qawu9.2l1E · 2015/12/01(火) 17:10:17.46

rubyで書いてくれないとちょっと。

**デフォルトの名無しさん** · 2015/12/01(火) 17:22:48.32

>>69
rubyで書いたぞ
http://ideone.com/B1bDnp

**デフォルトの名無しさん** · 2015/12/01(火) 17:26:42.78

再帰・ループの相互変換が難しいとかさあ
アルゴリズムの根本的なところ理解してないだけ

無能の>>68 は、勉強しろ。

**デフォルトの名無しさん** · 2015/12/01(火) 17:26:51.00

uyって式も読めないのかな

◆tAo.kQ2STk · 2015/12/01(火) 17:33:25.45

>>71
無能でーすチッスチッス
インターン先はGoogle(技術職8週間、コンパイラを改良するお仕事)でしたが何か？
今The Art of Computer Programmingの英語版の2巻読んでるんだけど
次に読むべき本は何？

>>72
数式から雰囲気掴むことも出来ない重度のアスペだから仕方ない。

**デフォルトの名無しさん** · 2015/12/01(火) 17:39:29.54

>>73
uyの残した名言

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

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

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

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

誰も「uy」からは逃げられないんだよ

**konisi** ◆tAo.kQ2STk · 2015/12/01(火) 17:44:25.62

>>74
酉とIDくらい見なさいな

# どうでもいいけど最近障害者3級取ったわ

◆tAo.kQ2STk · 2015/12/01(火) 17:49:32.14

あぁ、俺がuyと同一人物だと勘違いされたのではなく、
uyって人がそういう名言を残したって話か
ごめんごめん

**デフォルトの名無しさん** · 2015/12/01(火) 18:38:14.45

誰も uy なんかに価値を求めてないのにね

**デフォルトの名無しさん** · 2015/12/01(火) 18:56:25.56

でかでかと引用した奴が言うと説得力があるね。

**デフォルトの名無しさん** · 2015/12/01(火) 19:16:25.46

んでuyちゃんのループ問題はまだ解決しないのかしら

**デフォルトの名無しさん** · 2015/12/01(火) 19:43:22.28

まさにuyがアルゴリズムの根本的なところを理解しているかどうか問われているなｗ

**デフォルトの名無しさん** · 2015/12/01(火) 19:54:09.54

それな、今までC++スレ読んでてこいつ頭おかしいなとは思ってたけど実力が問われるよな

**デフォルトの名無しさん** · 2015/12/01(火) 19:58:37.14

はてさてuyの実力は如何。

# 俺自身の実力はさておき。

**デフォルトの名無しさん** · 2015/12/01(火) 20:19:08.98

おせぇな uy

**デフォルトの名無しさん** · 2015/12/01(火) 20:49:22.02

uy自力で頑張ってんのか？
なかなか根性あるじゃないか。
俺ならググって解答見てしまうがｗ

◆tAo.kQ2STk · 2015/12/02(水) 00:55:46.45

再帰で書かれた超有名な関数をループにするだけの簡単なお仕事なのに
何ですぐに出来ないんだろうね？

# 全然簡単じゃないからです

**デフォルトの名無しさん** · 2015/12/02(水) 02:08:55.48

末尾再帰に書き換えてから蓄積引数を中に押し込んでループにするんだよ。
やり方を書いたのだからきっとuyにもできるはず！

**デフォルトの名無しさん** · 2015/12/02(水) 06:47:05.05

>>85
普通に悩んだけど再帰なら一瞬でとけんのに
ループじゃまず何のデータ構造を使っていいかわからん。

**デフォルトの名無しさん** · 2015/12/02(水) 08:22:03.59

スタックだろ。
再帰とループ＋スタックは等価。
理屈ではそうだが実際やるのは結構難しいんじゃね。

uy ◆Qawu9.2l1E · 2015/12/02(水) 08:50:25.92

>>70
http://ideone.com/KDSDTc

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

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

つうかＳＴＡＣＫＵって知っていますか？

uy ◆Qawu9.2l1E · 2015/12/02(水) 09:14:47.18

ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る　です。

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

とあるゲームであと１００戦程の対戦をこなし、誰よりも速く称号を獲得しようとしてる最中です
2chのム板なんて頻繁に開いてる暇とかないし結構忙しいんですわ

**デフォルトの名無しさん** · 2015/12/02(水) 09:18:01.80

>>89
お見事です。申し訳ありませんでした。

**デフォルトの名無しさん** · 2015/12/02(水) 09:19:02.13

自分には分からなかったわ

じゃあ質問なんだけど、再帰は全てスタック+ループで書き換えられるの？

**デフォルトの名無しさん** · 2015/12/02(水) 09:34:55.30

連投だけど分かったかも、
再帰で帰ってくるべき値をスタックしておくってことでループ+スタック=再帰なのね

◆tAo.kQ2STk · 2015/12/02(水) 09:39:29.64

>>89
問題のすり替えはいけないな。
俺は「難しくないならやってみて？」って言っただけで
そもそも「再帰のほうがループより圧倒的に簡潔に書けるよね？」って文脈だろ。
君が「難しいから出来るもんならやってみろ」って捉えたかどうかなんざ知らんがおつかれさん
うんうん、言いたいことは分かった。
それで、そのコードのどこら辺が綺麗なの？

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

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

# ちなみにスタックの正しいスペルはstack。stackuなんて子は知りませんね。

◆tAo.kQ2STk · 2015/12/02(水) 09:48:27.56

s/69/67/

**デフォルトの名無しさん** · 2015/12/02(水) 10:13:14.24

>>92
数学的に証明されてる。

**デフォルトの名無しさん** · 2015/12/02(水) 10:15:05.34

>>96
そうなのか、、、
ならできるようにならなきゃだな

**デフォルトの名無しさん** · 2015/12/02(水) 11:13:43.91

>>92
再帰は機械的にCPSに書き換えることで末尾再帰にできて
そうしたらそれをループに書き換えられる
両方証明されてる

◆tAo.kQ2STk · 2015/12/02(水) 11:28:01.97

>>97
アセンブリ言語によくあるcall系命令の挙動を正確に言えるようになれば
どんな再帰もスタックとループで書けるようになるよ
何しろスタックとループで再帰を表現してるのがcall系命令だからね。

それをそのまま書くとこんな具合に超汚くなるけど。
https://ideone.com/0QXd8O

**デフォルトの名無しさん** · 2015/12/02(水) 12:52:27.49

ありがとうございます

**デフォルトの名無しさん** · 2015/12/02(水) 18:34:40.93

uyなかなかやるな。
ググって解答見た可能性もあるが、ググれるのも実力のうちだからな。

**.パンティーガァル** · 2015/12/02(水) 20:57:19.51

>>90
> ちなみにここ一週間のuyの生活は、朝起きて、ネトゲして朝寝る　です。
悲観することはない（してないかもしれないがｗ）
それも一つの生き方だ
人間の人生などそんなものだ

**デフォルトの名無しさん** · 2015/12/02(水) 22:54:08.11

https://ideone.com/upRuBk
アッカーマン関数の展開の様子を書いてみた。
メモリリークあるけど気にしない。
もっとスマートにかけそうな気もするが言語が悪いのかな？

**デフォルトの名無しさん** · 2015/12/03(木) 13:20:12.94

誰かループ版と再帰版でベンチマークしてみなよ

◆tAo.kQ2STk · 2015/12/03(木) 13:56:10.07

>>103
俺も書いてみたけど
確かにどう書いてももうちょっとスマートに書ける気がする。
https://ideone.com/BFP2wh

**デフォルトの名無しさん** · 2015/12/03(木) 17:06:18.36

>>105
メンドクサイやつだなお前ｗ

**デフォルトの名無しさん** · 2015/12/03(木) 17:30:30.61

>>104
ack(3,10)を100回計算させたところ

ループ 3.99秒
再帰 4.50秒

だった。微妙にループが速い。
言語はg++ 最適化あり

◆tAo.kQ2STk · 2015/12/03(木) 17:54:16.46

>>106
でも115行目以降は>>103に比べてスマートじゃない？
アッカーマン関数をより素直に表現している(ように見える)というか。

テンプレートその他がひじょーに面倒臭い事になってるのは認めるよｗｗ

**デフォルトの名無しさん** · 2015/12/03(木) 18:28:15.45

>>108
まあそうかも。
言語によってはめちゃくちゃ簡潔に書けたりするのかな、気になる。

◆tAo.kQ2STk · 2015/12/03(木) 19:58:47.04

>>109
ちなみに扱ってるのがアッカーマン関数だけだということとか考慮しつつ短く書くとこうなる。
https://ideone.com/ILFKf2

**デフォルトの名無しさん** · 2015/12/03(木) 20:19:17.43

>>110
だいぶスッキリした。
でも入れ子構造がなくなっちゃってるのはちょっと寂しいかな。

**デフォルトの名無しさん** · 2015/12/03(木) 22:49:14.77

https://ideone.com/hlWWly
んんん、haskell　気持ちいい！

**デフォルトの名無しさん** · 2015/12/04(金) 18:59:19.58

きっしょ

**デフォルトの名無しさん** · 2015/12/04(金) 20:33:45.20

んぎもちいいいいいいいいいい

**デフォルトの名無しさん** · 2015/12/05(土) 12:06:08.66

気持ち悪い生き物だなこいつは

**デフォルトの名無しさん** · 2015/12/05(土) 12:08:54.94

再起関数難しくて苦手だわ

**デフォルトの名無しさん** · 2015/12/05(土) 12:38:44.60

おいらも苦手だわ

**デフォルトの名無しさん** · 2015/12/05(土) 12:50:09.98

アッカーマンを知ったばかりで嬉しくてしょうがないんだろうな
俺くらいになるとどうでもよくなるけど

**デフォルトの名無しさん** · 2015/12/05(土) 14:22:16.61

さぁ次は竹内関数(たらい回し関数)だ！

**デフォルトの名無しさん** · 2015/12/05(土) 14:24:24.30

>>118
アッカーマン関数が原始帰納関数でない証明を頼む。
定義がシンプルかつ一般帰納関数になるように
アッカーマンさんが構成したらしいが。

**デフォルトの名無しさん** · 2015/12/05(土) 16:27:08.57

その問題が解けて嬉しかったんだろうな

**デフォルトの名無しさん** · 2015/12/05(土) 22:53:23.45

たらいのループ化と展開の様子誰か頼む

**デフォルトの名無しさん** · 2015/12/07(月) 01:05:16.16

なんで自分でやらない？

再帰関数が好きなんだろ？

**ネトuy** ◆Qawu9.2l1E · 2015/12/07(月) 02:12:06.27

ｗ

**デフォルトの名無しさん** · 2015/12/07(月) 19:27:26.73

https://ideone.com/63bZSE

たらいの展開の様子

haskell気持ちEー！

ループ化は誰か頼むわ

**デフォルトの名無しさん** · 2015/12/08(火) 10:04:03.24

きも

**デフォルトの名無しさん** · 2015/12/10(木) 22:01:50.93

たらいのループ化どうやるかわからん。

**デフォルトの名無しさん** · 2015/12/10(木) 23:27:19.50

んーなんかプログラムカウンタに相当するものをスタックに積まなきゃいけない感じ？

**デフォルトの名無しさん** · 2015/12/11(金) 02:06:03.72

https://ideone.com/rO18tw
んーできたっぽい？
コンパイラの吐いたアセンブラとか見ながら書いたからチートしてるけど。

**デフォルトの名無しさん** · 2015/12/11(金) 13:42:03.51

再帰厨はcall命令とjmp命令の違いが分かってから布教してほしい

**デフォルトの名無しさん** · 2015/12/11(金) 18:14:40.60

>>130
何言ってるんだ。。
ループで書けば早い、自分でスタック作れば、って言ってるループキチガイに、
命令にもこういうのがあるよ、必要だからあるんだよ。
と教えてあげてはどうだ？

**デフォルトの名無しさん** · 2015/12/11(金) 18:27:07.72

＞命令にもこういうのがあるよ、必要だからあるんだよ。

だからどうしたとしか。
基地外宗教を布教するなら、自分でするんだね。

**デフォルトの名無しさん** · 2015/12/11(金) 19:01:03.96

callとjumpの中間の命令もあるよな。
call使わない奴はいないのか?

**デフォルトの名無しさん** · 2015/12/11(金) 19:02:56.29

中間の命令ってなんだよ？

**デフォルトの名無しさん** · 2015/12/11(金) 19:40:32.13

>>134
MIPSのjalとjrとか。
callとretに相当。
jal相当すらなくてpcのレジスタ保存命令しかないのもあった。

**デフォルトの名無しさん** · 2015/12/13(日) 22:44:03.31

ツリーのイテレータってどう書くの
誰か頼む

uy ◆Qawu9.2l1E · 2015/12/14(月) 05:58:59.61

まずはこの手のアルゴリズム抽象化でC++使うのをやめろ
効率悪すぎ

uy ◆Qawu9.2l1E · 2015/12/14(月) 06:02:04.72

ツリーのイテレータっつうか
ゲームプログラミング的にいえばツリー構造のタスクシステム
ゲームプログラミングしてれば普通に書いてるような低レベルの話

◆tAo.kQ2STk · 2015/12/14(月) 11:28:00.80

>>136
ツリーのイテレータの書き方は大きく分けて3種類ある。
一つ目はイテレータ自身に「どのノードを辿ってきたか」って情報を覚えさせておいてそれを用いる方法
イテレータの空間効率がO(log n)になる代わりにサクセッサの時間効率が平均でO(1)になる。
二つ目はイテレータ自身にキーを覚えさせておいて、一旦そのキーを手繰ってから次のノードを手繰り直す方法
イテレータの空間効率がO(1)になる代わりにサクセッサの時間効率がO(log n)になる。
三つ目は木構造の各葉っぱに次の葉っぱへのポインタを書いておく方法
イテレータの空間効率がO(1)、サクセッサの時間効率がO(1)になる代わりに葉要素のサイズがO(1)増える。

**名無しさん＠そうだ選挙に行こう** · 2015/12/14(月) 11:57:14.44

イテレータってそんなにたくさん使うもんじゃないし、一つ目がいいかな、俺的に。

uy ◆Qawu9.2l1E · 2015/12/14(月) 15:02:59.78

それ種類じゃなくて、全部組み合わせて実装したほうが汎用的じゃねーの

class A
attr_accessor :up , :key , :list , :data
end

最低でも１と３のup listは無ければ木構造にならないだろ
君の考えは prev(up) と next(list) になってる

**名無しさん＠そうだ選挙に行こう** · 2015/12/14(月) 16:34:38.86

全部組み合わせたほうが汎用的？
何を言ってるかよくわからん

uy ◆Qawu9.2l1E · 2015/12/14(月) 21:12:22.29

まず、ツリーにしたらそれはイテレータとは呼ばないから
ただのツリーを走査する為の関数に過ぎない

「イテレータ」にしか使用できないツリーじゃなくて
一通りの事に使用できるツリークラス作れば？って話

**デフォルトの名無しさん** · 2015/12/14(月) 21:30:28.83

**デフォルトの名無しさん** · 2015/12/14(月) 22:23:44.30

uyのイテレータの定義がさっぱりわからん。
俺はC++STLのイテレータを想像しているんだが。
uyの言ってるイテレータはなんのイテレータなんだ？

**デフォルトの名無しさん** · 2015/12/14(月) 23:47:42.33

uyが言ってるのはツリーで実装されたイテレータということかな？
俺が言いたいのはツリーを巡回するイテレータなんだが？

**デフォルトの名無しさん** · 2015/12/15(火) 02:12:24.45

コレクションを操作するのがイタレータ

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

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