X



なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
0001デフォルトの名無しさん2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる?
0863デフォルトの名無しさん2019/03/22(金) 06:20:32.16ID:t/nkQ3ne
リストに対してはクイックソートやマージソートより選択ソートや挿入ソートのが速かった。
ケースによって使い分けるために色んなソートがあるんだなと実感した。
0864デフォルトの名無しさん2019/03/22(金) 18:03:42.63ID:GIrPmH5o
どうゆう状況でそんなことが起こるのか想像できない
0866デフォルトの名無しさん2019/03/22(金) 23:38:43.20ID:bs44Fjbm
>>861
ループと再帰とは違うよ
更に言えば高階関数があればループも再帰も必要ない
不動点演算子もループも再帰だと言うのはナンセンスだ
それは「再帰と同じだ」と君が思うものを再帰と呼ぶ、と主張しているに等しい
こんな君だけの主観による再帰の定義では議論にならない
0867デフォルトの名無しさん2019/03/23(土) 01:46:30.69ID:05rjzlE7
チューリング完全なんだからどの言語でも一緒、という暴論と同程度に「ループと再帰は同じ」も暴論
コンピュータからみた話じゃなくて、プログラムを書く人にとってループと再帰が同価値なのかが問題になる
自分は、複雑でも読み溶ける再帰の方が好き。ループが複雑になると、どの変数がいつのどの値を持っているのか追いきれなくなる
再帰で同程度に複雑な処理を書くと、引数の数やら名前からすぐにヤバイ臭いがするんでそんなに腐らない
0869デフォルトの名無しさん2019/03/23(土) 04:46:27.26ID:abrpiqJH
モナドな再帰(IOモナドやリスト->リストな再帰)は単純な再帰でもスタック消費しない。
繰り返しコードの単純さは再帰>末尾再帰>=ループ。
0870デフォルトの名無しさん2019/04/03(水) 19:48:29.75ID:mixCZYtf
非同期処理の終了を待って、次の繰り返しを行う
再帰でなければ書けない
0872デフォルトの名無しさん2019/04/04(木) 16:23:32.66ID:GBwqjObH
>>871
非同期処理の終了はイベントやコールバックで通知されるものとする
終了を待つ同期プリミティブは存在しない

Javascriptだとこれが普通で、繰り返しでは書けない
0874デフォルトの名無しさん2019/04/05(金) 00:21:14.27ID:ZWKOySqx
async/await が JavaScript の新しい仕様として入ったのも知らんのか
0875デフォルトの名無しさん2019/04/05(金) 12:13:43.00ID:dQkyjbHg
await/asyncの仕組みを知らないと見える
それ使って、繰り返しで書いてみなよ
0878デフォルトの名無しさん2019/04/15(月) 22:24:35.37ID:SVQji9la
>>867
違うよ
柴犬にこっちは太郎でこっちは次郎だから別の犬だ、と言ってるのと同じ
0880デフォルトの名無しさん2019/06/19(水) 05:49:29.73ID:K5sVxx6Y
再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。

再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。

普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する
0883デフォルトの名無しさん2019/07/31(水) 11:07:40.57ID:w173sz60
ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい
0888デフォルトの名無しさん2021/01/11(月) 13:49:06.57ID:nJc/cTVc
λf . (λx . f (x x)) (λx . f (x x))
0889デフォルトの名無しさん2021/01/13(水) 14:49:33.89ID:tLUt5qTN
ループで書くと出現する余計な変数がなくなるのが再帰のメリット
0890◆QZaw55cn4c 2021/01/13(水) 21:38:42.47ID:DfoNX22P
>>889

kwsk
ループ変数は再帰関数でも必要なのでは?
0891デフォルトの名無しさん2021/01/14(木) 06:32:41.62ID:7/cCpBde
どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど
0892デフォルトの名無しさん2021/01/27(水) 21:57:40.49ID:fE6h5Ua/
再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。
0893デフォルトの名無しさん2021/01/28(木) 02:47:34.69ID:ggjwGOj3
CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが
0894デフォルトの名無しさん2021/01/29(金) 03:09:35.61ID:5NtPwDh4
今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど
0895デフォルトの名無しさん2021/07/16(金) 14:24:10.16ID:S3gddm5/
>>890

要らない

/* n の階乗を求める */
int fact(int n)
{
 if(n==0){
  return 1;
 } else {
  return fact(n-1);
 }
}

実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。
0897デフォルトの名無しさん2021/07/19(月) 22:18:11.50ID:hlpOkuZF
くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ
0898デフォルトの名無しさん2021/07/22(木) 20:45:12.08ID:sSLTRpJ4
最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ?
0899ハノン ◆QZaw55cn4c 2021/07/25(日) 23:45:12.36ID:rUybnQpf
>>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない
0902デフォルトの名無しさん2021/10/02(土) 16:12:27.49ID:qz0ghb/n
>>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが

ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました
0903ハノン ◆QZaw55cn4c 2021/10/02(土) 20:52:53.81ID:7AkA9F3V
>>902
scheme の継続渡しに関係しますか?
キーワードありがとうございます
0904デフォルトの名無しさん2021/10/04(月) 21:48:56.27ID:tW+d3xqB
>>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで
0906デフォルトの名無しさん2022/09/07(水) 22:59:05.75ID:hj8+EGae
すき

しかし再帰絶対書かないマンが思いの外多くて草生えるわ

末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん

再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変
0907デフォルトの名無しさん2022/09/08(木) 09:28:47.03ID:JEMfdspa
スタックとヒープは別物
共有してるアーキテクチャもあるが
0908デフォルトの名無しさん2022/09/08(木) 13:02:30.59ID:o4zCWVHV
ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。
0910ハノン ◆QZaw55cn4c 2022/09/11(日) 14:15:38.74ID:gVwBfSXr
>>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね
0912デフォルトの名無しさん2024/01/02(火) 13:18:51.50ID:yx0oLXiq
再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする

こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A
0913デフォルトの名無しさん2024/01/04(木) 11:34:09.71ID:iR4GsMlV
何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ
レスを投稿する

レス数が900を超えています。1000を超えると表示できなくなるよ。

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