X
なあ、再帰関数好きな人いる？ パート3 [転載禁止]©2ch.net
0001デフォルトの名無しさん
垢版 |
2015/11/28(土) 18:51:38.86ID:Rc2MJzM/
なあ、再帰関数好きな人いる？
0710デフォルトの名無しさん
垢版 |
2016/04/30(土) 22:02:43.20ID:uVz81x78
GitHubで匿名通信（Tor、i2p等）ができるBitComet（トラッカーサイト不要でDHTだけで日本語検索可能）
みたいな、BitTorrentがオープンソースで開発されています
言語は何でも大丈夫だそうなので、P2P書きたい！って人居ませんか？
Covenantの作者（Lyrise）がそういう人と話したいそうなので、よろしければツイートお願いします
https://twitter.com/Lyrise_al

ちなみにオイラはCovenant(純粋P2Pのファイル共有ソフト)の完成が待ち遠しいプログラミングできないアスペルガーｗ
q
0711デフォルトの名無しさん
垢版 |
2016/05/04(水) 10:34:46.82ID:PLBcNQ3k
匿名通信（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的に分散され、特定のサーバーに依存しません
ｔ
0712デフォルトの名無しさん
垢版 |
2016/05/05(木) 20:47:26.30ID:a3JwFvV1
眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる
0713デフォルトの名無しさん
垢版 |
2016/05/09(月) 20:57:03.75ID:QYIZFGji
アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの？
0714デフォルトの名無しさん
垢版 |
2016/05/10(火) 14:12:08.45ID:zxnDb8j/
チューリングマシンになる

証明：以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。

# ツッコミ待ち
0717デフォルトの名無しさん
垢版 |
2016/05/11(水) 20:12:13.79ID:LnJQmy5e
グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。
0718デフォルトの名無しさん
垢版 |
2016/05/19(木) 19:24:04.68ID:eYV7veAj
女性限定、恋愛相談サイトオープン。
4000名のイケメンカウンセラーが在籍中♪

自己紹介動画はいつでも見放題です！

メンガ　って検索してください
※本当のサイト名は英字です
0719デフォルトの名無しさん
垢版 |
2016/06/19(日) 18:09:53.79ID:SmadYZ7Z
最近再帰好きだわ
0722デフォルトの名無しさん
垢版 |
2016/06/19(日) 21:07:57.12ID:OFyR5xSG
再帰で実装した方がスッキリするケースってなかなか出てこないから最近全く使ってないや
0723デフォルトの名無しさん
垢版 |
2016/06/20(月) 12:26:15.09ID:xPaMOXBK
再起なんてバグの温床だからなぁ
マインスイーパー作る時ぐらいしか使わない
0724デフォルトの名無しさん
垢版 |
2016/06/20(月) 19:47:38.77ID:YaidyggX
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まんけたひょうじする
0726デフォルトの名無しさん
垢版 |
2016/06/20(月) 23:52:55.90ID:YaidyggX
$ time ./pi >/dev/null
./pi > /dev/null 0.40s user 0.00s system 99% cpu 0.400 total
一瞬やね(最適化 -O)
ちなアルゴリズムはRubyのソースについてるやつから持ってきた
0727デフォルトの名無しさん
垢版 |
2016/06/27(月) 22:23:07.70ID:99UKpQvj
深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。
0729デフォルトの名無しさん
垢版 |
2016/07/18(月) 23:29:48.39ID:v2MXNS7u
まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど
0731デフォルトの名無しさん
垢版 |
2016/07/26(火) 07:11:59.49ID:HN1KCMsQ
ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど
0736デフォルトの名無しさん
垢版 |
2016/07/30(土) 22:01:40.05ID:v/rkDCKK
超簡単なハノイの塔のコードを
理解出来ない奴らばかり

俺様ステキ

再帰は楽しい
0737デフォルトの名無しさん
垢版 |
2016/07/30(土) 22:19:26.10ID:jcPMAjAY
ハノイの塔って最初誰が考えたんだろなｗ
まさに再帰のための問題だよなｗ
0739デフォルトの名無しさん
垢版 |
2016/07/31(日) 11:30:45.35ID:ea63k9Af
連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ？
0746デフォルトの名無しさん
垢版 |
2016/10/13(木) 18:46:47.08ID:Xwk5OgLP
void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。
0747デフォルトの名無しさん
垢版 |
2016/10/30(日) 02:58:18.76ID:oDMcv2JQ
斉木楠雄と再帰関数って似てるよな
0749デフォルトの名無しさん
垢版 |
2016/11/06(日) 03:07:23.35ID:gP4JS71d
昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ
0752デフォルトの名無しさん
垢版 |
2016/11/09(水) 21:10:33.07ID:5TPAUZWc
再帰は面白いと思ってた時期もあった気がする。

ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか
0756デフォルトの名無しさん
垢版 |
2016/11/10(木) 13:27:48.38ID:dxAJlx69
x 再帰はループの一つ
x ループは再帰の一つ

o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる
0757デフォルトの名無しさん
垢版 |
2016/11/10(木) 14:27:23.84ID:hh42qZlp
>>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。
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
再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの？
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの？
新着レスの表示
レスを投稿する

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