5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

再帰

1 :デフォルトの名無しさん:2001/06/11(月) 15:44
http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842

2 :デフォルトの名無しさん:2001/06/11(月) 15:46
再帰の意味も理解できないヴァカ発見!

3 :デフォルトの名無しさん:2001/06/11(月) 15:51
>>2
お前は再帰の意味がわかってるのか?
そうなら、是非解説してください。

ちなみに結構広い意味で使われてるのよ。
http://dictionary.goo.ne.jp/cgi-bin/dict_search.cgi?MT=%BA%C6%B5%A2&sw=2

4 :デフォルトの名無しさん:2001/06/11(月) 15:52
このスレどうやって立てたの??

5 :4:2001/06/11(月) 15:54
…と思ったら、hidden の中に時刻入ってるじゃん。なーんだ。

6 :デフォルトの名無しさん:2001/06/11(月) 15:59
>>2
自己参照も再帰の一種かと。

7 :1:2001/06/11(月) 16:04
>>4-5
でもタイミングが難しいのよ。

8 :デフォルトの名無しさん:2001/06/11(月) 17:17
>>2は基底がないと再帰じゃないと思っているとか。

9 :デフォルトの名無しさん:2001/06/11(月) 17:20
このスレは糞スレリサイクル法にもとづき、ただいまより
「再帰について語るスレ」と致します。

10 :デフォルトの名無しさん:2001/06/11(月) 17:23
>>4
どういうこと?未だにどうやって立てたのかわからん

11 :デフォルトの名無しさん:2001/06/11(月) 17:57
>>1の投稿時間を考えると、なかなか評価できるな

12 :11:2001/06/11(月) 17:58
って全然関係ねぇや<タイミング
むっちゃ簡単じゃんよ

13 :1:2001/06/11(月) 18:01
>>7の補足
>>5
hiddenの値がスレ番になるわけじゃないかと。
CGIがリクエストを受け付けた時刻っぽい。

14 :Nanasshy:2001/06/11(月) 18:08
One day a student came to Moon and said: "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons."

Moon patiently told the student the following story:

"One day a student came to Moon and said: `I understand how tomake a better garbage collector...

[Ed. note: Pure reference-count garbage collectors have problems with circular structures that point to themselves.]

15 :デフォルトの名無しさん:2001/06/11(月) 18:14
俺には、適当にスクリプトでも組んで、
適当なリクエストでサーバータイムとの差をms単位で算出してから、
余裕があるタイミングでポストする(ping値も参考にする?)
これ位しか、やりかたを思いつかない。

16 :デフォルトの名無しさん:2001/06/11(月) 20:58
1みたいな人が、ハッカーになるんでしょうね。

17 :11:2001/06/11(月) 22:31
>>13
ああそうなのか。疑ってスマソ

18 :デフォルトの名無しさん:2001/06/11(月) 23:18
再帰とゆーか、ループっちゃってGCできなくなっちゃった
リストとゆーか...

19 :1:2001/06/12(火) 12:58
>>16
虐めないでくれ…

20 :デフォルトの名無しさん:2001/06/16(土) 02:20
これも1だろ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241448
sageで立てたから気付かれなかったけど。

21 :デフォルトの名無しさん:2001/06/16(土) 02:36
これでテストしたんだな。8秒ずれ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241080

22 :デフォルトの名無しさん:2001/06/17(日) 15:28
すごい

23 :デフォルトの名無しさん:2001/06/17(日) 15:40
クソスレリサイクル法に従い再帰の話題をば

再帰を人に教えるのは難しい。
ハノイの塔とかグラフィックを使うのとかは相手のレベルが低いと辛いし。

24 :デフォルトの名無しさん:2001/06/17(日) 17:20
>>23
8クイーンじゃだめ?陳腐すぎますか?

25 :デフォルトの名無しさん:2001/06/17(日) 17:35
アッカーマソ関数は?

26 :デフォルトの名無しさん:2001/06/17(日) 17:35
>>23
まずクイックソートでおしえれよ

27 :23:2001/06/17(日) 17:42
>>24
いきなりバックトラックだとちょっといやかな、とは思ったんですが。
ディレクトリを奥まで探っていく感じのサンプルがいいんだけど、
伝えたい感覚わかるかな?

>>25
ネタだよね(藁

>>26
理解してもらえませんでした(涙)

28 :デフォルトの名無しさん:2001/06/17(日) 17:44
再帰的定義: GNU = "GNU is Not Unix!"
再帰的動作: function qsort(0,n) = qsort(0,n/2); qsort(n/2+1, n);

29 :デフォルトの名無しさん:2001/06/17(日) 17:46
CFGで教えるというのはどうか。

30 :デフォルトの名無しさん:2001/06/17(日) 17:51
無難に階乗とフィボナッチ

31 :デフォルトの名無しさん:2001/06/17(日) 17:59
ターミネーター2で最後、敵のロボが溶鉱炉に落ちて口から顔が出て
そのまた口から顔が出て来るのを見て再帰を理解しましたw

32 :デフォルトの名無しさん:2001/06/17(日) 18:01
&d('.');sub d{opendir D,$_[0];my@a=grep!/^\.\.?$/,readdir D;closedir D;
foreach(@a){printf"%".length($b="$_[0]\\$_")."s\n",$_;&d("$b")if(-d$b)}}

さぶでれくとり一覧を表示するperlスクリプト

33 :デフォルトの名無しさん:2001/06/17(日) 19:34
Cで教えるにはANSIにこだわると難しいらしいな。
グラフィックで雪印やドラゴンカーブを書かせれば
すぐに理解できるとは思うけれど

34 :デフォルトの名無しさん:2001/06/17(日) 20:09
ファイル検索のアルゴリズムは再帰?

35 :>>34:2001/06/17(日) 20:17
検索関数でサブディレクトリ(フォルダ)が見つかったら
そのフォルダ相手に検索関数を実行する再帰手法が一般的
というか他のやり方はすぐに思いつかないのだが。
そういえばANSIにファイル検索関数ってなかったっけ。

36 :デフォルトの名無しさん:2001/06/17(日) 20:45
>>33
Cで再帰を教える代表的なものは、クイックソートだな。

>>35
それは深さ(縦)優先の再帰。逆の再帰もあるだろ。
深さ優先は使用メモリは最小限にできるが、
その深さに比例してハンドルをオープンしっぱなしにしなければならない。

37 :デフォルトの名無しさん:2001/06/17(日) 20:58
>>36
逆の再帰って何ですか?

38 :デフォルトの名無しさん:2001/06/17(日) 21:04
lispヤレヤ

39 :デフォルトの名無しさん:2001/06/17(日) 23:26
逆というか一般的に探索戦略は、深さ優先と幅優先の二種類がある。

40 :デフォルトの名無しさん:2001/06/17(日) 23:51
幅優先ってどんなの?具体例だけでもいいから希望

41 :デフォルトの名無しさん:2001/06/17(日) 23:52
幅を優先いたしまーす。

42 :デフォルトの名無しさん:2001/06/17(日) 23:53
>>23
K&R(第一版)にのってる数字を表示するやつは結構簡単でいいと思う。

43 :デフォルトの名無しさん:2001/06/17(日) 23:55
23じゃないけど>>42
K&R、持ってない。どんなの?

44 :デフォルトの名無しさん:2001/06/17(日) 23:56
aaa
 bbb
  ccc
 ddd

という階層構造があった場合、
aaa->bbb->ccc->dddと上から(?)順番に探してくのが深さ優先
aaa->bbb->ddd->cccと浅い順から探してくのが幅優先。
無限に(あるいは十分に)深い階層を探索する場合はこっちが有効な場合が多い。
ただメモリを馬鹿食いする。

45 :40:2001/06/17(日) 23:57
>>44
tnx.

46 :デフォルトの名無しさん:2001/06/18(月) 00:06
>>43
printd(int n) /* nを10進数で表示 */
{
 int i;

 if (n < 0) {
  putchar('-');
  n = -n;
 }
 if ((i = n/10) != 0)
  printd(i);
 putchar(n % 10 + '0');
}

再帰使わない例も載ってて、それと比べると再帰の良さがわかりやすい。

47 :39:2001/06/18(月) 00:10
オセロや将棋などのゲームで考えると分かりやすいと思う。
次の手、その結果に対して次の手とどんどん先読みしていくのが深さ優先。
次の手には何があるのかを全て調べてから、その次の手を調べるのが幅優先。

48 :デフォルトの名無しさん:2001/06/18(月) 00:35
なるほど、さすがK&R。わかりやすい。
情報ありがとう>>46

49 :デフォルトの名無しさん:2001/06/20(水) 00:38
階乗とか最大公約数とか。

50 :デフォルトの名無しさん:2001/06/20(水) 04:07
>>49
再帰の例として良く見かけますけど、
階乗は、あまりメリットが見えないので、
n個以上(n>1)の数の最大公約数が良いかと…。

51 :デフォルトの名無しさん:2001/06/20(水) 04:36
全数探索を行うときに再帰を使った。
当然、全数探索にはO(2^n)かかるのを承知でだが。
指数オーダーはいかんよ。今さらだけど。

52 :デフォルトの名無しさん:2001/06/20(水) 04:51
宣教師と人食い土人

53 :デフォルトの名無しさん:2001/06/20(水) 04:52
バックトラック問題はみんな再帰

54 :デフォルトの名無しさん:2001/06/20(水) 09:02
スゲェ。
ちと感動したよ。>>1
一発ネタだが、名スレだ。

55 :デフォルトの名無しさん:2001/06/20(水) 23:45
再帰呼び出しを使わずに再帰を実装する方法も考えてみよう

って優香、クイックソートの実装に再帰を使うのはヤメレ

56 :デフォルトの名無しさん:2001/06/20(水) 23:51
>>55
再帰を使うのはサンプルだけだろ

57 :デフォルトの名無しさん:2001/06/20(水) 23:55
ワイルドカードプログラムはどうだろうか?

58 :デフォルトの名無しさん:2001/06/20(水) 23:56
>>56
再帰をスタックに直すプログラム書いてくれ。

59 :デフォルトの名無しさん:2001/06/20(水) 23:59
再帰のコードを1とすると、
再帰使わない方法(スタック)は2以上の工数がかかる。

60 :デフォルトの名無しさん:2001/06/21(木) 00:30
Q.

>>1を再帰を使わずに表現しなさい。

61 :デフォルトの名無しさん:2001/06/21(木) 00:33
>>55
 えっ!?なんで!?厨房なんでわからない。
教えて

62 :デフォルトの名無しさん:2001/06/21(木) 00:41
Win2000で試したら、窓380個(推定)まで開けたよ>>1

63 :デフォルトの名無しさん:2001/06/21(木) 00:45
>>61
サイキハショリガアマリハヤクナイ

64 :デフォルトの名無しさん:2001/06/21(木) 00:59
>>61
1. 速度が遅い

2. スタックサイズは制限がある環境が多く、エラーハンドリングが面倒

  ヒープならメモリ確保する時に正否が分かるが、スタックだと失敗した
  瞬間にシグナル (しかも環境によっては SIGKILL) 飛んできたりするし。

65 :デフォルトの名無しさん:2001/06/21(木) 01:07
58 名前:デフォルトの名無しさん 投稿日:2001/06/20(水) 23:56
>>56
再帰をスタックに直すプログラム書いてくれ。

これ作れば再帰で書いても良いんじゃない?

66 :デフォルトの名無しさん:2001/06/21(木) 01:18
>>64
POSIXならsigaltstack()が使えるが、
スタックが溢れたのかそうでないかを判別する手段がないんだよな。
なんかいい手知らない?

67 :61:2001/06/21(木) 01:23
 ふーむ。そうだったのか。
一つ賢くなったよ。アリガトホ

68 :デフォルトの名無しさん:2001/06/21(木) 01:38
>再帰をスタックに直すプログラム書いてくれ。
同じく

69 :デフォルトの名無しさん:2001/06/21(木) 01:56
再帰をやめれば自分で管理できるかと。

70 :デフォルトの名無しさん:2001/06/21(木) 01:59
59 名前:デフォルトの名無しさん 投稿日:2001/06/20(水) 23:59
再帰のコードを1とすると、
再帰使わない方法(スタック)は2以上の工数がかかる。

71 :デフォルトの名無しさん:2001/06/21(木) 02:34
>>58
なぜ俺に言う。
しかも、ループに展開できるのは末尾再帰だけだ

72 :デフォルトの名無しさん:2001/06/21(木) 12:18
>>64 qsortならスタックのサイズは高々 log n じゃない?
それから、再帰呼びだしのオーバーヘッドて
自分でスタック実装したときよりもそんなにデカいものなんですか?
アセンブラレベルで比べたことがないからわからない。

73 :デフォルトの名無しさん:2001/06/21(木) 12:30
>>70
状況によって違う。
一般論では語れない。

74 :デフォルトの名無しさん:2001/06/21(木) 16:46
>>74
おまえもなー。

75 :デフォルトの名無しさん:2001/06/21(木) 16:53
>>74
ナイス!ワラタ

76 :デフォルトの名無しさん:2001/06/22(金) 00:18
>>72
違うよ。
クイックソートは平均がO(logN)なだけで、最悪の場合はO(N)になる。

77 :デフォルトの名無しさん:2001/06/22(金) 03:33
>>72 >>76
クイックソートはO(n log n)。
最悪はO(n^2)。(避けれるように出来るけど)

>>72
> それから、再帰呼びだしのオーバーヘッドて
> 自分でスタック実装したときよりもそんなにデカいものなんですか?

結構でっかいような気はするなぁ。

78 :デフォルトの名無しさん:2001/06/22(金) 03:58
スタック
if (sp == stack_num) stack = realloc(stack, stack_num *= 2);
stack[sp++] = val;

再帰
f(val);

スタックは毎回
・オーバーフロー判定(最初に見積もれれば不要)
・インデクス参照代入
・spの増加

再帰は毎回
・関数呼出し(オーバーフローは判定不能)
が必要。

79 :デフォルトの名無しさん:2001/06/22(金) 04:09
>>78
> ・インデクス参照代入
> ・spの増加

popは…。

> ・関数呼出し(オーバーフローは判定不能)

これがでかいよね。
レジスタ退避させたり。

80 :77:2001/06/22(金) 04:17
あ、ごめん。
O(log n)ってスタックのサイズの話ね……。

81 :デフォルトの名無しさん:2001/06/22(金) 06:59
再帰→スタック変換を人間が行なうと、
プログラム意味論的(よく知らんけど)に、
「再帰構造である」という主張が薄れるって害は無い?
(forやwhileをgotoに直す様な事と同等)
C->ASMの様に、
機械的(暗黙的に)にやらせるのが理想だと思うんだけど。

82 :デフォルトの名無しさん:2001/06/22(金) 07:57
>>77
計算量ではなくてスタックの深さの話だと思うが

>>76
末尾再帰を上手く使えば O(log N)で抑えられる。
小さいブロックを先に片づけるのだ

83 :デフォルトの名無しさん:2001/06/22(金) 07:59
>>81
まあね。
でも意味重視で性能悪いのは・・・ね。

まあ、理解不能になるわけじゃないしいいんじゃない?

84 :デフォルトの名無しさん:2001/06/22(金) 08:03
>>82
小さいブロックを先に…って話じゃ無理かと。

二つに分ける時に、片寄らないようにしないとイカン。

85 :age:2001/06/24(日) 23:11
age

86 :デフォルトの名無しさん:2001/06/25(月) 14:59
ニホンジンハウソツキ

87 :>>50:2001/06/26(火) 00:20
>再帰の例として良く見かけますけど、
>階乗は、あまりメリットが見えないので、
>n個以上(n>1)の数の最大公約数が良いかと…。

nが2個ならユーグリッドの互除法だよね。
3つ以上ならどのように再帰で表現する?
出来なくないですか?

88 :デフォルトの名無しさん:2001/06/26(火) 12:44
GCD(n1, n2, ..., nm) <= GCD(n1, GCD(n2, ..., nm)).
じゃないの?

89 :デフォルトの名無しさん:2001/06/26(火) 13:47
ネタスレがこんな良スレに育って・・・父さん嬉しいぞ

90 :本ヲタ:2001/06/26(火) 14:13
The Little Schemer
http://www.amazon.com/exec/obidos/ASIN/0262560992/002-6796989-4387263

The Seasoned Schemer
http://www.amazon.com/exec/obidos/ASIN/026256100X/002-6796989-4387263

A Little Java, a Few Patterns
http://www.amazon.com/exec/obidos/ASIN/0262561158/002-6796989-4387263

http://www.cs.rice.edu/~matthias/TLS/
http://www.cs.rice.edu/~matthias/TSS/
http://www.cs.rice.edu/~matthias/Javar/

リスト遊び
http://www.kame.net/~kazu/book/list.html
http://www.ascii.co.jp/books/detail/4-7561/4-7561-3442-4.html
http://www.amazon.co.jp/exec/obidos/ASIN/4756134424/249-7473945-9268357

91 :デフォルトの名無しさん:2001/06/29(金) 06:06
実際問題、
「(末尾再帰ではない)再帰→スタック+ループ」
変換は機械的に可能でしょうか?

92 :デフォルトの名無しさん:2001/06/29(金) 06:20
>>91
可能でしょ。
アセンブラレベルでは「スタック+ループ」みたいなもんじゃん。
あれがcallとretでなくjmp+αだったらいいだけでしょ?
# これは可能っていう根拠について書いてるので
# 上記の方法でやれってのとは違うです。

93 :デフォルトの名無しさん:2001/07/06(金) 18:12
age

94 :デフォルトの名無しさん:2001/07/06(金) 23:17
>>92
アセンブラにした所で、再帰構造のコードはずっと再帰ですが。

95 :デフォルトの名無しさん:2001/07/06(金) 23:45
じゃあ、「再帰」と「スタック+ループ」の違いは?
PCをスタックに積むかどうか?

96 :96:2001/07/07(土) 00:25
>>96
オマエモナー(気に入ったらしい)

97 :74:2001/07/07(土) 14:13
>>97
パクルなYO!(ちょっとしつこいな・・・)

98 :デフォルトの名無しさん:2001/07/09(月) 00:14
 順列の生成を再帰を使わずにやってみた事が有るけど、パフォーマンスは
確かに上がるね。ソースは汚くなるけど。

99 :デフォルトの名無しさん:2001/07/09(月) 01:29
いまさらだけど、schemeというlisp系言語やMLなどの関数型言語は
言語規約として末尾再帰(単体/相互)をgoto相当に展開する。
普通の再帰は知らないけど。
表現能力は、
再帰>スタック+ループ

100 :デフォルトの名無しさん:2001/07/09(月) 01:56
100!

101 :デフォルトの名無しさん:2001/07/09(月) 02:17
101!

102 :デフォルトの名無しさん:2001/07/09(月) 02:17
>>103

103 :デフォルトの名無しさん:2001/07/09(月) 02:18
>>102

104 :98:2001/07/09(月) 02:48
そういえばあの時順列のアルゴリズムを追求してすごいの作ったつもりに
なってたけど、ある本を読んだら最少順序変換法って名前が付いてた。
車輪を再発明してたのが判ってしばらく鬱だったよ。

>>102,103
入り口が複数なのね。

105 :デフォルトの名無しさん:2001/07/09(月) 03:06
>>104
そうやって、人は一歩ずつ成長して行く

106 :デフォルトの名無しさん:2001/07/09(月) 22:12
アルゴリズム言語Schemeに関する第五改訂報告書
http://www.sci.toyama-u.ac.jp/~iwao/Scheme/r5rsj/html/r5rsj.html#SEC2
>繰り返しを表現する場合に手続き呼び出しのみを使用することによって、
>終端再帰的手続き呼び出しが本質的に引数を渡すgotoであることが、Schemeでは強調されている。

107 :デフォルトの名無しさん:2001/07/10(火) 08:47
>>99 単純にそうは言えないだろ。
暗黙の制御スタック一つしかない再帰に比べれば、明示的な
スタックは複数もつことができて、より細かい制御はできるし。
まあ、安直なものは再帰のほうが楽にかけて、
世の中安直で十分な場合も多いというのは真だけど。

108 :デフォルトの名無しさん:2001/07/12(木) 15:25
なんだぁ、リカーシブって
再び呪いをかけられることかと思ってたよ

109 :デフォルトの名無しさん:2001/07/13(金) 23:15
>>108
Bit悪魔の辞典ですか(笑)

110 :>108:2001/07/13(金) 23:30
そりゃ、リ・カース(re-curse)

111 :デフォルトの名無しさん:2001/07/14(土) 20:47
難しいボケとツッコミだなぁ

112 :1:2001/07/17(火) 23:02
うんち

113 :デフォルトの名無しさん:2001/07/17(火) 23:28
>>112
1がコレだもんなぁ

114 :デフォルトの名無しさん:2001/07/18(水) 00:33
>>113
ナイーブな対応。再帰にしてみよう

115 :1(本物):2001/07/18(水) 03:14
>>113
>>112は騙りです。

116 :デフォルトの名無しさん:2001/07/18(水) 10:50
再帰することはオブジェクト指向的に見てどう?

117 :再帰:2001/07/18(水) 12:07
人をバカって言うヤツがバカ。

118 :デフォルトの名無しさん:2001/07/18(水) 13:17
人をバカって言うやつがバカって言うやつが…

Stack overflow

119 :デフォルトの名無しさん:2001/07/19(木) 03:11
>>118
ほぉら、再帰に入る前に脱出の手段考えてないからこんなことに…

120 :デフォルトの名無しさん:2001/07/19(木) 03:14
>>118-119
ワラタ。おもろい

121 :116:2001/07/19(木) 04:02
なるほどそういうことか!
目から鱗だね!

122 :デフォルトの名無しさん:2001/07/19(木) 17:34
良スレ

123 :#6411:2001/07/19(木) 18:28
良スレ
>>16 >>19 他称ハッカーは尊称、ということにしとこうや。

124 :デフォルトの名無しさん:2001/07/19(木) 21:07
末尾再帰ぐらい展開しろやボケェ!
って状況になるといいね。

125 :デフォルトの名無しさん:2001/07/20(金) 18:27
>>121 は、どのカキコをみて >>116 の解を見つけたのか謎である。

126 :デフォルトの名無しさん:2001/07/21(土) 00:52
ほんと、謎だね。

127 :116=121=125:2001/07/22(日) 11:37
ジサクジエンデシタ (o^ー')b

128 :末尾再帰?:2001/07/24(火) 10:09
http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842

26 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)