X

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

0001デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
0759デフォルトの名無しさん
垢版 |
2016/11/10(木) 18:03:12.84ID:gVGtx90I
再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する
0761デフォルトの名無しさん
垢版 |
2016/11/10(木) 19:18:34.28ID:bdp7hkfZ
天才じゃないから再帰使うわ
0762デフォルトの名無しさん
垢版 |
2016/11/10(木) 19:25:25.72ID:Him+SRv0
>>755
再帰と同じようにループを実装すればオーバーフローしますけど。

>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。

ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。


まずこうゆうときは、E（電力）あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。

再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。
0764デフォルトの名無しさん
垢版 |
2016/11/11(金) 06:56:11.81ID:wvSdzlse
>>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ？
0765デフォルトの名無しさん
垢版 |
2016/11/11(金) 07:27:43.35ID:xeUlHUrh
分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね
0767デフォルトの名無しさん
垢版 |
2016/11/11(金) 07:54:13.90ID:iDJmU8Gv
再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。
0768デフォルトの名無しさん
垢版 |
2016/11/11(金) 08:11:51.46ID:xeUlHUrh
スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。
0770デフォルトの名無しさん
垢版 |
2016/11/11(金) 11:06:28.50ID:4NXZomhC
C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに
0772デフォルトの名無しさん
垢版 |
2016/11/11(金) 12:05:55.04ID:KJb+NHX6
>>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。
0777デフォルトの名無しさん
垢版 |
2016/11/11(金) 20:38:07.10ID:7sFk++lS
>>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ
0778デフォルトの名無しさん
垢版 |
2016/11/12(土) 15:29:28.13ID:vO6QCHLM
コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か
0780デフォルトの名無しさん
垢版 |
2016/11/13(日) 23:46:50.63ID:qpRTYVIa
辿るだけ（構造を保持しなくていい）ならできるでしょ
たとえば全てのアドレスを出すだけとか
0781デフォルトの名無しさん
垢版 |
2016/11/14(月) 09:15:00.34ID:qrJVzCCo
スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。
0783デフォルトの名無しさん
垢版 |
2016/11/15(火) 06:36:20.67ID:HcDSv4MP
質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない

意味不明
0791デフォルトの名無しさん
垢版 |
2016/11/16(水) 02:58:25.42ID:fzskfnoe
codepadって年はでないのか
0792デフォルトの名無しさん
垢版 |
2016/11/16(水) 22:36:41.79ID:1lDDb3P+
ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。　馬鹿には永遠に判らんだろうけど。
0793デフォルトの名無しさん
垢版 |
2016/11/17(木) 11:34:22.18ID:u2Ucvcf0
情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。
0795793
垢版 |
2016/11/17(木) 11:44:39.48ID:u2Ucvcf0
>>794
上の行？ 下の行？ それとも両方？
0797793
垢版 |
2016/11/17(木) 13:03:18.99ID:u2Ucvcf0
>>796
Prologですから再帰述語で関数ではありませんが、

repeat :- 割り込みあり,!.
repeat :- repeat.

の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。
0798797
垢版 |
2016/11/17(木) 13:06:35.00ID:u2Ucvcf0
すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。

repeat.
repeat :- repeat.
0799793
垢版 |
2016/11/17(木) 13:16:05.70ID:u2Ucvcf0
>>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。
0800デフォルトの名無しさん
垢版 |
2016/11/21(月) 07:42:33.65ID:Z9LRReIl
>>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。
0801デフォルトの名無しさん
垢版 |
2016/11/21(月) 09:29:48.04ID:IXIwDt6r
>>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。
0806デフォルトの名無しさん
垢版 |
2016/11/22(火) 08:09:17.87ID:sAluFFeZ
再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの？
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの？
0811デフォルトの名無しさん
垢版 |
2016/11/22(火) 13:48:40.05ID:sAluFFeZ
抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。

抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。
0813デフォルトの名無しさん
垢版 |
2016/11/26(土) 09:43:28.08ID:cQHpTyuw
>>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか？
0814813
垢版 |
2016/11/26(土) 09:45:28.00ID:cQHpTyuw
すみません。最後
こういうことを「実体」というのではないか？
です。
0819デフォルトの名無しさん
垢版 |
2016/12/22(木) 22:15:49.61ID:vkr4xxpW
継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の１割に満たないんだろうな。
0823デフォルトの名無しさん
垢版 |
2017/02/11(土) 02:50:31.54ID:JwDD7IDr
私は再帰の塊のようなプログラムを作ったことがある。
DirBaseだ。
起動後のウィンドウにエクスプローラからファイルやフォルダを
ドラグ＆ドロップするだけで簡単にツリーができる。
DirBaseで検索すれば、ダウンロードできる。
0825デフォルトの名無しさん
垢版 |
2017/02/16(木) 15:31:02.48ID:VWTLMYuE
競プラではforループが盛んらしいが、言語開発者としては再起の方が使って欲しい
ソースは俺が今朝見た夢
0828デフォルトの名無しさん
垢版 |
2017/10/03(火) 20:26:43.27ID:GaATZUfo
(数値計算を主体とする)関数では使わないけど、
再帰ルーチンで使用頻度が激しいのは、外部記憶装置を含めた初期化ルーチン。
一つのルーチンで、内部記憶(主記憶装置)と外部記憶(HDD等)の出入りを管理している場合に、
初期化ルーチンで外部記憶が存在しない場合には、ルーチンで保存している定数を読みだして、外部記憶に保存する。
初期化ルーチンからの定数の読み出し・外部への保存が再起処理。
初期化ルーチン以外では使わない手法。
分割して作成すると、何年か後に見直した時に、どのように初期化しているのかわからない、という事態になることが多発したので、
初期化が必要な場合には、このような手法で同一ルーチン内に収めるようにした。

もっとも一番利用頻度の高いのは、Winでは、ダイアログボックスのプロシージャ。再起の塊で、何をしているのかわからなくなってくる。
0829デフォルトの名無しさん
垢版 |
2018/01/28(日) 06:23:28.69ID:GN9YKPqU
再帰プログラムは関数の呼び出しで積みあがるスタックを配列とみなせば、ループアルゴリズムそのものだ。
0830デフォルトの名無しさん
垢版 |
2018/01/28(日) 06:51:19.47ID:GN9YKPqU
ファイルやフォルダ、ダイアログやウインドウは階層構造で構成されるので、再帰プログラムを使うのが一般的だ。
0831デフォルトの名無しさん
垢版 |
2018/01/28(日) 15:26:22.97ID:Erw8GBm0
再帰って何?って頃から普通に再帰使ってたからなあ。
自分自身を呼び出せば良いじゃんみたいな。

高校で数列とか演繹法が得意だったせいかも。
自然に使ってた。
0832デフォルトの名無しさん
垢版 |
2018/01/28(日) 16:28:26.35ID:C2Jb//yt
再帰云々言ってるのは大昔のFORTRANとかCOBOLを使ってた人ぐらいじゃないのかな
あと組み込みとかでスタックサイズが厳しい環境で組んでるとか
0834デフォルトの名無しさん
垢版 |
2018/01/28(日) 18:03:09.52ID:GN9YKPqU
再帰プログラムの基本はスタックにデータを入れ積み上げていく過程と、スタックからデータを取り出しスタックをクリアしていく過程の二つの動作しか基本的にない。
データを取り出したら、そのデータを使ってプログラミングされた処理を実行する。スタックはデータを貯めることと同時に処理の順番を決めている。再帰のプログラミングには二つの概念が必要だ。
0836デフォルトの名無しさん
垢版 |
2018/02/23(金) 11:23:42.25ID:cixhX8OH
javaで再起処理書いたらガーベッジコレクションが掃除してくれるもんだと思ってたけど違うの？
十年前の記憶だから曖昧ですまない
cpu使用率が100%になるけど影響ないから使ってます〜って顧客に言われたのを思い出したもんやで
0838デフォルトの名無しさん
垢版 |
2018/02/23(金) 12:18:58.87ID:E8zJnigo
影響ないなら気にすんな
0839デフォルトの名無しさん
垢版 |
2018/05/23(水) 20:21:54.46ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

980U0
0840デフォルトの名無しさん
垢版 |
2018/07/05(木) 01:23:47.56ID:RfoszcD2
TB1
0844デフォルトの名無しさん
垢版 |
2018/11/14(水) 23:02:37.97ID:ur2RK8H0
再帰アルゴリズムはなるべくライブラリで隠蔽して欲しいな。
自分で書くのはまだしも他人の再帰コードを読むのはかなり嫌。
0845デフォルトの名無しさん
垢版 |
2018/11/15(木) 12:26:32.11ID:yIPB3Fsn
好きなんか嫌いなんかハッキリしろや
0847デフォルトの名無しさん
垢版 |
2018/11/15(木) 16:22:56.36ID:zCiKr9uf
再帰関数と言えばアッカーマン関数とかたらい回し関数などが
有名ですが他にも何かある?
0848デフォルトの名無しさん
垢版 |
2018/11/15(木) 21:36:15.07ID:sS26qanx
有名じゃないからwどんな入りかたしたんおまえw
0849デフォルトの名無しさん
垢版 |
2018/11/16(金) 07:45:28.14ID:Q+Zstbtj
174 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:04:12.40 ID:N77Q/1ZeM
＞ドラゴンクエストの世界観が全く反映されていないような印象

　　　　ド　ラ　ゴ　ン　ク　エ　ス　ト　と　は　何　か　？

ドラゴンクエストとは何かを問い続けるのが、終わらないドラゴンクエストだろう？　違うか？

2 その名前は774人います (ﾊﾞｯﾄﾝｷﾝ MM5a-fW3D) 2018/11/16(金) 07:42:40.97 ID:N77Q/1ZeM
再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。
この例のおかげもあり、はじめは再帰関数なにそれ状態から、最後はしっかりと実装できるようになりました。再帰関数はPythonで実装しています。
https://qiita.com/jumpyoshim/items/20e6b5e70efa466699b4
0850デフォルトの名無しさん
垢版 |
2018/11/16(金) 23:40:45.23ID:HodhQ/sE
問) 再帰的にオマンコを定義せよ
0851デフォルトの名無しさん
垢版 |
2018/11/16(金) 23:59:40.68ID:xavUeX/s
再帰関数『終わらないドラゴンクエスト』

ドラゴンクエストとは？（）{
　　　ドラゴンクエストとは？（）
}
0852デフォルトの名無しさん
垢版 |
2018/11/17(土) 00:12:17.17ID:eQWBxdMf
正直小学生のガチネタにはついていけん
0853デフォルトの名無しさん
垢版 |
2018/11/17(土) 03:28:35.36ID:corCuJCM
def DQ(n)
　puts "DQ #{n}"
　DQ(n+1)
end
0854デフォルトの名無しさん
垢版 |
2018/11/17(土) 10:42:46.80ID:B4GISbTr
({})
0855デフォルトの名無しさん
垢版 |
2018/12/16(日) 22:50:52.23ID:EHgXXRnO
バブルソート中
0857デフォルトの名無しさん
垢版 |
2018/12/18(火) 11:28:45.03ID:/M0/bFGF
グロ中尉
0858デフォルトの名無しさん
垢版 |
2019/03/20(水) 19:02:56.05ID:DvYG4dOj
>>1
好き嫌いの問題じゃないと思うが、理論上再起かそれと同等の内部処理履歴を残さないと実現できない処理なら、使うだろう
再起にならざるを得ない具体的な数学（科学）的な条件は忘れたが、けっこう複雑な処理じゃない限り再起じゃなくても実現できたように思う
新着レスの表示
レスを投稿する

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