なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
匿名通信(Tor、i2p等)ができるファイル共有ソフトBitComet(ビットコメット)みたいな、
BitTorrent(Covenant)が活発な情報交換・交流コミュニティでオープンソース開発されています(プログラマー募集中)
言語は何でも大丈夫だそうなので、P2P書きたい!って人居ませんか?
Covenantの作者(Lyrise氏)がそういう人と話したいそうなので、よろしければツイートお願いします<(_ _)>
https://twitter.com/Lyrise_al
ちなみにオイラはCovenantの完成が待ち遠しいプログラミングできない情報発信好きアスペルガーw
The Covenant Project
概要
Covenantは、純粋P2Pのファイル共有ソフトです
目的
インターネットにおける権力による抑圧を排除することが最終的な目標です。 そのためにCovenantでは、中央に依存しない、高効率で検索能力の高いファイル共有の機能をユーザーに提供します
特徴
Covenant = Bittorrent + Abstract Network + DHT + (Search = WoT + PoW)
接続は抽象化されているので、I2P, Tor, TCP, Proxy, その他を利用可能です
DHTにはKademlia + コネクションプールを使用します
UPnPによってポートを解放することができますが、Port0でも利用可能です(接続数は少なくなります)
検索リクエスト、アップロード、ダウンロードなどのすべての通信はDHT的に分散され、特定のサーバーに依存しません
t 眠い時にプログラム書いてたら1つの関数の中にこれでもかと再帰を詰め込んだモンスター関数を書いてしまって訳が分からなくなる アッカーマン関数はただの再帰じゃないらしいけど、
再帰のパワーを究極まで高めたら何になるの? チューリングマシンになる
証明:以下より明らか
・再帰を用いて、スタックとループをそれぞれ構築できる
・スタック2つとループを用いて、チューリングマシンを模倣できる
・故に、再帰の能力はチューリングマシン以上である。
・一方で、チューリングマシンを用いて再帰を表現出来る
・よって、再帰はチューリングマシンと等価である。
# ツッコミ待ち グッドスタイン数列というのがペアノ算術の限界を超えた再帰という話があるらしいのだが、詳しいことはよくわからない。
でもロマンを感じる。 女性限定、恋愛相談サイトオープン。
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のソースについてるやつから持ってきた 深さ優先探索より幅優先探索が好きだ。
重複がある場合計算量が深さより有利だし、
メモリモリモリ積んでゴリゴリ問題を制覇する感じがたまらない。 まだ再帰一回しか使ったこと無いな。
ループでもよかった感じしたけど ディレクトリ掘っていく処理なら再帰の方がすっきり書ける
それ以外使ったこと無いけど flattenがあると再帰書かなくて済むことがまれによくある。 超簡単なハノイの塔のコードを
理解出来ない奴らばかり
俺様ステキ
再帰は楽しい ハノイの塔って最初誰が考えたんだろなw
まさに再帰のための問題だよなw >>737
エドゥアール・リュカ/1800年代後半 連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ? 数学のように条件を書くだけで処理が書けるのは楽しい >>741
では
これの値を教えてください
lim[n->∞]sin(πen!)
わりとまじです void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。 昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ int main()
{
return main();
} 再帰は面白いと思ってた時期もあった気がする。
ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか ただのループでスタックオーバーフローの心配はないからなぁ x 再帰はループの一つ
x ループは再帰の一つ
o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる >>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。 再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する >>758
あー、ループあるな。そういう意味では。
すまんかった。 >>755
再帰と同じようにループを実装すればオーバーフローしますけど。
>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。
ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。
まずこうゆうときは、E(電力)あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。
再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。 >>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ? 分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね 再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。 スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。 >>767
int main(){ return main(); } 簡単です C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに >>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。 >>770
C++で、クラス内に関数を定義すりゃいいだけ >>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。 >>770
なるほどね,コンパイル単位内だけで末尾再帰を保証するわけだね >>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か 木構造をループで辿りたいときってスタック使わずにできる? 辿るだけ(構造を保持しなくていい)ならできるでしょ
たとえば全てのアドレスを出すだけとか スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。 ツリーだってメモリがツリー状になってる訳じゃない罠 質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない
意味不明 >>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな >>786
ニーハオ!
モドル サキ ハ ドコニ キヲク シマスカ? ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。 馬鹿には永遠に判らんだろうけど。 情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。 誰かの口真似したのかもしれないけどそれは完全に間違ってますよ >>796
Prologですから再帰述語で関数ではありませんが、
repeat :- 割り込みあり,!.
repeat :- repeat.
の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。 すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。
repeat.
repeat :- repeat. >>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。 >>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。 >>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。 好きか嫌いかで言ったら好きだ
趣味以外では使わないけど 再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの?
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの? >>806
ループで実現したときはスタックに積まれない。 >>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒 抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。
抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。