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

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

わくわく

嫌いな奴なんて見たことない

ループで書けるものはループで書く。
再帰使うのは仕方ない場合だけ。

スタック的なメモリ確保が必要かどうかがループと再帰を使い分ける分岐点じゃね。
末尾再帰最適化とかは本末転倒なイメージ。

前スレ
なあ、再帰関数好きな人いる？ パート2
http://peace.2ch.net/test/read.cgi/tech/1441528549/

>>5
ループ実装を隠せるのは大きいよ
抽象化はプログラミング言語の進化のベクトルと一致するからね

ループより再帰のほうが抽象度が高いと言っている？
そこは俺にはよくわからん。

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

もちろん再帰をループにするためにスタックを自前で用意するといったことでは本末転倒だが。

ツリーの巡回は再帰を使ったほうがいいだろう。
リストの巡回はループでいいんじゃね？

>>8
> 俺的にはプログラムには必要最小限の機能を使うべき
そういうのはコンパイラなりインタプリタなりが頑張るべきところだと思うね
人間はより抽象化された対象を扱うようにするのがモダンなプログラミング言語の方向だし

抽象的なスレだな

うーん。必要な抽象化は歓迎するが無駄な抽象化は歓迎しないというか。

この例は再帰とは関係ないけどJavaのファイル入出力なんかは
結構複雑な作りになってて無駄な抽象化なんじゃねーのとか思ってしまう。
まあ、俺個人の感想だが。

アルゴリズムが再帰なら普通に再帰で書く
スタックサイズ制限とかあるなら別だけど

アルゴリズムが再帰であってもクイックソートなど
再帰のままじゃあ使い物にならんものがいくらでも。

スマンｗ　クイックソートは再帰で書くわｗ

書いたことないくせにｗ

書いたことはあるけど１０年以上昔の話だな。
これは拾い物だけどクイックソートなんてこれだけのことだろ。

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

リストの巡回はループでいいんじゃないんかｗ

クイックソートは単純な巡回とは違うだろ。
だからスタック的なメモリを必要とするかどうかだよ。

ｆｉｌｔｅｒはリストの巡回とちゃうんかｗ

filterの実装がどうなってるかまでは知らんがな。

知らんなら最初からそう言えやｗ

なんか変なテンションだなぁ
俺がC++とかでfilter相当の関数書かにゃならんくなったらループで書くよ。

クイックソートはhaskellでfilterはc++なんか？
なんか変な奴だなぁニヤニヤ

何が変か、わからん。
まあ関数型言語なんかは再帰推奨らしいがあんまり好きになれん。

推奨なんて生易しいもんじゃないで。
理論に囚われすぎて原理主義に陥いった餓鬼共やｗ

まあ参照透過性とかは原理主義か？という気はする。

やっぱハノイの塔は再帰
有能

お遊びに使うためのものだね。
再帰なんて。

>>8
ループでquicksort書いてみてくれ
上のコードと比較で見るだろ
言語は好きに選んでいい

ループでクイックソート書こうとするとスタック的なものを自前で用意せにゃならんのじゃないか。
めんどくさすぎ。

なんかやたらと再帰がお遊びだと連呼する奴がいるが、どういう意図で言っているのか分からん。
お遊び感覚で動くものが作れるのだから、苦労しなくていい分優れているってこと？

>>25
関数型言語は変数再代入禁止（のものが多い）から、そもそもループは書けないんだよね

再帰がお遊びだ
再帰がお遊びだ
再帰がお遊びだ

>>32が可哀想だから連呼してあげたよ

あ、意味は「お遊び感覚で動くものを作るな」という事です。

動くんならいいんじゃないの？

ま～た関数型コンプレックスのアホが暴れてるのか

関数型は関数脳にならないと書けないからねー
手続き脳がしみついてると貶す対象にしかならないよね

お前ら俺を笑い死にさせる気かｗ

初めて知った時すごいと思いました

せっかく埋め立てたのに何またスレ立ててんのゴミクズ

ぼくたん初心者なのでわからんけど僕が今作ってる
関数から値を求める計算プログラムで再起型関数が大活躍してるお
たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー

> たぶん今僕がやってる書き方が一番きれいだと思うんだけどなー
いろんな方法で書いてみないと比較できないんじゃね？

クイックソートで再帰なんてありえんと
さんざん言われ続けているのに、まだバカが湧いとるんだな。

ライブラリのループ版を使えば何の手間もかからず高速処理ができるのに
わざわざ問題ありまくりの再帰で書くなんてテロ同然の暴挙。

>>44
それって結局真の再帰を見たことがないからそう思い込んでるだけだよね。
見せてやるよ、真の再帰ってやつをな。
https://ideone.com/EDtRIH

もうソーティングの話は良いよ、仕事で使う大抵の言語ではライブラリとして用意されてるんだから。

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

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

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

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

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

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

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

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

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

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

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

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

直列化ツリー構造kwsk

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

>>59 乙

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

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

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

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

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

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

恥ずかしすぎるこのスレ

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

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

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

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

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

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

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

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

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

>>73
uyの残した名言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

おせぇな uy

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

s/69/67/

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

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

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

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

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

ありがとうございます

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

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

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

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

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

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

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

ループ 3.99秒
再帰 4.50秒

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

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

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

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

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

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

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

きっしょ

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

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

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

おいらも苦手だわ

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

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

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

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

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

なんで自分でやらない？

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

ｗ

https://ideone.com/63bZSE

たらいの展開の様子

haskell気持ちEー！

ループ化は誰か頼むわ

きも

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

function NodeIterator(node, childNodesName) {
　　this._stack = [node];
　　this._name = childNodesName;
}
NodeIterator.prototype.hasNext = function() {
　　return this._stack.length > 0;
}
NodeIterator.prototype.next = function() {
　　var node = this._stack.pop();
　　if (node) {
　　　　for (var i = node[this._name].length -1; i > -1; --i) {
　　　　　　this._stack.push(node[this._name][i]);
　　　　}
　　}
　　return node;
}

ノードの親や深さも欲しい時は、スタックに積むノードをオブジェクトでラップして親の参照や深さを持たせればいいかも

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

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

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

センスないと無理

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

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

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


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

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

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

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

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

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

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

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

ツリーじゃね

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

何だこの池沼ｗ

ごめん

いいってことよ

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

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

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

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

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

ごめん

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

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

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

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

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

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

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

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

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

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


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


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

>>172
Java「…」

>>175
漸化式

それは、無限再帰

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

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

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

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

馬鹿には出来ませんね

ごめん

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

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

flattenとか難しいよね

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

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

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

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

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

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

そうなのか？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

それは再帰のデメリットではなくそういうクソコンパイラしかない言語のデメリット

>>192
能書きはいいからとっとと実証しろ。超基本的な知識なんだろ。

「はるかに遅い」とか言ってるバカ仲間のサイトでも良いぞ。

>>197
なんか食パン裏返してこっちが表だとか必死に言ってるようなレスだな

>>199
食パン裏返してんのはお前のほうだよw

>>198
へい。再帰が130倍時間がかかるエビデンス。

食パンの裏はどっち側だよ

>>201
こうするとなかなか興味深いことになるね。
本当に興味深いと思ってるだけで他意は無いよ。

fun_rec(){
if [ $1 -gt 5000 ] ; then
time fun_for
return
fi
fun_rec $(( $1 + 1 ))
}

>>203
たしかにおもしろい。
再帰の深さに比例して時間がかかる。
再帰が深くなると処理に時間がかかるようになるのか、
別の時間を測ってしまっているのか。わからん。これはわからん。

>>201
必死で再帰否定してるバカは知能が低いというエビデンス乙

シェル関数は呼び出しのたびに名前解決するのでペナルティが大きい

Cの場合は入った時にフレーム作成と出る時にフレーム復元
c86なら、レジスタ操作4ステップ(複合命令なら2ステップ)だ。
名前解決なんかリンク時に終わってる。

最近の関数呼び出しは引数をスタックに積まずにレジスタ渡しみたいだから
再帰で何段ネストしちゃっててもレジスタに収まってる限りは爆速なんじゃね

名前解決まで計算時間に含めるなら
もう再帰云々じゃなくて長大な再帰なしの一つの関数で全部こなせって話になるんだがな

>>207
いや、そうはならない。
レジスタの退避が必要になるから、自己再帰するならどっちにしても同じだけpush/popは必要になる。
最適化が掛かったらその限りじゃないけど。

>>205
呼び出しだけじゃなく参照もね、iの。
localでもスタックフレームなめてるのかな?

>レジスタの退避が必要になるから

そうかなー

>>209
スタッフフレームは再帰に必要なステップだから、再帰のペナルティとしてあえて受け入れた。

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

(場合もある)を知らないのか、教わってないのか知らないが、全ての場合だと思い込んでるところもバカの、特徴だね。

>>210
再帰で書いた何の変哲もないフィボナッチ関数をビルドしたケースを示すよ
https://gist.github.com/pixie-grasper/ba2d0ade523b8599c182
gccではr12を、clangではraxを、rbp/rbxの他に退避してるのが分かる。

対比先もレジスタにすればいいのにね

そんな事をすると
既に退避させてある値を別なレジスタに退避させてから、退避させたい値を退避するコードを吐く羽目になるけど
レジスタが最低でも加算無限個無いと出来ないからね。仕方ないね。

externしていないstatic関数とかならレジスタ渡しもふつうにある。
もちろんCランタイム・コンパイラによる

>>215
いつの時代の話をしてるのか分からんのだけど、所謂Intel系の64bit環境(amd64)だとレジスタ渡しがデフォルトだよ。
https://en.wikipedia.org/wiki/X86_calling_conventions#List_of_x86_calling_conventions

>>204
bashはダイナミックスコープだから再帰の深いところでは
変数の参照に時間がかかるのかな。いまはその辺を疑ってる。

>>197
ｗ

だいたい再帰で問題が無いなんて
クイックソートで再帰が役に立たない事すら知らないってことか？

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

>>219
何が言いたいのかわからん…

>>219
ファーｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

>>219
じゃ、これを10000倍高速化して実証してよ。
http://svnweb.freebsd.org/base/stable/10/lib/libc/stdlib/qsort.c?revision=256281&;view=markup

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

>>223
10000倍高速化の比較対象はそれでも良いぞ。

一万倍とかｗｗｗｗ
どこをどうやったら一万倍差がつくんだ

>>225
クイックソートの最悪の時間計算量はn^2なので
データによってはとても大変なんよ。

アルゴリズムの抽象化に静的言語使うチンパンとか話にならないから(´・ω・｀)


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

>>225
最低10000倍ね。笑

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

あ、小学生のように0.0001万倍とか言い逃れるかも。爆笑

>>227
http://hissi.org/read.php/tech/20151223/UGp4VlNGMlU.html

万倍高速化はよｗｗｗ

ID:u0B3Sjd8
10000倍の高速化まだ? 常識的で簡単そうな口ぶりだったけど。

万は間違いだったとしても、最低でも倍速は楽勝なんだろ。

>>232
速度以前に >>223 は簡単にスタックオーバーフローするよ。
それを防ぐ方法を教えてやってよ。

>>233
繰り返し版が明示的スタックに使うヒープと同サイズに
マシンスタックの上限を変更すればOK

いや、君に言ったわけじゃないし、最適化を教えてやれってことなんだけど。

>>233
バカなの? >>222読めないの?
10000倍の高速化まってんだから、くだらねー横槍入れないように。
お前が10000万倍高速化するならかまってやんよ。

>>226
繰り返しか再帰かに関係ないがな。
pivotの選び方次第だろ。
それは明示的にスタック使う繰り返し版クイックソートでも同じ。

>>237
あたりまえ

>>238
>>225に対するレスとして
>>226はおかしいだろ。
気にならんのか?

>>239
何を言っているのか意味がわからない…

>>240
最悪パターンでもよいから、10000倍高速化しろよ。

スキルない人間をいくら叩いても何も出てこないのに
ここは動物園かよ

黒魔術師は再帰関数が大好き

黒魔術師はマクロを生成するマクロも大好き

再帰を必死に否定しているバカの主張

1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。

>>245
そうやって執拗に絡むのもはっきりいって馬鹿丸出しだよ。
せっかく相手がクイックソートのコードを書いてくれたんだから
そのコードの問題点を指摘する方が賢そうに見えると思ったんだけどね。

>>246
さらなる意味不明なバカが出てきたな。
コード出したのは再帰を必死で否定してるバカじゃないぞ。

最初期は再帰をサポートしてなかった計算言語があるらしい

今はハードウェアレベルで再帰が実装されてるからな。
それを思えばいかに再帰が本質的にプログラミングに必要とされてるかってことだな。

計算可能性を探求する試みにおいて最初に出たのが、
エルブラン・ゲーデルの一般帰納関数だからね。
次がラムダ計算。
その次がノイマン型計算機直系の先祖であるチューリングマシン。

10000倍だっておとなしいぐらい。

再帰だと落ちまくるから∞倍だって当たり前だろ。

メモリ足りないなら動かないのは再帰もループも変わらんだろ。
ループのほうが本質的にメモリ使用量少なくなるとかなら話は変わってくるが。

これだね。本当に知能が低い。
> 1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する

＞再帰もループも変わらんだろ。

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

ループ方式なら、データが何千万件あろうと無問題

>>254
ループのソース晒してみろや

覚えたての知識を使ってレスバトルするだけのスレなんていらねーから

いらないスレを使って自分の意見を垂れ流すとか有効活用乙としか

そういう初心者の遊び場もあっていいと思うけどなあ

>>252
再帰の方は、関数呼び出し大量に発生するから、リターンアドレス待避とレジスタ待避に、メモリーが喰われる。

>>259
ループの方は今どの範囲についてソートしているのかという情報が大量に発生するから同じ議論が成り立つ訳だが。

>>260
ループはヒープ、再帰はスタック
つまり、ヒープとスタックがぼくらを助けてくれるんだ！

>>254
>>222(再帰版qsort)で5000万件ソートしてみた。楽勝で終了する。
必死で再帰を否定しているバカが低知能だという事がまた証明されてしまった。
頭が悪いって本当にかわいそう。

>>262
再帰版でうまくいくのだったら非再帰版ではもっとうまくいく，という発想はないのかね？

>>263
うまくいくって言ったって高々定数倍速くなるだけだろ？
非再帰版を書いたり保守したりするコストより新しい速いマシンを買ったほうが安く上がるって発想は無いのかね？

>>263
知能障害者って本当にかわいそう。
5000万件でソート出来てるってことは、「再帰はスタックあふれる」という迷信が嘘だという発想には至らないのかね。
クイックソートの深さの制御はすでに研究し尽くされてて、全然問題ないんだよ。

あっ、繰り返し版は10000倍速いんだっけ? (爆笑)
早く実装コードみたいなあ。

>>266
そんなに実装したいのなら教えてしんぜよう。
5000万件で >>201 を実行してみたまえ。
再帰呼出しというのは効率が悪いとても頭の悪いやり方なんだよ。

シェルスクリプトを証拠として使うのは笑ってしまうからやめろ

>>268
反論できないのな？じゃあお前の負けってことで。

野次飛ばしてる観客相手に勝利宣言も笑うからやめろ
おまえはプロレスのヒール役か

＞高々定数倍

そんな安全なもんじゃあねぇ。
データが増えれば差も増大。

>>267
ぷぷぷぷ
知能障害者は>>201をクイックソートと呼ぶのか?

>>271
ミジメすぎるぞ。クイックソートのスタック消費量はlog nに抑える事が可能。
こんな基本的な事を知らないから数千万件はソート出来ない。キリッ

とか、赤面な発言しちゃうんだよ。

ちなみにglibcのqsort(これは非再帰)も同じ手法で自前スタックを管理してる
知能が低いって本当にかわいそう。

https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;h=04c25b984f74a8f738233cc6da8a738b6437833c;hb=b8079dd0d360648e4e8de48656c5c38972621072

/* The next 4 #defines implement a very fast in-line stack abstraction. */
/* The stack needs log (total_elements) entries (we could even subtract
log(MAX_THRESH)). Since total_elements has type size_t, we get as
upper bound for log (total_elements):
bits per byte (CHAR_BIT) * sizeof(size_t). */

>>272
バカかお前は。ボウフラサイズの脳ミソしか搭載してないのか？
ただの繰り返しでさえ130倍の差があるのだから
クイックソートを実装したらそれ以上の開きがあるのは自明だろうが。

>>273
log n は発散するんだが‥

>>275
バカはお前だ。シェルスクリプトでクイックソートを実装するなんて誰がするか。
sortプログラムを使え。

ちなみにシェルスクリプトの場合、関数呼び出しはそれ自体がスタックの深さをnとしてO(n^2)くらいの計算時間を持つっぽい。

>>275
ぷぷぷ。知能障害は本当にかわいそう。
qsortの繰り返し版は関数呼び出しの代わりに自前でスタック管理しなきゃならないんだよ。
10000倍高速化の実証コードはよ。

>>276
確かに、うん、確かに、非常にゆるやかに発散するね。

n=2^64としてもlog nは64だけどね。
定数と変わんないレベルだよね。

>>277
実装できないのな？無理なのな？はい論破。

>>278
>>201 がすべてを物語っている。
これが何よりの証拠。再帰がとてつもなく効率が悪いことを
つまびらかにしてみせた。ここに来て見てみぬふりは通用しない。
エビデンスもきちんと示されている。もはや知らぬ存ぜぬでは済まされない。

>>280
何万倍も高速だっ。キリッ。
って主張してる奴に実証責任があるんだが

ガイジにはわからないの?

>>280
練習のためなら兎も角、シェルスクリプト「だけ」でソーティングなんてやる意味が無い。
ループだろうと再帰だろうとね。
理由は遅いから。
ループで組んだとしても、非常に遅いから、実装するだけの意味が無い。
sortを呼べばCで書かれた非常に高速でスケーラブルなソーティングが出来るから、普通はそっちを使う。

さぁ君は一体何を論破したというのだい？

>>281
障害児くん
10000倍と130倍って、どっちがどれだけ大きいかわかる?

>>282
>>201 で完全に証明してみせた。
反証する責任がお前にあるとは俺は思わないよ。
俺は自分の都合の良いように他人に責任を押し付けるなんて
卑劣な真似はできない。俺はただの真実の探求者。

>>281
ちょっと試せば分かることなんだけど、シェルスクリプトに於いて再帰の実行速度は
呼び出し深さnに対してO(n^2)くらい掛かる。

で、クイックソートの呼び出しの深さは要素数mについてO(log m)なので
O(log^2 m)の計算時間が再帰だけで掛かることになる。
つまり全体の計算量はO(m log^2 m)だ。

一方でループの場合にはO(m log m)掛かるから、その差はO(log m)だ。
この値はm=5000万、底2として約25だ。

つまり、理論上は再帰とループで25倍の差が開きうる。
そして君は10000倍違うと言う。
残り400倍はどうやって稼ぐんだい？

>>284
ボウフラ並みの脳ミソをメダカにでも食われたのかお前。
頭悪いにも程があるだろうが。こんな鶏頭野郎の
相手する俺の身にもなれ。なんていいやつなんだ俺。
聖人君子としか言いようがないわ。>>201 は5000回の繰り返しだ。
5000回の繰り返しでさえ130倍の開きがあるのだから回数が
増えれば差は開く一方だ。だから、>>267 で5000万と言ったのだよ。

霊がいるのかいないのかは判りませんが
人間の目が無いものを見ることがあるのは事実です

差は開くだろうけど比も開くのか？

>>287
5000回の再帰で130倍の差が開いた訳じゃなくて、
深さ5000の関数呼び出しで130倍の差が開いたって事を理解してる？

5000万要素のクイックソートなら最良のケースで深さ25の再帰だからね？
130倍どころか2倍にもならないからね？

>>286
クイックソートを実装して試したのか？あ？
だれが実装するかと言っていたのと矛盾するだろうが。
つまり、君は嘘をついている。ゆえに俺が言ってることの方が正しい。はい論破。

>>289
当たり前だろ。小さな町の町長が東京の都知事になって
仕事をこなせると思うか？数が増えるほどにコストは増大するんだ。劇的にな。劇的にだ！

障害児発作を発症中

>>292
すまん、その例えどこまで信用していいか分からないからそういうの語るときは式でお願い

>>290
ヤってみたのか？ヤったのか？ヤってから言えや！
さっさとクイックソートのコード提示しろよ！
いつまでグズグズ言ってりゃ気が済むんだ
俺はお前がクイックソートをシェルで実装するのをあとどれだけ待てばいいわけ？

>>295
再帰は数万倍遅いといったお前が実証しろよ

>>294
log2・5000 : log2・5000 ? 30 ⇒ log2・50000000 : 10^4 ? A
QED.

1万倍高速なクイックソートはよ

>>296
俺は >>201 で示したし、それで十分に満足の行く結果を得た。
>>201 に不満だというのならそれを超えるものをお前が書け。自分でやれ。
他人にやらせるっていうのは俺の常識からは考えられない。

>>298
お前がやるんだ。お前が言い出したことだろうが。

>>295
どうして俺が実装しなきゃならないわけ？
数万倍遅いって言い出した奴が実証のためにコードを提供するのが筋だろ？

>>301
そんな筋は通らない。実証コードが欲しいといいだしたのは
お前なのだからお前が自分で書け。言い出しっぺの法則は
プログラマを始め科学的論証に関わる人間すべてに通じる基本原則だ。
どうやればそれを確認できるかという手順も道筋も結論も示した。
自分の満足のいくものが欲しいのなら自分で行動しろ。
他人の足にしがみつくな、気持ち悪い。

１万倍の実証コードとか言い出しといて書かないってどういうことよ？
他人に頼りっきりってどういうことよ？
夢があるのなら自分で叶えろよ
親の足かじってんじゃねえぞニート野郎

>>302
IDをよく見ろ。俺は実証コードが欲しいだなんて一言も言ってない。

>>297
何この記法初めて見た
もしかして情報界隈では常識なのか？

>>219
親のスネかじってんじゃねーぞニート野郎
とっとと数万倍速いクイックソートの実証しろよ

ID:6n5NtJkMは発狂して「再帰は数万倍遅い」発言をウヤムヤにしたい模様
でも、まだ300レス。先は長いぞ。頑張れ。

>>305
俺も見たこと無い。
一瞬、三項演算子にも見えるけど順序がおかしいし。

>>304
言ったかどうかは問題じゃない！
お前はクイックソートで1万倍の差があるのか確認したい、
それを確認する手段としてシェルでクイックソートを実装すればわかる
ということを俺は示したんだよ。それだけわかってればいいよもう！

>>308
?はただの文字化けだぞ。
数理式計算量証明の理想解近似法を大学で習ってたらわかるだろ。
情報科学の基礎中の基礎だし。

>>309
いいや、そもそもそんな事は望んでない。よく読め。
俺が言いたいのは、1万倍もの差が出るなんて事は理論上ありえないって事だ。

それでも尚、実際に1万倍の差が出ると言い張るのであれば
それを実証するコードを君が示すべきだよね？

>>310
すまん、その文字化けしてるところ元は何だったのか教えてくれ
O?

>>311
だから、俺は示したって言ってるだろうが！
>>201 でくっきりはっきりと証明してみせただろうが。
それで満足できないというのであれば、満足の行くコードを見たいというのであれば
お前がそれを書くべきだ！それが論理的検証というものだ。科学的な姿勢というものだ。
他人の論文に満足できないと言ってるばかりじゃ学会では一切評価されないよ。
それを超える論文を自分で書いてこれでどうだと魅せつけるべきだ。
君はシェルでクイックソートを書くべきなんだ！！

>>312
掛け算の掛けるだ。
右側では1万倍になってるのがわかっていただけると思う。

>>281
>>205

>>285
>>205

>>313
いいかい？
君は「示した」と何度もはっきり発言してはいるけど、実のところ何も示しちゃいないんだ。

>>315
バカかお前は。大脳半球が全損して産まれて来たのか？
名前解決に時間がかかるとするならば、名前解決まで含めて再帰呼出しだ。
外務省はシリアへの渡航を自粛するよう日本国民に通告しているが、そんな不安な情勢の中、
「シリアが危険なんじゃないテロリストが危険なんだ」と言って
意気揚々とシリアに出かけていく頭の中お花畑野郎と同じだろうが。
お前が言ってるのはそれと全く同じこと。
シリアという地域でテロの被害に遭う確率が高いから外務省は渡航を自粛するように
必死に呼びかけているんだ。少しでも日本の国民がテロの被害に遭わないよう骨身を削って
頑張っているんだ。再帰呼出しでプログラム事故に遭う確率が高いから俺は再帰を自粛するよう
呼びかけているんだ。外交官としての俺の立場に立って再考してみろ。お前がどれだけ
愚かなことを言っているか今一度ようく考えてみることだな。

やべえ記号わかってもなお式の意味わかんねえw

障害児は
シェル関数呼び出しはwhileより130倍遅い
と
再帰版のクイックソートは何万倍も遅い
が等価らしい

必死で再帰を否定しているバカが低知能であることのエビデンスがまた一つ明らかになってしまった

>>317
>>201 の画像が見えないのか？俺はエビデンスをしっかりちゃっかりくっきりまるっきり示したぞ。
お前はアイマスク付けて前が見えないと言ってるだけのただのうつけ者。話にならない。

もしかしてだけどさ、もししてだけどさ、>>201で示されてることってシェル関数呼び出しがシェルwhileより130倍遅いことだけじゃね？

>>322
おいおいいい加減にしろよナメクジ野郎。
自らの関数を呼び出すことを再帰と言うのだろうが。
関数の呼び出しが遅い、すなわち再帰の効率がとてもよろしくないということだ。
テロリストが民間人を殺害するのならば、テロがはびこっているシリアには行くべきじゃないということだ。
お前、後藤さんのご家族の前で後藤さんが悪いって言えるのか？後藤さんは悪いよ。
とても危険なところと知りつつシリアに言ったんだから。だけど、それをご家族の前で言う意味がないよね。

再帰を使うっていうのはテロリストの前に自らの首を差し出すことと同義。
何があっても文句言うな。そして周囲の人間をその愚行に巻き込むな。
悲しませるな。俺はお前らが再帰を使うと悲しいよ。

純粋にシェルスクリプトだけでクイックソートを組むのは骨が折れたぞっと


ループのほうが遅いです本当にどうもありがとうございました

コードが見たけりゃどうぞ。
https://ideone.com/b9DfXr

　 　 　 ＿＿＿_
　 　 ／　　 　 　＼
　 ／　─　 　 ─　＼
／ 　 （●） 　（●） 　＼
|　 　 　 （__人__）　　 　 |
＼　 　　 ｀⌒´ 　　　,／
／　　　 　ー‐　　　　＼

なんだやっぱり再帰の方がいいのか

ぐうの音も出ないなこれは

シリアとか言わなきゃよかった
後藤さんのくだりとか意味わかんないし

フィボナッチとかはループと再帰で指数倍の差が出るんだっけ？

メモ化しないコードだとそうなるね

メモ化とか線形のメモリ食うじゃね？

>>333
直近2つを記憶するだけだから定数

>>334
それは再帰的定義を使う方では？
フィボナッチ数列の第n項を直接nの式で表せるはずだが

>>335
文脈読もうな。
メモ化に必要な記憶領域が線形ではないか、と言ってる奴がいたから定数だ、と答えただけ。

まだアーキ依存どころか言語依存の話してるの？

再帰メモ化定数メモリフィボナッチってどんなソースになるの？

fibonacci = fib (0,1)
fib (m1,m2) 0 = m2
fib (m1,m2) n = fib (m2, m1+m2) (n-1)

タプルの代わりに木かハッシュを使えば値を全部保持する
普通のメモ化にできるがフィボナッチの計算にはもちろん不要

>>325
bashを使うのであれば

if [ $i -ge $j ]; then
の代わりに
if (( $i < $j )); then と書ける。

また(( )) の中で単体の変数は$を省略できる
if (( i < j )); then

一行で書くこともできる。
(( i >= $ )) && break

stack=("${stack[@]:0:((${#stack[@]}-2))}")

これは、こう書ける。

stack=("${stack[@]::${#stack[@]}-2}")

ついでに、""をつける方が正しいのではあるが、
値にスペースが無ければ、"" は省略可能。

p=$(( $((${array2[$i]}+${array2[$j]}))/2 ))


$((・・・)) の中では普通に () が使用可能

p=$(( (${array2[$i]} + ${array2[$j]}) / 2 ))

for i in `seq 1 1 1000`; do


`` は基本的に $() と同等。新しい$()の使用が推奨されている。

for i in $(seq 1 1 1000); do


また、これは以下のように書ける

for i in {1..1000}; do

lintツールとして、shellcheckコマンドがある。

qsort_rec $left $((i-1))
^-- SC2086: Double quote to prevent globbing and word splitting.

qsort_rec $((j+1)) $right
^-- SC2086: Double quote to prevent globbing and word splitting.

$leftと$rightにスペースが入ってる場合に問題になるから""をつけろと警告される。

これは冒頭で
left=$(($1))

right=$(($2))
のようにして数値であると保証してあげれば消える。

変数 pair が未使用

その他の警告は、上の指摘を修正すれば消えるはず

ループ版で時間がかかってるのはこの部分な気がするな。
配列をコピーしているわけだし。

stack=(${stack[@]::${#stack[@]}-2})

http://www.drk7.jp/MT/archives/000995.html
さて、ここの非再帰版を見ると、どうも配列のコピーはしてないようだ。
ループ版は高速化の余地がありそうだ。

やってみるかね？ うまく実装できるかな？

ループの途中でコマンドを呼び出すようにすればもう少し遅くできるんじゃないかな。

さーて、コードをほとんど読まずに、Perl版をそのまま置き換えてみたが
きちんと動かんぞとｗ 面倒くさいな。
速度的には再帰版より速くなりそうな感じはしてるが、処理間違ってるからなｗ

あ、できたっぽい？ 参考にしたコードに二箇所バグが有るようだな。

> &qsort_array($array2,0,$size);
> $right_stack[0] = $right;

$sizeが$rightに入るが、正しくは$size-1

> if ($i - $left < $right - i) {
↓
> if ( ($i - $left) < ($right - i) ) {

Perlの優先順位は、下のように解釈されるんだっけ？
そんなの変えないよな。

今コードを見直してる。

ごめん嘘だったｗ 。あれぇ～？

Perl版実行してみたがもともとのコードからして動いてないｗ

マジめんどくさかったわｗ 参考にしたコードが悪すぎた。

他のコードと比べてよくわからん比較条件とか処理が多かったので
結局諦めてこっちを参考にした。
http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_102

結論。やっぱりループのほうが速かったねｗ
https://ideone.com/KmmnH7
recursive
real 0m0.550s
user 0m0.548s
sys 0m0.000s

loop
real 0m0.439s
user 0m0.436s
sys 0m0.000s


なお再帰版も>>326よりも速くなっているのは、
上で指摘した点をリファクタリングしたため。
>>326のコード
> recursive
> real 0m0.637s
> user 0m0.636s
> sys 0m0.000s
>
> loop
> real 0m0.723s
> user 0m0.720s
> sys 0m0.000s

ループの方が速かったので訂正よろｗ

328 名前：デフォルトの名無しさん[] 投稿日：2015/12/26(土) 21:22:21.55 ID:EXUTS9i+ [10/10]
なんだやっぱり再帰の方がいいのか

329 名前：デフォルトの名無しさん[sage] 投稿日：2015/12/26(土) 21:26:26.06 ID:hFLlv/LI [1/3]
ぐうの音も出ないなこれは

定数の差とかどうでもいい

>>353
10000倍高速化してから言いなさい

>>355
いいだしっぺどうぞｗ

>>356
>>219の主張を受け継いで高速化したお前が言い出しっぺ

言い出しっぺの定義を変えるなよｗ
本当に往生際が悪いｗ

>>353でお前が訂正を求めたレスはID:6n5NtJkMの
「再帰は1万倍遅い」に対するレス。
なので、訂正を求めるには10000倍高速化する必要がある

知能障害児には理解不能かな?

と言われてもなぁｗ

俺は1万倍速いなんて言ってないし。
ループのほうが速いという証拠も出したからどうでもいいかなｗ

じゃ、求めた訂正を取り消しなさい。

>>361
これでいいのかい？ｗ

ループの方が速かったよｗｗｗ

328 名前：デフォルトの名無しさん[] 投稿日：2015/12/26(土) 21:22:21.55 ID:EXUTS9i+ [10/10]
なんだやっぱり再帰の方がいいのか

329 名前：デフォルトの名無しさん[sage] 投稿日：2015/12/26(土) 21:26:26.06 ID:hFLlv/LI [1/3]
ぐうの音も出ないなこれは

少し速いと10000倍速いの区別がつかないおバカさんとうエビデンス(笑)

分かったことは
・再帰をただ単にループに直すと却って遅くなる
・最適化を施せばループのほうが速くなるが、10000倍速くなるなんてことはない
の2点でおっけい？

そうだな。シリアがどうとか言い始めるほどループの方が優秀な訳では無さそうだな

∞倍だね。

再帰なんってのと比較すること自体おかしい。
却って遅くなるなんて書いてる恥知らずは、プログラミング技術が無さ過ぎ。

>>366
昨日から昨晩に掛けてのやり取りを知らないのか？
俺はそのやり取りから、>>364が分かった事の全てであるって発言しただけなんだけど。

やり取りからだって？

２ｃｈの妄想だけじゃなくて現実を見ろよ。

∞倍 ｗｗｗｗｗ
無限大を憶えたての小学生かよ
quick sort 再帰/quick sort 非再帰 = ∞, すなわちquick sort 非再帰が0って事だな。

再帰を必死に否定しているバカの主張

1 スタックが制限の厳しいリソースである環境が全てだと思い込み、再帰の致命的なペナルティだと主張する
2 シェル関数呼び出しをエビデンスとして、再帰が130倍遅いと主張する
3 再帰版のqsortは数万倍遅いと主張するが、数万倍速いはずの非再帰版を示さない
4 知能が低く再帰を理解できない。それをもって再帰は難解と主張する。
5 非再帰版qsortの実行時間はゼロ

本当に知能が低い

>>364
最適化なくてもループのが速いでしょ
10000倍は無いがw

>>368
お前の中ではそうなんだろうな。そんな事より現実を見ろよ。

大本の彼らの主張は「クイックソートをお題にした場合に於いて再帰はループに比べて何万倍も差がでる(>>219)」
俺らの主張は「そんなに差がでることは理論的にありえない(>>286)」
であって、
ループのほうが再帰より「僅かでも」速いかどうか(>>352-353)なんざ元々議論していない。

クイックソートをやる上で比較にならないほど再帰のほうが遅くなるというならソースを出せや

繰り返しの方が再帰より速い！
(ただしシェルスクリプトに限る)

>>370
>>325

>>371
引数受け渡しとかレジスタ待避とかで、余分なメモリー操作が発生する。

>>374
>>260

定数オーダーの空間計算量で計算が出来ないなら、原理的に余分なメモリ操作は避けられない。
それはループでも一緒。

>>374
明示的なスタック操作と大差ないのでは?

>>373
純粋に処理速度の話してんならネイティヴコード化したものでないとさ

>>375
横ですが、再帰呼出だとcallのオーバーがある分遅くなるで良いのかな？
まあ数パーセント程度だと思うけど

クイックソートだからなんとかなってるだけで
たとえば赤黒木の操作を自前でスタック管理するアホはいないわけ

>>377
ほい、最適化しなければループのほうが遅い証拠。

>>380
ああ分かってない人ねwww

>>378
Pen4のデータシートの値を元にするなら
ループのコストと再帰のコストは約2.5～3clockくらいの差になると思う。

今時のCPUならもっと差は縮まるだろうし、実際に測った訳じゃないけど
だいたいそのくらいになる筈。

>>381
最適化が無くてもループの方が「僅かでも」速いって言い張るお前に
そうじゃない場合もあるって言ったのが>>373
で、それに対しお前はネイティブコードで比較しろっつーから
「最適化無しのネイティブコードで」比較したんだが。

一体お前は何を求めてるんだ？

>>382
そこまで解説できる人ならネイティヴコードだと逆転するのわかるでしょ
アセンブリで書けとは言わんけどさ

>>381はすまん

>>384
ループ以外の本質的な処理に100clock掛かるとすれば、
数％の差だけどループより再帰のが遅くなるって意見は正しいねって話さね

381については了解

>>385
thx

>>378
tail callを繰り返しに変換できるようなケースだと
関数呼び出しはコスト高かも知れないが、
ループ版では明示的スタック操作をしなければならない場合、
call,ret相当のことをjpと組み合わせて明示的にやらないといけない。
通常、関数呼び出し後のスタックフレームの確保はcalleeが明示的にやるからループ版と変わらないが、
スタックフレームの開放はretが自動的にやる。
だからコスト的には大差なく、
関数呼び出しの方が有利なケースだってあるはず。

繰り返しの明示的なスタック操作が圧倒的有利にあるのは、
FILOじゃなくてFIFOにしたり戦略が建てられること。

>>379
お前は何を言っているんだ。
FreeBSDもLinuxも.NETもJavaも赤黒木はループで実装してるぞ。
再帰はプログラムの中に時限爆弾仕込むようなもの。再帰使うやつはテロリスト。

頑張ってバグ入れずに済んでよかったね、としか。
しかもそれで得られる速度の向上も微々たるもの。

>>389
再帰にしたらバグが減るってものでもないしなあ。
不変オブジェクトを使うから再帰がやりやすいのであって
可変オブジェクトでの再帰はループよりもややこしいところがあるよ。

>>388
＞赤黒木はループで実装してる
本当か？やればできるものなのか？証拠をみせてみろ

平衡ニ分木であるからスタックもむやみに深くならないし，
正直なところ，可能だとしてループ化するメリットがあるのかね

>>391
freebsd red black tree source
とかで検索すれば出てくるよ

>>390
バグ云々ではなくて、コード数や可読性だと思うが
そもそも再帰呼出を理解出来ない人は論外だが

知らないうちにコードが再帰化してハマりました
のほうが多そう

>>393
主語がわからん

>>395
バグが増える要因はプログラミングソースのステップ数や可読性に左右されるのであって、アルゴリズムは特に関係ないということ

>>396
アルゴリズムによってステップ数や可読性は変わるよ

>>388
LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してないからあたりまえ。

どっかで見たことある気がしたので探してみたらunbound
http://code.metager.de/source/xref/freebsd/contrib/unbound/util/rbtree.c

また一つ、再帰否定バカが無知のエビデンス(笑)を積み重ねていく

>>398
知らない人がいたから言っただけだよ。
ループで実装されてるんだよーって。
インターフェースを実装してないからとか理屈付けする意味あるのかな。
バカはお前。

インターフェース？
再帰と関係あるのかな？
わからん。この世はわからんことだらけだ。

> LinuxもFreeBSDも木全体に対して何らかの操作を行うインターフェースを実装してない

？
OSが…インタフェースを…実装？

>>399
ねぇねぇ
そのループで実装されてる>>398のコードでも
自前でスタック管理してる訳じゃ無い。
とすると、>>379に対する突っ込みとしては>>388変じゃない？

>>402
スタック管理の解釈次第だね。>>388が変だと結論できる解釈もありだね。

>>401
わけわからんよね。

>>403
ほう、つまり君はただのループをスタック管理と解釈する訳だね？

最近、書き込みが多くなって
このスレの勢いがすごい

>>406
確かに。
>>256から数えて、1日半で150も伸びてる。

>>405
再帰をループに置き換えるときには
再帰で暗黙的に管理されるスタック上の情報を
明示的に管理する必要がある。それをやるのは面倒だから
赤黒木は再帰で実装されているはずだというのが>>379に関する俺の解釈。
面倒なことないよ、現に赤黒木はループで実装されることが多いよっていうのが>>388

語句の解釈に文句つけるのはあまり建設的じゃないような・・・。
その先には何もないような・・・。

クイックソートについても再帰のスタックをそのまま
ループで再現するっていうのはどうかと思うなあ。
末尾再帰は単純なループに変換できる。ループで書くならループらしい書き方をするべき。

>>408
ふーむ。

複雑な再帰構造を持つ場合、例えば再帰下降構文解析器みたいに複雑な相互再帰をする場合には
クイックソートの時のように簡単に再帰をループで置き換えることは出来ない。
そして一般に再帰をループで置き換えるならスタックが必要で、
込み入った再帰をスタックを使ってでもループに置き換える奴は居ないだろう。
現に赤黒木をスタック管理をしてでも強引にループで書き直すようなアホは居ないんじゃないの？
というのが>>379に関するこっちの解釈。
それに対し、いやいや赤黒木はループで実装してるんだぜ！ってのが>>388の俺の解釈。
話が噛み合って無くね？ってのが>>402

日本語の問題な気も

>>411
解釈が違うのなら話が噛み合わないことについては筋が通るかと。

>>410
そもそもクイックソートは分割統治法の典型例だからなぁ。
自分を2度呼び出す時点で末尾再帰的じゃないし
ループらしい書き方をするとクイックソートとは呼べないシロモノになると思う

あ、勿論クイックソートをもっと単純なループで書き直せるってんなら歓迎するよ！

>>413
一方の再帰呼び出しは末尾再帰になるっしょ。ループに置換できる。

>>412
複数の解釈の仕方がありうるなら、
オレオレ解釈を元に相手をこき下ろす前にやることがあるだろうと

>>415
・・・・・・それは依然として再帰関数と呼ぶのでは？

>>416
僕とー君とーは解釈が違うよねってことだよ。
こき下ろすべきじゃないと思うのは君の勝手ー。
こき下ろすのも僕の勝手ー。
ヒューマニズム振りかざす人大嫌いー。←これ僕

>>417
ループを書く場合、一方の再帰呼び出しは末尾再帰だから
単純なループに置き換えられるよねってことだから、もはや再帰関数とは呼ばないよ。

>>418
いや、君が>>403で言ったのは「スタック管理」の解釈の違いだろ？
「赤黒木が再帰で書かれてる」等とは一言も言ってない>>379を読んだ君が>>408みたいな解釈をして、
人のことをテロリスト呼ばわりするのってどうなの？

>>419
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0
「再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。」

ループを含む関数は再帰関数にはなれないの？
そんなことはないと思うんだけど。

末尾再帰を勘違いしている人がいるので説明しておこう。

末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
（単純な）ループを何らかの理由で再帰の形にしないといけない時、
末尾再帰の条件を満たすように、ループを再帰に変換すると
コンパイラが再帰をループに逆変換してくれる機能


なので、再帰を全て末尾再帰にできるわけではなく
（末尾再帰にできるのは、元が単純なループの場合のみ）
また、ループ ─(人間)→ 再帰 ─(コンパイラ) → ループ
というふうに、ループに戻しているだけなのでループより速くなることはない。

>>401,404
FreeBSDのrbtreeもLinuxのrbtreeもそういうインターフェースを実装していないって事だよ。

>>422
より正確には、「再帰全てをノーコストで末尾再帰にできるわけではなく」かな。
関数がファーストクラスならCPSに変換すれば末尾再帰の形にはなる。
・・・・・・ヒープガリゴリ使うし、スタックを自前で持つのと変わらんけど。

>>420
>>379は「赤黒木が再帰で書かれてる」とは一言も言ってないけれども、
「赤黒木の操作を自前でスタック管理するアホはいない」と言っているのだから
赤黒木の操作は、自前でスタック管理しないやり方、つまり再帰で実装される
と思っているという解釈は妥当だと思ってる。悪いけど、この解釈については譲歩するつもりはないよ。
120%君が間違っているし、再帰を使う人は120%テロリスト。それでいいね？

>>424
速くするための末尾再帰なのに、
逆に遅くなったら本末転倒だよなｗ

>>421
無理。再帰を使うなら全部再帰で書くべき。
ループを使う処理では再帰を書かない。
再帰を使う処理ではループを書かない。
それで初めてループと再帰の決着がつけられる。
そしてループが勝利する。

>>425
確率が1を超えてるとか、幼稚園に迷い込んだ気分だよ。

「赤黒木の操作を自前でスタック管理するアホはいない」と言っている以上、
赤黒木の操作は、スタックなんてものをそもそも自分で触らないようなやり方、
つまり再帰か、又は上手なループで実装されているって話だろ？
フィボナッチ数を計算する関数をスタックを使わずに書いたって言った時、君は再帰の方しか思い浮かべられないのかい？
もしかして自閉症患者かい？

>>427
それじゃぁ各ノードに可変個の子要素を持つ多分木を列挙するコードは
どうやって書くつもり？
for (auto it : children) {
　if (it->is_leaf()) {
printf("%d ", it->value);
} else {
it->print_values();
}
}

>>428
>>389を見るに、そうじゃないと思うんだがなあ。
俺は自閉症患者だけれども、それとこれとは関係ない。
お前は全国の自閉症患者やそのご家族の方に謝罪するべき。
あとテロリストにも。

>>429
どうやってって何がだよ？
ループでか？再帰でか？

>>430
日本語って難しいよね。分かる分かる。
>>389の解釈は、
再帰でも書けるところをループで書いたんだ。へぇ。バグってなくて良かったね。ご苦労さん。
じゃないの？
>>379が再帰を仮定しているかどうかとは別問題。

俺も自閉症患者だけどね。自分に謝るのって変な感じがするよ。

>>431
どっちでも良いけど、どっちかしか「使ってはならない」というローカルルールの元ではどう書くの？

>>431
まだ出来ないの？
>>429に7行で書いたような、こんなコードが走ります的な切れ端で十分伝わるんだよ？

>>432
スタックで管理の解釈の違いだな。やっぱり噛み合わない。

>>434
あのさ、同意も取らずに強引に物事を進めようとするのってどうかと思うよ。
北風と太陽って話くらい知ってるでしょ？コンセンサスってとても大事。
お前コンセントしか知らないだろ。扇風機の線をぶち込んどけば何とかなるものと
しか思ってないだろ。それじゃないからな。
まずは、どういう理由で書いてほしいのかっていうところと
それによって何が成し遂げられるのかっていうところとどうして自分で
やらないのかって言うところを説明して、心からお願いしないと俺の不動の心は動かないよ。

>>435
残念。

>>436
ループを含む関数が再帰関数になれないのであれば、
>>429のような書き方は認めないって事だよね？
君ならどう書くの？って聞いただけなのになんでそんな反応になるのかね？

横道にそれ過ぎずに、それぞれの論旨を書いてみろよ。
中傷合戦ひどくてわからん。

>>437
ループと再帰の優劣をつける場合、ループはループだけで
再帰は再帰だけで実装するべきだよねって話をしただけだよ。
お話の前提をすり替えてあたかもお話が続いているように
するのはよろしくないと思うんだよな。

>>438
俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
恐ろしいことだ。

>>438
大本の論旨としては、人のことをテロリスト呼ばわりするのってどうなん？って事なんだけど。

ループと再帰の優劣をつけるなんてどこから出てきた？

>>441
テロリストと呼ばれるのが嫌ならテロ行為やらなければいいだろ。
クイックソートでやってただろ。ループがいいか、再帰がいいかって。それのこと。
知らなかったの？じゃあ知って。今知って。

バッファオーバーフロー攻撃を成功させるためには、再帰が最も都合よい。

攻撃されるのと攻撃するのと、どちらが良いか？
当然、攻撃する方が良い。

つまりテロリストは勝ち組なのである。

当該スレにおいて再帰を推奨している人は勝ち組である。
なぜなら危険物を推奨するのは攻撃側だからである。

>>443
そういうことだな。昨今、関数型言語の流行に伴って再帰がすぐれたものであると
思い込んだニワカのペーペーどもがろくな知識も持たずに危険なコードを
書きまくって悦に入ってる姿を見ると暗い気持ちになる。再帰というのは
ループに大敗北した歴史を持つものだっていうのを知って欲しい。
for whileというのは再帰の進化形。メガ進化。

お前ら逮捕されても知らんぞ。

公共の場所で再帰を勧めたりしてたら、そのうち警察が事情を聴きに来るぞ。

どうでも良いけど、再帰がテロ行為になるなんて初耳だなぁ

# 今日の夕飯はすき焼きでした

>>447
自動車の256バイトしかないRAMで再帰したら、バシバシ轢き殺すぞ。
そこまでやってこそ本物のテロリストだろ。

>>448
誰がそこまで特殊でオンボロな例を挙げろと

ちなみにテロリストの定義はテロリズムを奉ずる人で、
テロリズムの定義は
https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%AD%E3%83%AA%E3%82%BA%E3%83%A0#.E5.9B.BD.E9.9A.9B.E9.80.A3.E5.90.88
「住民を威嚇する、または政府や国際組織を強制する、あるいは行動を自制させる目的で、
市民や非戦闘員に対して殺害または重大な身体的危害を引き起こす事を意図したあらゆる行動」
だそうですよ。

あと自動車の場合、バシバシ轢き殺すなんて事態にはならず、単にエンストするだけだと思うの。
フェイルセーフって知ってるよね？

>>440
> 俺は畑を耕していただけなんだ。そしたら ID:Zmrinoji こいつが
> 機関銃もって脅してきたんだ。おらはイモが食いたいだけだ。再帰使うやつはテロリストだ。
俺の知ってる事実と違うね。

俺は今日は364から話を始めた。そこにID:9aquywWvが388から割り込んできて、
人のことをやれテロリストだやれ機関銃をもって脅してきただ喚いてるの。

>>450
テロリストは自分のことをテロリストだと思っていないんだよな。
聖戦士だと思ってる。
正義のために再帰を仕込むんだよな。

まあでも、国民側から見ればテロリストなんだけどな。

再帰なんてある意味爆弾みたいなものだしな。
テロリストが使う新型爆弾なんじゃねーかな。

そうやって正義の為にループを仕込むんだね？
よく分かったよ！

ちなみにバッファオーバーフローの攻撃手法としては再帰は下の下だからな。
getsなんかを使った方がよっぽど手っ取り早い上に任意コード実行まで出来る。

>>450
聞かれたから答えてたけど、>>388は君に対するレスじゃないよ。

>>454
知ってるよ？
でも再帰使うやつはテロリスト発言で敵を増やしてないかい？

>>455
割り込んでないよね。テロリストと糾弾されて君が勝手にファビョッただけだよね。
僕は畑耕してただけ。

>>456
文脈をよく読もう。
364から始まる再帰とループに関する話に混ざった379に君が割り込んでるね？

>>457
アッラーアクバル。

テロリスト（笑）
アホかな？

お前らなんでそんな盛り上がってんだ？

>>457
割り込んでないね。僕は>>379に話しかけただけだね。
君が>>379とお話したかったのなら>>379に話しかけるべきだね。

>>458
そうだね、偉大だね。
スプンタ・マンユに祈りを！(宗教ちげぇ)

>>460
いわゆる暇人という奴では。

>>461
木構造って知ってる？

あと、俺はそのレス(>>379)にその返し(>>388)って変じゃね？って言っただけで、
それに対して君が「スタックの管理とは」なんて話を始めるから(>>403)
そのコード(>>398)の何処にスタックなんて使われてるんですか―って訊いて(>>405)
それに対してまだ答えが返ってきてないんだけど。
君はあれかな、都合の悪い質問は見なかったことにする人なのかな。

>>463
なんで僕にレスしてくるの？
自分が話したいことがあるならそれを話せばいいじゃん。

僕は僕で自分の話したい話を話したい人とするから。
たまたま>>379だったってだけで君が>>379と話したいなら
僕はそれを否定しないよ。割り込まれたとも思わない。

ほら話しかけろよ。>>379も絶対お前のこと好きだって。
言っちゃえよ。好きだって言っちゃえよ！

>>464
暇潰しに最適なので大好きです

>>465
僕もだよ

>>466
それで、人のことをテロリスト呼ばわりするのってどうなん？

ID:Zmrinoji必死だなｗ

>>469
必死乙

>>467
違うんだ、待ってくれ、君のことをテロリストと言ったんじゃない。
再帰を使う人はテロリストなんだ。君じゃない。

>>470
つまり、>>469で示したように再帰を使う俺はどっち？

>>471
では準構成員ということでここはひとつ

>>472
笑ったから良いやｗｗ

お前ら仲良いな

やっぱり再帰無しでループによるプログラミングが最高だね！

しね

uy
品が無さすぎ。

>>476
>>476

私生活において自分ほど品性の高い奴はそうそういないよ
何をしていてもカリスマ性があふれ出してしまう

「しね」というのは、実は奥の深い言葉なんだけど知っていましたか？
プログラム中でいえばNULLと似ている

人はなぜ生きるのか、なぜ死なないのか、
その真理を見つける事は誰も出来ていない
よって「死」とは恐怖かもしれないし、救いかもしれない
つまり正解でも不正解でも無い
それゆえに「しね」という言葉を発しても、敵と味方は最終的に五分にしかならない意味のない言葉なんです
だから頻繁に使っていくと良いよ

アスペが語りだしたと聞いて

>>480
しね

再帰じゃないと書いてらんない関数があるのも事実

>>419
アホはしね

>>422
tail callも知らんのかよw

>>423
インターフェースとか抽象データ型ってことを理解できてないから、
そう言っただけでは理解できないんだと思うよ。

>>429
でけたやでー
https://ideone.com/hykdXg

>>485
お前のほうが分かっていないような気がするが‥

>>422の「なので、再帰を全て末尾再帰にできるわけではなく」とか恥ずかしいよなw

>>489
>422 「再帰を全て末尾再帰にできるわけではな」いのは当然だが，どうしてはずかしいんだ？

> コンパイラが再帰をループに逆変換してくれる機能
恥ずかしい発言はこれだね。

>>491
その理由を言わないとｗ

掲示板ではレベルのミスマッチがよくあるんだよな。

たとえば、アセンブリと機械語は一対一で対応していると純粋に信じてる人は世の中に結構多い。
そういう人たちとプロセッサのデザイナが掲示板で議論すると当然ミスマッチが起こる。
こういう場合、当然勢力の面でデザイナの方が分が悪くなるね。
世の中、知ったかぶりのバカの方が多いから。

手動で末尾最適化をしてみればいいんだよ。

そうすれば、なるほど、
これが最適化されたコードなんだな！って
ループになったコードを目の当たりにすることになる。

そういう周りくどい事やってるうちは三流
uyの領域に到達すると文章読むだけで理解する

>>491
コンパイラが再帰をループにしてくれる機能はあるよ，恥ずかしいのはどちら？

再帰の方が有利なら、わざわざループに変換するなよ。
むしろ、ループを自動的に再帰に変換しろよ。

>>492
逆変換が意味不明
単に変換なら同意するけど

テロリストは逮捕されろよ。

再帰が実用的でなく
ループの方が有利だから
変換しないといけない。

>>498
それは文脈による，よく逆電圧っていうが実は順電圧だったりすることはあるし

>>501
> それは文脈による，

だからこの文脈だと意味不明って言ってるんだが

> よく逆電圧っていうが実は順電圧だったりすることはあるし

ますます意味不明

>>502
この分からず屋！！

分かるように説明できないんじゃ周りは皆分からず屋に見えてしまうね

我々市民はテロリストを納得させるような言葉を持たない。
従って、テロリスト自ら変わらない限り、テロリストは永遠に市民の敵である。

>>496
キミの方だとおもうよ。ぷぷぷ。
「末尾再帰は... コンパイラが再帰をループに変換してくれる機能」

> 末尾再帰は「再帰を末尾再帰で書けば速くなる」というものではなくて
> （単純な）ループを何らかの理由で再帰の形にしないといけない時、
> 末尾再帰の条件を満たすように、ループを再帰に変換すると
> コンパイラが再帰をループに逆変換してくれる機能

>>496
それは、「末尾再帰最適化」というコンパイラの機能だね。

「ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる」
頭沸いてるだろ。ぷぷぷ。最初からループで書いとけよ。

そんなんじゃ小説なんか読めないだろう。
読解力なさすぎだよ。

読解力が足りないとか言いだしたぞ。このバカ。

> ループを再帰に変換すると、コンパイラが再帰をループに逆変換してくれる機能

>>490
再帰はすべて機械的に末尾再帰に変換できる。
そんな基本的なことも知らないのは恥ずかしいだろう？

おー、すげー。天才現る。
これで、スタックオーバーフロー完全克服だ。

末尾再帰に変換できるとは言ったが,スタックオーバーフローを回避できるとは言ってない(ｷﾘｯ

クイックソート10000倍高速化とか再帰→末尾再帰の自動変換とか、このスレには天才が多いな。

CPS変換も知らんのか…

>>510
俺は第三者だ。
俺は書き込んだ奴の言いたいことが容易に把握できている。
それがキミにはできないという。

再帰についてのスレで再帰について書かれているのだから、バックボーンの違いではないだろう。
知識ではなく読解力の問題だ。
こんなもん小学生でも意味をくみ取るぞ。

>>516
>>422を理解出来てるのか? こりゃすげーわ。
ループを再帰の形にするときに、ループを再帰に変換すると、再帰をループに逆変換してくれるコンパイラの機能が末尾再帰?

>>422が末尾再帰を理解してない事が読み取れるだけだ。
それをお前が読み取れるという事は、同一人物以外あり得ない。

そんなんじゃ小説も読めないだろう。

末尾再帰とは、本来ループで書くべきものを再帰で書いた時にコンパイラが
自動でループに直す機能・・・という主張なのだろう。

>>515
よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。

逆変換という言葉は、そういった前提があって出てくる言葉だと思うぞ。

コンパイラが最適化してくれるならコンパイラにやらせるのが普通の話だよね

>>521
ループの方が最適化効きやすいしな。

>>520
末尾再帰の説明に「逆変換」を使うってどういう前提だよ www

>>523
本来ループであるべきものをプログラマが再帰に変換しているので、
コンパイラがループに逆変換するという主張なのだろう。

お前、本当にこの程度の文章が読めないの？
そんなんじゃ小説どころか論文も読めないだろう。

俺は元の文すら読んでいなく、引用されてるのを見てそこまで理解できてるぞ。
もう一度聞くけど、お前本当にこの程度の文が読めないの？

> インバータ（Inverter）とは、
> 直流電力から交流電力を電気的に生成する（逆変換する）電源回路、
> またはその回路を持つ電力変換装置のことである。
> 逆変換回路（ぎゃくへんかんかいろ）、逆変換装置（ぎゃくへんかんそうち）などとも呼ばれる。

逆変換ｗ

>>519
>よくいるんだわ。より難解な前提が必要なのに、出来るよって言い出す奴。

何言ってんだこいつ

>>524
おおー、スゲー
その調子で>>422を解説してくれや。

>>526
読解力が、足りない。

半端な知識を振り回す知ったかぶりが沢山いるという事だよ。

>>528
それは読解力関係ないだろう。
俺にも全く意味が分からなかった。
何言ってんだコイツ？というのが素直な感想。

http://athos.hatenablog.com/entry/20110119/p1

ここまでこれの話題ないって相当終わったレベルの奴らしかこのスレにいないんだな

さっさと死ねよ

>>530
そりゃrubyだからさ

今年もrubyのオワコン芸ｗ

>>531-532
本当に頭悪いカスだな
rubyに限定せず実装出来ると思うけど技量的に理解すら無理な感じ？
再帰とループの変換や末尾再帰の話題には触れてもここはTCOという単語が今まで一回も出てこないという事実

「知ってる側」からすると嘘をついてるのがすぐにわかってしまう
知ったかぶりのクズ

>>531-532
さっさと死ねよ

>>533
だって末尾再帰なんてlisp/schemeでは当たり前だもの，今はgccでも当たり前だし
いまさらrubyですかね‥

むしろ自分でやんないと末尾呼び最適化が利かない処理系って（ry

なんだか遅れてるんだよねruby屋さんって

rubyだからね。仕方ないね。

>>533
何度も出てるし「末尾再帰」といった時点でジャンプへの変換という意味を持っていってるんだよ。
最適化が無ければ「末尾」と特別な扱いをする意味が無い。
runyって最近言い出したのか。30年遅れてるな。

理解度が低すぎる
このアルゴリズムはこのスレでは初出だと認識してるけど
読めなくてわけわかんない状態か

さっさと死ねゴミ

妥協点でPythonだからね
それ以下の言語でアルゴリズム語ってるスレ見ると
そこで話してる内容とか読む前に
まずはスレ民を学習させる事から初めて
レベルを上げてやらないと話にならない

>>540
末尾再帰のループ最適化は >>5 や >>507 ですでに出てきているよ

>>541
最適化の話題なら python や ruby のようなインタプリタではなく
コンパイラで比較するのが適切だね，インタプリタ上で速くなっても
だれもうれしくない．C/C++一択だよ
ま，fortran でもいいが

再帰好きの人をサイキッカーと呼びたい

いいなそれ

再帰好きの人のを中二コーダーと呼びたい

>>542
理解力なさすぎだな
お前の学校の担任はさぞかし苦労したことだろう

>>546
どんな点をみて「理解力がない」と判断したのか？
説明できますかね，それとも吼えるだけ？

つか、末尾再帰ってループそのまんまで再帰の利点ないし

recHoge1(a,n,arg...){
　dobefore()...
　if(a<n)recHoge1(a,n,arg...);
}
loopHoge1(a,n,arg...){
while(a<n){
　dobefore()...
　}
}
再帰は無意味、使う必要なし

recHoge2(a,n,arg...){
　dobefore()...
　recHoge2(a,n,arg...);
　doafter()...
}
loopHoge2(a,n,arg...){
　while(a<n){
　　pushargstack();
　　dobefore()...
　　popargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える

pop,push逆だった
loopHoge2(a,n,arg...){
　while(a<n){
　　popargstack();
　　dobefore()...
　　pushargstack();
　　doafter()...
　}
}

pushargstack();
popargstack();
ユーザー定義のこれらはめんどくさいから
再帰関数使ってコンパイラ任せにするよ

またゴミカス初心者が来たけど
また１から説明して教育しなきゃいけないの？

recHoge1(term,arg...){
　dobefore()...
　if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
　while(term){
　　dobefore()...
　}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
　dobefore()...
　if(term)recHoge2(term,arg...);
　doafter()...
}
loopHoge2(term,arg...){
　while(term){
　　popargstack();
　　dobefore()...
　　if(term)continue;
　　pushargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容

>>551
>>552
以上のことの何があるか説明してみてよ

http://nas6.main.jp/Maze.cpp

再帰、ループ、等価迷路

recHoge1(term,arg...){
　dobefore()...
　if(term)recHoge1(term,arg...);
}
loopHoge1(term,arg...){
　while(term){
　　dobefore()...
　}
}
再帰は無意味、使う必要なし
recHoge2(term,arg...){
　dobefore()...
　if(term)recHoge2(term,arg...);
　doafter()...
}
loopHoge2(term,arg...){
　while(term){
　　pushargstack();
　　dobefore()...
　　if(term)continue;
　　popargstack();
　　doafter()...
　}
}
再帰で有意味、この場合使える
pushargstack(); popargstack();
ユーザー定義のこれらはめんどくさいから、再帰関数使ってコンパイラ任せにするよ
たったこれだけの内容 、勘違い訂正

>>554で、
ループ実装が好きなやつはいないと思うんだけどな

RubyかPythonで書き直して
C++とかいうゴミいらねーから

「｛Ｃ＋＋規則をかなり抑えてＣライク｝で書かれたソースコード」
のクロスランゲッジなんて、ほぼ、ライブラリの関数名を書き換えるだけだろ

あ、あと制御構文もちゃっちゃっと書き換えれば出来上がり

それをなぜ最初から簡潔な言語で書かないで
わざわざ冗長したC++・C言語といった言語でドヤァとソースコード貼りつけてくるのか、理解しがたいんだけど
カスレベルの初心者である事を数レスに渡る自己紹介でもしにきたのかね？
アルゴリズムの抽象化でC++とか使う奴はその時点で初心者だって一瞬で分かるって言ってるのに
自分が知恵遅れだと分かってないままの奴が続々現れるからこういう場所は話題がループする

>>559
死ね

熱烈なC++アンチって速度要求される場面に出会ったことがないんだろな
もしくはフォートラン信者なんだろな

オッパイソンはベーシックみたいなもんで非プログラマが使うのに適してるけど、
プログラマが使うには色々しょぼすぎ。
ペイントショッププロのマクロにオッパイソンが採用されたときは、来るかと思ったけど、
それを機に没落していった。
イヌックスの呪いは有名だけど、オッパイソンの呪いもあるのかもしれん。

しかし、エクセルのマクロ使いはザラにいるのに、他のアプリはマクロ使いが
ほとんどいないんだよな。
イーマックソとか言うウンコは置いといて。
CADなんかマクロの使いであると思うのだが。
Autocadなんかウンコ使いが泣いて喜ぶLisp搭載してるのにな。
なんでだ。

とりあえずuyがほんとになにもわかってないことだけわかった

ruby知らんがこんな感じだろ

def recHoge2(term,arg...)
　　dobefore(arg...)
　　if term
　　　recHoge2(term,arg...)
　　end
　　doafter(arg...)
end
end

def loopHoge2(term,arg...)
　while term
　　pushargstack(arg...)
　　dobefore(arg...)
　　if term
　　　next
　　end
　　popargstack(arg...)
　　doafter(arg...)
end
end

class stack
　def initialize
　　@ret = -1
　　@crnt = 0
　　@MAX_STACK = 32768
　　@stk[MAX_STACK]
　end
def pop_stk()
　　if -1 < crnt
　　　ret = stk[crnt]
　　　crnt = crnt - 1
　　end　
　end　
def push_stk(v)
　　if crnt < MAX_STACK - 1
　　　crnt = crnt + 1
　　　stk[crnt] = v
　　end
　end
end
stk = stack
def pushargstack(arg1...argn)
　stk.push_stk(arg1)
　...
　stk.push_stk(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop_stk()
　...
　arg1 = stk.pop_stk()
end

def recHoge2(term,arg...)
　dobefore(arg...)
　if term
　　recHoge2(term,arg...)
　end
　doafter(arg...)
end

で、こんだけで済むのに、
ループにしたいからって
スタックのユーザー定義なんて馬鹿だろう

再帰をループにしたかったら
こういうのをいちいち作らなきゃだめだよ
class stack
　def initialize
　　@crnt = 0
　　@MAX_STACK = 32768
　　@stk[MAX_STACK]
　end
def pop_stk()
　　if -1 < crnt
　　　ret = stk[crnt]
　　　crnt = crnt - 1
　　　return ret
　　end　
　end　
def push_stk(v)
　　if crnt < MAX_STACK - 1
　　　crnt = crnt + 1
　　　stk[crnt] = v
　　end
　end
end

プログラミング半年目くらいだろうかコイツは
多く見積もって1年半
それ以上なら今すぐPC捨てたほうが良いレベル

>>569

http://www.rubylife.jp/ini/

http://www.tohoho-web.com/python/index.html

http://qiita.com/ozw_sei/items/b45e316fced8aec9a97e

　
　
　　
死ねカス

Array.push()、Array.pop()があるんね
>>568で済む内容を、ループで書きたかったら↓しなければならない

def loopHoge2(term,arg...)
　while term
　　pushargstack(arg...)
　　dobefore(arg...)
　　if term
　　　next
　　end
　　popargstack(arg...)
　　doafter(arg...)
　end
end

stk = Array.new()

def pushargstack(arg1...argn)
　stk.push(arg1)
　...
　stk.push(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop()
　...
　arg1 = stk.pop()
end

def recHoge2(term,arg1...argn)
　dobefore(arg1...argn)
　if term
　　recHoge2(term,arg1...argn)
　end
　doafter(arg1...argn)
end
↑は、こう↓書き換えられる
def loopHoge2(term,arg1...argn)
　while term
　　pushargstack(arg1...argn)
　　dobefore(arg1...argn)
　　if term
　　　next
　　end
　　popargstack(arg1...argn)
　　doafter(arg1...argn)
end
end
stk = Array.new()
def pushargstack(arg1...argn)
　stk.push(arg1)
　...
　stk.push(argn)
end
def popargstack(arg1...argn)
　argn = stk.pop()
　...
　arg1 = stk.pop()
end

#同色上書き塗りつぶし
def refill(dest,src,x,y,color,minx,miny,maxx,maxy)
　if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
　　return
　end
　dest[y][x] = color
　#上
　if (src[y-1][x] == color) && (dest[y-1][x] != color)
　　refill(dest,src,x,y-1,color,minx,miny,maxx,maxy)
　end
　#左
　if (src[y][x-1] == color) && (dest[y][x-1] != color)
　　refill(dest,src,x-1,y,color,minx,miny,maxx,maxy)
　end
　#下
　if (src[y+1][x] == color) && (dest[y+1][x] != color)
　　refill(dest,src,x,y+1,color,minx,miny,maxx,maxy)
　end
　#右
　if (src[y][x+1] == color) && (dest[y][x+1] != color)
　　refill(dest,src,x+1,y,color,minx,miny,maxx,maxy)
　end
end

↑のループ等価が↓

stk =Array.new()
#同色上書き塗りつぶし
def loop_refill(dest,src,x,y,color,minx,miny,maxx,maxy)
　term = 0
　while !((x < minx) || (maxx < x) ||(y < miny) || (maxy < y))
　　dest[y][x] = color
　　#上
　　if (term < 1) && (src[y-1][x] == color) && (dest[y-1][x] != color)
　　　term = 0
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　y = y - 1
　　　term = 0
　　　next
　　end
　　#左
　　if (term < 2) && (src[y][x-1] == color) && (dest[y][x-1] != color)
　　　term = 1
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　x = x - 1
　　　term = 0
　　　next
　　end

　　#下
　　if (term < 3) && (src[y+1][x] == color) && (dest[y+1][x] != color)
　　　term = 2
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　y = y + 1
　　　term = 0
　　　next
　　end
　　#右
　　if (term < 4) && (src[y][x+1] == color) && (dest[y][x+1] != color)
　　　term = 3
　　　stk.push(x)
　　　stk.push(y)
　　　stk.push(term)
　　　x = x + 1
　　　term = 0
　　　next
　　end
　　term = stk.pop()
　　y = stk.pop()
　　x = stk.pop()
　end
end

再帰関数を無理矢理ループで書くことが
正解だなんてとても思えないんだけど・・・

>>575-577
はdestにcolorが最初から使われていると、それ以上塗れないバグがあるな
ま、いいか

destはコピー先だからそういう条件でクリア済みってことで

2色必要だった・・・
srcのx,yからcolor2の連続部分をdestにcolor1で塗りつぶし
#同色上書き塗りつぶし
def refill(dest,src,x,y,color1,color2,minx,miny,maxx,maxy)
　if (x < minx) || (maxx < x) ||(y < miny) || (maxy < y)
　　return
　end
　dest[y][x] = color1
　#上
　if (src[y-1][x] == color2) && (dest[y-1][x] != color1)
　　refill(dest,src,x,y-1,color1,color2,minx,miny,maxx,maxy)
　end
　#左
　if (src[y][x-1] == color2) && (dest[y][x-1] != color1)
　　refill(dest,src,x-1,y,color1,color2,minx,miny,maxx,maxy)
　end
　#下
　if (src[y+1][x] == color2) && (dest[y+1][x] != color1)
　　refill(dest,src,x,y+1,color1,color2,minx,miny,maxx,maxy)
　end
　#右
　if (src[y][x+1] == color2) && (dest[y][x+1] != color1)
　　refill(dest,src,x+1,y,color1,color2,minx,miny,maxx,maxy)
　end
end

>>576-577
も同様に直してね

recHoge2(term,arg1...argn){
　dobefore(arg1...argn);
　if(term)recHoge2(term,arg1...argn);
　doafter(arg1...argn);
}
この↑再帰関数を無理矢理
loopHoge2(term,arg1...argn){
　while(term){
　　pushargstack(arg1...argn);
　　dobefore(arg1...argn);
　　if(term){continue;}
　　popargstack(arg1...argn);
　　doafter(arg1...argn);
　}
}
ループで書くのはpushargstack()popargstack()書くのもだし
再帰関数でreturnされた時の箇所で
制御をdoafter()に飛ばすように考えるのもめんどくさい
つまり、再帰関数の構造化の部分までなんでわざわざ
コーディングする必要があるのか謎

そうだね、グリーンだね。

任意の再帰はスタックを使えばループに書き直せるし、任意のループは末尾再帰で書き表せるけど
書きやすい方で書いたら良いんじゃない？
配列を舐めるだけのループをわざわざ再帰で書く必要はないし、
二分木を舐めるだけの再帰をわざわざループで書く必要はない。
勿論例外は幾つもあるけどね。

死ね　→　NAS6 ◆n3AmnVhjw

>>585
語彙少なすぎだろ

時間とフィンガーポイントを無駄にしたくない

ばいばい

MPC

>>589
時間とフィンガーポイントを無駄にしない為に今すぐ2chから立ち去るんだ！
さぁ早く！

またuyが言い負かされてると聞いて

http://kakaku.com/item/K0000791258/
これを使ってるけど打ちにくい
隙間にゴミが入りにくいキーボードで何か探してくれれば長文レス出来るけど
ゲームもやるから同時押しが出来ないキーボードは使えないんだよ
バッファローのこのキーボード系列は
何故かゲーミングキーボードでもない癖にかなりの同時押しが出来る
お前らもこれくらい社会の役に立ってくれ

長文レスなんざしなくていいから死ね

ゲームなどという恥ずかしいご趣味をお持ちのようで

tail callはrecursive callと直行する概念だと理解してないのが何人かいるな

直行てなんやねんｗてのが何人もいるな

読みやすい方で書いたらいいんちゃうの？
無理にループにしてソース長くしてテスト項目増やす奴の気がしれんわ

取り敢えずutがカスだってのは旗から見てわかった

補足しておくけどループで済むものを再起にしろと言ってるわけではないからな

そりゃrecursiveじゃないtail callなんざ幾らでもあるわ

流し

仮にもプログラマならHHK使ってます自慢くらいしろよっていう

そういう俺はreal forceだけど。

>>595
まっすぐ行ってどうすんねん…

ワロタ

芸能界で生きていけるレベルの芸だな。

自分はプログラマじゃないんだよ
目的を最高効率で達成する事を念頭に置いてるスクリプトキディだ

そして複数人でプログラムを組むときに必要なノウハウなんて持ってない
そもそも自分はそういう事をしなくて良いから、生きてく上で必要無い配慮だから
周りが読みにくいとか知った事ではないし

身分がちげーんだよカス

スクリプトキディの意味も知らないのな

（他人の作った）スクリプトを使うしか能の無いお子様

正しく自分のこと理解してるということでいいのかもしれないですね。

正しく自分を理解していたら、あんなバカな生態を晒し続けるわけが無い

スクリプトキディとは、他人の作ったスクリプトでいたずらしてはしゃぐお子様の事だね

にちゃんに

誤送信

2ちゃんに書き込んでる地点で効率最悪といえる

地点？

数学的な再帰定義関数は好き
プログラムの再帰定義は多少罪悪感が

身分は再起する

>>605
読みやすさを考慮しなくていいとか言うなら、ソースあげんなksが

まともなプログラムは再帰使わないて
Javaじゃ標準でhashでもvisitorでも使ってるやん
初心者かな？

>>615
ウェブサイトがハッキングされるのはそのせいかもしれませんね。

ワロタ
何別人ぶってるんだコイツ

Javaがまともじゃないとか何様だよ

Haskellを知ればJavaなんぞ子供のおもちゃにも及ばない。

でも　cloujure が気になるのです‥

データベース扱いにくいゴミ

データベースは扱いにくいゴミだそうです。

いや、もしかしたら
データベースを扱うのに困難を伴うゴミ人間って意味かも

もしかして、もしかしてだけどさ、Haskelのこと言ってるんじゃね？

Haskellほどデータベース扱いやすい言語も少ないからそれはない

世界一のデータベースを持つと言われるGoogleがHaskellで動いているくらいだからね。

Haskellって実用で使われてんのかｗ
おもちゃかと思ってたわｗ

おもちゃだよ
Googleのおもちゃ

この世はおもちゃで十分

2ちゃんは漏れらのおもちゃ

漏れらとか使う香具師久しぶりに見たわ

イッテヨシとかギコはにゃーんとかもう死語なんだろうな。
ゴルァはまだありかな。

ヌルポにはガッっていうのはなぜだったのか理由がいまだに判らないので
香具師にどう反応すればいいのかも判らない

>>633
ぬるぽにかぎらず、例外発生したら、ガッ！

>>633
NullPointerExceptionをぬるぽと呼ぶスレだかなんだかいうスレタイのスレが立った2分後に
2が1にガッしたから

だった筈

ヌルポ

たたき続けなさい
さすればヌルポは失せるでしょう

>>636
catch

>>638
ガッてキャッチのことだったの?

>>638
そしてスローせず

ガッはガッチャの略だろ。　ガッチャマンでお馴染みのガッチャはI have got you.の略で捕まえたとかの意味。

でもアメリカのドラマ見てると了解するときにガッチャ！って言ってるよね。
特にチャーリーズエンジェルのカエル顔が（別のドラマでも）言ってるような気がする。

再帰使うとエラーの予測が立てにくい

それ再帰のせいじゃなくてもともと難しいアルゴリズムなんじゃ

再帰の方が簡単に難しいアルゴリズムを作れる

同じコードでも言語やバージョンの違いで即死する可能性があるのがネック。
可能ならwhileにするよ。
どうでもいいスクリプトなら木にしないけど。
べ、別に再帰関数苦手なわけじゃないんだからね！

再帰否定する奴は局所変数も否定すんの？

再帰否定派は生きるのがつらいんだよ
いつも周りのもの何もかも否定してるよ

無限か有限かを判別するだけでも難しい再帰コールが簡単に作れるからな

ループなら無限か有限か簡単に判別できるとでも？

再帰の方が簡単に作れる

例えば再帰を使えばC++149文字で数学的に非常に判別が難しいコードが作れる
ステップ数がF_φ_ω(0) (n)のオーダー
再帰を使わないともっとずっと必要な文字数は増える

つまり再帰を使うと簡単に分かりにくいコードが書けてしまうというアピール

アホなのこいつ？

まともなプログラマーしかいなけりゃ問題ないよ

適材適所

まぁ、ループは現代ではほとんど高階関数に置き換えられてはいるが

そうか？

再帰、ループ、高階関数は互いに別カテゴリーの概念だけどな。

>ループは現代ではほとんど高階関数に置き換えられてはいるが

mapとかfoldって言いたいの？

ファンクショナルのことだろ

Yコンビネータの事かも

最近の言語は分かり易いから好んで使う人多いみたいだね。

俺はダメだわ。単純な再帰でもアセンブラ時代の間接修飾と再帰を混合で使ってたときのトラウマが・・・

スタック使うから組み込みでは禁則かな

末尾呼びにすればぁ？

無理して使う物ではないのは、確か。

今更だけどアッカーマンの展開ループです
https://ideone.com/dKocyf

これループに直せません？
https://ideone.com/Ub1M86

>>665
ループ，というよりは map によるメモ化を先にするべきかと思う

アッカーマンメモ化はやめとけ
メモリ使用量がシャレにならん。
小さい引数ならいいけど。

と思ったけどスタック消費量は逆に減る？
よくわからんくなってきた。

>>668
アッカーマンはメモ化意味ない

しかしヤッターマンならきっとやってくれる

>>669
それはありえない．
アッカーマン関数にメモ化は有用な手段
http://echo.2ch.net/test/read.cgi/tech/1434079972/14

メモ化とかメモリリークしてるに等しい欠陥技術でしょ。

>>672
fjの昔からの議論をここで蒸し返しますか？

再帰というソフトにはスタックというハードがあるけどほかのソフトをハードで実装するのはどうなの？
ＧＣとかハードで実装してまったくフリーズなしに出来ないの？

int main(){return main();}

とあるRubyスクリプトだけどこれと等価のＣ書けんの？

$f=lambda{
print "f";
return $g
}

$g=lambda{
print "g"
return $f
}

a=$f
10.times{a=a.call}

rubyはcで書かれているんやで知らんかったやろ？

そういう等価じゃなくて文法的にというか。
Cだと$fと$gの型をどうしていいかわからん。

グローバル変数じゃなくてもこれでいけるっぽい

g=nil

f=lambda{
print "f";
return g
}

g=lambda{
print "g"
return f
}


a=f
10.times{a=a.call}

typedef void *(*F)()でいいやんけ

まじで
やってみる

やりかたわからん。
コンパイル通るソースプリーズ

これでいけるやろ
#include <stdio.h>
typedef void *(*F)();
void *f();
void *g();
void *f()
{
puts("f");
return g;
}
void *g()
{
puts("g");
return f;
}
int main()
{
int i;
F func;
func = f;
for (i = 0; i < 10; ++i)
func = func();
return 0;
}

g++だとエラーになるんだが。
コンパイラは何で確認した？

なんでいきなりg++やねんw
これ以上はcの質問スレでもいって聞けタコ

なんだ、結局コンパイル通ってないのか

通るわアホw
つーかそんなレベルでよくその質問出来るなお前

だからコンパイラは何つかったんよ。
こっちでも確認するから教えれ。
有料コンパイラだったら諦めるけど。

まあ、Ｃ質問スレにもマルチしてみるわ

>>684
ここではうまくいく
http://codepad.org/vXykoc8I

>>690
ふーむ確かに。
コンパイラがC++だといかんの？

キャストすればいいのか

しかしvoid * はなにか負けたような気分になるなｗ

キャストが嫌ならちゃんと型定義すればいいじゃん
と思ったがちゃんとやるには自己参照型定義みたいなのが必要になるのか
Cでそれってできるのかな

関数型Fのポインタを返す関数型をFと定義

>>694
そう、それ！
俺もそれで悩んだ。

お前はその前に悩むべき問題が山程あるだろｗ

voidにキャストがどうのって、rubyでコード書くような奴に言われてもなぁ。

>関数型Fのポインタを返す関数型をFと定義

これ定義できる静的型言語ってあるの？
それとも本質的論理的に矛盾した型であって、どうやっても定義できないの？

Forループは正直見た目が汚らしい
場合にもよるんだろうけど、再帰で書けるならそっちのほうがコードが綺麗になる

いかにもルビイバカらしい考え方だな

なんでルビイなんだ？
ハスケルバカならまだわかるが。

るびいもはすけるもよく知らないんでしょ

Y = λf.(λx.f (x x)) (λx.f (x x))　

#include<stdio.h>
char*s="#include<stdio.h>%cchar*s=%c%s%c;main(){printf(s,10,34,s,34);return 0;}";main(){printf(s,10,34,s,34);return 0;}

ピクセルシェーダーで再帰関数使えるようになるのはいつだろうか

CPUがGPU化するのが先かGPUがCPU化するのが先か。
まあ超並列プログラムは憧れるけどね。

main = putStrLn $ q ++ show q where q = "main = putStrLn $ q ++ show q where q = "

超並列はどうしてもデータレースが怖いからハードウェアトランザクションは必須だな

ツクツクボウシの鳴き声を一番正確に表せた奴が優勝 [無断転載禁止]©2ch.net

1 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:01:56.231 ID:EVnE4ji20
ツクツクボーシッ！！！！ツクツクボーシッ！！！！ツククツ、ツククククククク……！！！
ｱｯ　ヴィーナス！！！！　ヴィーナス！！！！ヴィヴィヴィヴィッ！！！！！

8 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:05:05.180 ID:rZ8gq0650
ツクツクホーシ！ツクツクホーシ！ッツクツク、ツクツクホーシ！
ッ！ツクツクヴィーヨー！ツクツクヴィーヨー！ツクツクツクツクアアアアｱﾞｱﾞｱﾞｱﾞｱﾞ…天

12 ：以下、無断転載禁止でVIPがお送りします：2016/04/28(木) 08:24:50.425 ID:SYCMGSQFa
ツクツクウィーヨーンｗｗｗｗｗｗツクツクウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗウィーヨーンｗｗｗｗｗｗあああああああああああああああ あ！！！！！！！

GitHubで匿名通信（Tor、i2p等）ができるBitComet（トラッカーサイト不要でDHTだけで日本語検索可能）
みたいな、BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al

ちなみにオイラはCovenant(純粋P2Pのファイル共有ソフト)の完成が待ち遠しいプログラミングできないアスペルガーｗ
q

匿名通信（Tor、i2p等）ができるファイル共有ソフトBitComet（ビットコメット）みたいな、
BitTorrent（Covenant）が活発な情報交換・交流コミュニティでオープンソース開発されています（プログラマー募集中）

言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？

Covenantの作者（Lyrise氏）がそういう人と話したいそうなので、よろしければツイートお願いします<(_ _)>
https://twitter.com/Lyrise_al

ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできない情報発信好きアスペルガーｗ


The Covenant Project
概要

Covenantは、純粋P2Pのファイル共有ソフトです

目的

インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します

特徴

Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)

接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
ｔ

眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる

アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの？

チューリングマシンになる

証明：以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。

# ツッコミ待ち

突っ込み待ちというかそんなに間違ってなくない？

なんで再帰がどうこうで喧嘩してるんだこいつらw

グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。

女性限定、恋愛相談サイトオープン。
4000名のイケメンカウンセラーが在籍中♪

自己紹介動画はいつでも見放題です！

メンガ　って検索してください
※本当のサイト名は英字です

最近再帰好きだわ

ダジャレ？

>>719
そう言う時期が俺にもあったな...（遠い目）

再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや

再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない

import Data.Function (on)
import Data.List (concatMap, groupBy)
main =
    let (f:r) = mypi 2 4 1 12 4
        s = slice 5 $ slice 10 $ concatMap show r
    in putStrLn (show f ++ ".")
       >> putStr (unlines $ map unwords $ take 200 s)
slice :: Int -> [a] -> [[a]]
slice n ls = let q = concatMap (replicate n) [0..] :: [Int]
             in map (map snd) $ groupBy ((==) `on` fst) $ zip q ls
mypi :: Integer -> Integer -> Integer -> Integer -> Integer -> [Integer]
mypi k a b a1 b1 =
    let p = k * k
        q = 2 * k + 1
        a' = a1
        b' = b1
        a1' = p * a + q * a1
        b1' = p * b + q * b1
        loop a a1 d d1 =
            if d == d1 then
                d : let a' = 10 * (a `rem` b' )
                        a1' = 10 * (a1 `rem` b1')
                    in loop a' a1' (a' `quot` b') (a1' `quot` b1')
            else
                mypi (k + 1) a b' a1 b1'
     in loop a' a1' (a' `quot` b') (a1' `quot` b1')
えんしうりつを100まんけたひょうじする

パイ焼きか？
何秒で計算できんの？

$ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた

深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。

幅優先探索の絶対見つかる感は異常

まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど