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

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

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

**デフォルトの名無しさん** · 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

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

uy ◆Qawu9.2l1E · 2015/12/15(火) 02:28:13.41

センスないと無理

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

>>147
それを言うなら走査だろと自分で突っ込んどく

uy ◆Qawu9.2l1E · 2015/12/15(火) 02:44:41.16

例えば
[1,2,3,4]　←　これをイテレートするのがイテレータだろ？

ツリーは
[1,2,[3,4,[5,6]]]　←　これをイテレートしたいのが作りたいイテレータだろ？

下のはイテレータと表現するまでもなくプログラム中でツリー構造が必要になって、
「ツリークラス」ってのを定義した事あれば、そんなのは標準実装しているレベルのものだから、わざわざツリーのイテレータなんていう半端なものは誰も作らない

作る順序的にまずはイテレータのツリー化じゃなくて、ツリークラスの定義
考えが追いつかないなら好きな順序で作れば良いけど

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

ツリーオブジェクトにtoArray()メソッドを用意すれば
すべて解決すると思うの。

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

大富豪プログラミングだなtoArray()
ツリーなんかはサイズが非常にデカくなることがしばしばあるぞ。

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

tAo.kQ2STk　ってテレンスタオから取ってんの？

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

>>150
汎用的なツリークラス作れって言ってんのか？
javascriptみたいになるんじゃね？

◆tAo.kQ2STk · 2015/12/15(火) 19:28:58.56

>>153
違うよ。人間が読める某文字列をキーにしたらその酉が作れる。

ところでさ、どうでも良いんだけど
今話題にしてるのは木構造
>>141が示したデータ構造は無向グラフ
・・・・・・だよね？

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

ツリーじゃね

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

参照が木構造になってるかグラフになってるかなんて実行時に決まることじゃないのか？

**デフォルトの名無しさん** · 2015/12/16(水) 03:41:52.77

何だこの池沼ｗ

**デフォルトの名無しさん** · 2015/12/16(水) 09:38:17.31

ごめん

**デフォルトの名無しさん** · 2015/12/16(水) 21:37:56.27

いいってことよ

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

Elixir再帰おもろい
http://confreaks.tv/videos/elixirconf2014-introduction-to-elixir-for-rubyists

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

プログラマはMacを使ってるってマジ？
http://hayabusa3.2ch.net/test/read.cgi/news/1450395043/

**デフォルトの名無しさん** · 2015/12/19(土) 15:12:57.98

メモメモ
http://izumi-math.jp/M_Harada/kinou_o/kinou_o.pdf
http://examist.jp/mathematics/recurrence-formula/suitei/
http://mathtrain.jp/fibonacci

**デフォルトの名無しさん** · 2015/12/19(土) 16:17:36.19

制御では、実行時間が読めないアルゴリズムは使いにくい。

**デフォルトの名無しさん** · 2015/12/19(土) 16:48:17.67

再帰と繰り返しは相互に変換可能なんだから、再帰で実行時間が読めないならば、繰り返しでも読めない。
こんなじょうしきも知らないの?

**デフォルトの名無しさん** · 2015/12/19(土) 20:02:11.53

ごめん

**デフォルトの名無しさん** · 2015/12/19(土) 20:16:05.69

再帰はシステムダウンの危険がある。
処理速度もはるかに遅くなる。

再帰の場合には、こうした実行時間が読めない特有の問題点がある。

**デフォルトの名無しさん** · 2015/12/19(土) 22:02:48.92

> 再帰はシステムダウンの危険がある。
そう言う環境ならば、システムダウンの可能性は繰り返しでもある。

> 処理速度もはるかに遅くなる。
ヘボが作った繰り返しは再帰よりはるかに遅い。

**デフォルトの名無しさん** · 2015/12/19(土) 22:20:57.65

>>168
繰り返しと再帰はいっしょなんだろ？

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

>>169
お前、バカなんだろ。

**デフォルトの名無しさん** · 2015/12/19(土) 23:26:42.72

末尾再帰に対応した言語が少ないからなぁ

**デフォルトの名無しさん** · 2015/12/19(土) 23:29:13.06

普通の言語は対応してる
変な言語は使うもんじゃない

uy ◆Qawu9.2l1E · 2015/12/20(日) 01:30:16.73

# 1
def f
　if 条件
　　処理
　else
　　f()
　end
end

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

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

末尾再帰されるパターンわからない奴ｗｗｗｗｗｗｗｗｗｗｗｗっうぃる？　

**デフォルトの名無しさん** · 2015/12/20(日) 01:48:28.93

>>172
Java「…」

**デフォルトの名無しさん** · 2015/12/20(日) 12:14:12.80

>>175
漸化式

**デフォルトの名無しさん** · 2015/12/20(日) 12:15:13.29

それは、無限再帰

**デフォルトの名無しさん** · 2015/12/20(日) 14:49:43.30

ID:EjHtX5K0のような白痴ばかりだから
再帰厨だと馬鹿にされることになる。

再帰を愛して使うんだったら、
ループ版にはない深刻なデメリットがある事ぐらいちゃんと注意した上で、
効率や安全性を無視したプログラミングを楽しむべき。

**デフォルトの名無しさん** · 2015/12/20(日) 17:18:50.85

繰り返しの唯一の利点は回数の制御が再帰よりも容易であること。
これ以外の利点はない。

バカにはそれが理解できないらしいが。

**デフォルトの名無しさん** · 2015/12/20(日) 17:26:49.52

馬鹿には出来ませんね

**デフォルトの名無しさん** · 2015/12/20(日) 18:23:24.49

ごめん

**デフォルトの名無しさん** · 2015/12/20(日) 19:26:33.84

再帰はID:zNzoBoA2のように低知能には理解不能という弱点があるけど
ID:zNzoBoA2のような低知能の出現率は低いので全然問題無い
むしろ低知能者を検出試験としてのメリットの方が大きい

**デフォルトの名無しさん** · 2015/12/20(日) 22:01:31.82

再帰苦手だから何でもかんでもループ使ってすまん

**デフォルトの名無しさん** · 2015/12/20(日) 22:05:01.79

flattenとか難しいよね

**デフォルトの名無しさん** · 2015/12/20(日) 22:51:10.83

もし再帰が理解出来たつもりなら、ちゃんとループに直せるぐらいのプログラミング技術は備えなくちゃ。

最低でもそれくらいの技術や知能が無ければ
再帰を楽しむことはできないよ。

**デフォルトの名無しさん** · 2015/12/21(月) 02:17:48.47

「再帰には深刻なデメリットがある」キリッ
なんて発言する低知能人は再帰を理解してるはずが無い、理解不能なものを怖れている。未開人と同じ。

**デフォルトの名無しさん** · 2015/12/21(月) 09:54:25.69

ループを恐れるのは、ループにするだけの知識・経験を欠いているから。

その程度じゃあプログラミングの世界からすぐに消えるだけの存在。
再帰厨は、現実で満たされないのでスレで妄想を垂れ流すことしかできないクズ。

**デフォルトの名無しさん** · 2015/12/21(月) 10:52:48.60

関数内にjmpも好き勝手にやるタイプだからどうとも言わんけど、
再帰否定派はまさか単一のアーキテクチャの話してないよな？
アルゴリズムとして再帰がイケてないって話だよな？

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

そうなのか？

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

>>186
必死で再帰を否定しているバカを弄っているだけで、繰り返しを否定しているわけでは無い

やっぱり低知能なんだな。

**デフォルトの名無しさん** · 2015/12/21(月) 18:43:17.30

みなさん、これが「弄ってるって言いたいバカ」ですｗ

**デフォルトの名無しさん** · 2015/12/22(火) 08:48:59.73

迷信を信じ込んで再帰を否定してるバカが
深刻なデメリット(爆笑)、例えば
> 処理速度もはるかに遅くなる。
を、実証すればスレ終了するのに。

**デフォルトの名無しさん** · 2015/12/22(火) 11:16:51.41

>>191
そういう超基本的なプログラミング知識が無いのに
なんでプログラム板にいるの？

そもそもプログラミング経験無いだろ、お前。

◆tAo.kQ2STk · 2015/12/22(火) 12:54:32.04

異様に伸びてると思ったら深刻な問題祭りかい

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

そんなに変わらないって言うのは十分大きな入力に対して精々2〜3倍以下に納まるって意味だからね。
1時間掛かる処理を20マイクロ秒速くする為にごちゃごちゃ書き換えるのは結構な事だけど。

**デフォルトの名無しさん** · 2015/12/22(火) 14:08:14.84

はるかと言っても所詮定数倍でしょ。
しかも一桁違うケースは
関数呼び出しがやや高価なスクリプト系の言語でもほとんどないでしょ。

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

>>193
いやね，絶対的に再帰でないと書けない，いや非常に書きにくいものはあるのは確かで．
たとえば代数式の解析を非再帰的で記述しろといわれると「はたして出来るのか？？」と逡巡してしまう．
こういう話題があまり発展しないのはどうしたわけですかね

関係ないけどquick-sort を三項演算子とコンマ演算子で書く話題，誰か‥私は挫折した‥

uy ◆Qawu9.2l1E · 2015/12/22(火) 18:25:40.50

再帰の深刻なデメリットと言えば、コンパイラ設計者が甘えてる事によってバグを触ったり
異常に速度遅くなるパターンが放置されてたりする事

なんの言語とは言わないけど

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

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