108コメント27KB

　　　　　　　再　　　　　　　帰　　　　　　　

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

0001デフォルトの名無しさん

2006/01/01(日) 23:04:15

うわああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
ああああああああああああああああああああああああああああああああああああ
!！！！！！！！！！

0002最凶VB厨房

2006/01/01(日) 23:18:08

>>2
どうした？

0003デフォルトの名無しさん

2006/01/01(日) 23:22:04

>>3
何やってんだよ

0004デフォルトの名無しさん

2006/01/01(日) 23:24:18

>>4
４様ですか？

0005デフォルトの名無しさん

2006/01/01(日) 23:26:38

>>4
４様です。

0006デフォルトの名無しさん

2006/01/01(日) 23:31:15

>>6
４様でしたね。

0007デフォルトの名無しさん

2006/01/02(月) 01:49:43

int fact(int n)
{
if(!n) puts("う"), return 1;
else if(n == 1) puts("わ"), return 1;
else puts("あ"), return fact(n - 1);
}
int main(void)
{
return fact(1000);
}

0008デフォルトの名無しさん

2006/01/02(月) 03:51:41

まったくもって再帰にする必要がねえな

0009デフォルトの名無しさん

2006/01/02(月) 05:03:02

末尾再帰という

0010デフォルトの名無しさん

2006/01/02(月) 07:33:11

>>7
これだと

[出力結果]
あ*999
わう

になってしまうような気がする俺ガイル。
俺はただの馬鹿野郎ですか？

0011デフォルトの名無しさん

2006/01/02(月) 08:58:41

>>10
そもそも数字は出てこないし
足してもいないし掛けてもいない

0012デフォルトの名無しさん

2006/01/02(月) 09:02:12

ああ、こういうことか

int fact(int n)
{
if(!n) puts("う"), return 1;
else if(n == 1) puts("わ"), return 1;
else fact(n - 1), puts("あ"), return 1;
}
int main(void)
{
return fact(1000);
}

0013デフォルトの名無しさん

2006/01/02(月) 09:03:30

わうあ*9999
になってしまうな orz

0014デフォルトの名無しさん

2006/01/02(月) 09:05:15

「う」は出てこないんじゃないか？w

0015デフォルトの名無しさん

2006/01/02(月) 09:09:14

ん？
新たな初心者スレ？ｗ

0016デフォルトの名無しさん

2006/01/02(月) 10:53:22

>>10-11
あを999個書くの面倒で、あ*999としたんだろ。

int fact(int n)
{
if(!n) return 1;
else if(n == 1000) puts("う"), return 1;
else if(n == 999) puts("わ"), return 1;
else if(n == 9) puts("!"), return 1;
else if(n < 9) puts("！"), return 1;
else fact(n - 1), puts("あ"), return 1;
}
int main(void)
{
return fact(1000);
}
こうか？自動的にｗ改行されるとして、また、1000個ほどあると仮定して。

0017デフォルトの名無しさん

2006/01/02(月) 15:05:09

>>16
これだと「う」しか表示されないワナ

0018デフォルトの名無しさん

2006/01/02(月) 15:10:08

酔っ払い供めが。
素直にこう書けばいいんだよ。

int fact(int n)
{
if(!n) puts("う");
else if(n == 1) puts("わ");
else puts("あ");
return fact(n - 1);
}
int main(void)
{
return fact(1000);
}

0019デフォルトの名無しさん

2006/01/02(月) 16:26:07

int fact(int n)
{
if(!n) return 1;
else if(n == 1000) puts("う"), fact(n - 1);
else if(n == 999) puts("わ"), fact(n - 1);
else if(n == 9) puts("!"), fact(n - 1);
else if(n < 9) puts("！"), fact(n - 1);
else puts("あ"), fact(n - 1);
}
int main(void)
{
return fact(1000);
}

0020今年初プログラミング

2006/01/02(月) 16:44:56

fact = fact' 0
　　where
　　　　fact' 0 = 'う' : fact' 1
　　　　fact' 1 = 'わ' : fact' 2
　　　　fact' n = 'あ' : fact' (n+1)

main = putStrLn $ take 1000 fact

0021デフォルトの名無しさん

2006/01/02(月) 16:55:58

int fact(int n)
{
if( !n ) return 1;
else if(n == 1000) puts("う");
else if(n == 999) puts("わ");
else if(n == 9) puts("!");
else if(n < 9) puts("！");
else puts("あ");
fact(n - 1);
}
int main(void)
{
return fact(1000);
}

0022デフォルトの名無しさん

2006/01/02(月) 16:58:15

>>20
fact = 'う' : 'わ' : aaa
where
aaa = 'あ' : aaa

0023デフォルトの名無しさん

2006/01/02(月) 17:00:09

何を盛り上がってるんだお前らｗ

0024デフォルトの名無しさん

2006/01/02(月) 17:05:10

再帰不能

0025デフォルトの名無しさん

2006/01/02(月) 17:06:37

2chのスレ立てって簡単ですねって見本

0026デフォルトの名無しさん

2006/01/02(月) 17:28:02

fact = 'う':'わ':fact' [] "あ"
where
fact' x y = x ++ fact' y ("ぁ" ++ x ++ y)

0027デフォルトの名無しさん

2006/01/02(月) 17:31:07

C初心者とHaskell初心者が入り乱れてるなｗ

0028デフォルトの名無しさん

2006/01/02(月) 18:16:50

(defun fact (x)
  (case x
    (0 (write-string "うわ"))
    (t (fact (1- x)) (write-char #¥あ))))

0029デフォルトの名無しさん

2006/01/02(月) 18:38:35

```s.わ`.うi``s.あi

厳密には再帰じゃないけど。

0030デフォルトの名無しさん

2006/01/02(月) 18:50:53

再帰が難しいとか言ってる奴は、
現代のプログラミングの基本中の基本が出来ていない似非プログラマ。

0031デフォルトの名無しさん

2006/01/02(月) 19:07:26

あ、末尾再帰じゃないとまずかったかな。

(defun fact (x)
    (progn
        (write-string "うわ")
        (labels
            ((fact1 (y) (unless (zerop y) (write-char #¥あ) (fact1 (1- y)))))
            (fact1 x))))

これで末尾呼び出しになってる?

0032デフォルトの名無しさん

2006/01/02(月) 20:26:36

let fact len =
　let rec f id ed vl =
　　if id >= ed
　　　then vl
　　　else match id with
　　　　0 -> f (id + 1) ed (vl ^ "う")
　　　| 1 -> f (id + 1) ed (vl ^ "わ")
　　　| n -> f (id + 1) ed (vl ^ "あ") in
　f 0 len ""

let main =
　print_endline (fact 1000)

0033デフォルトの名無しさん

2006/01/02(月) 22:23:33

次のお題をどうぞ

0034デフォルトの名無しさん

2006/01/02(月) 22:39:55

>ALL このスレへ行け。
ttp://pc8.2ch.net/test/read.cgi/tech/1136124255/

0035デフォルトの名無しさん

2006/01/02(月) 22:56:57

>>35

0036デフォルトの名無しさん

2006/01/03(火) 00:23:24

相互再帰
http://pc8.2ch.net/test/read.cgi/tech/1048088635/215

0037デフォルトの名無しさん

2006/01/04(水) 19:04:24

void a(int n) {
　if (n == 0) {
　　puts("!!");
　　return;
　}
　puts("A");
　b(n-1);
}

void b(int n) {
　if (n == 0) {
　　puts("?");
　　return;
　}
　puts("H");
　b(n-1);
}

int main() {
　a(100);
}

0038デフォルトの名無しさん

2006/01/09(月) 01:47:33

再帰ってどのくらいまでスタックすることが出来るんでしょうか？

0039デフォルトの名無しさん

2006/01/09(月) 01:52:11

>>38
それは、コンパイル時に設定する最大スタックサイズしだいじゃないかな？？

0040デフォルトの名無しさん

2006/01/09(月) 01:53:44

100%?

0041デフォルトの名無しさん

2006/01/09(月) 01:56:19

UNIX だとプロセス起動時にスタックサイズ変えられるけど

0042デフォルトの名無しさん

2006/01/09(月) 08:00:02

qsort使って要素数10000000くらいの配列でソートしたら時々暴走するんです。
やはり再帰が原因のスタックオーバーフローでしょうか？

0043デフォルトの名無しさん

2006/01/09(月) 08:11:13

気になるんなら、スタックをどのくらい使ってるか見てみれば良いじゃん
スタック使いきってるなら暴走じゃなくて segv とかでプロセスがクラッシュ
するんじゃないか?

0044デフォルトの名無しさん

2006/01/09(月) 08:39:07

再帰でスタック消費するの？だっせー言語ﾌﾟｹﾞﾗ

0045デフォルトの名無しさん

2006/01/09(月) 11:37:01

M$のqsortは再帰はつかってないな

0046デフォルトの名無しさん

2006/01/09(月) 14:26:04

>>44
末尾再帰に限定しないの？
ヒープとか使うの？

0047デフォルトの名無しさん

2006/01/10(火) 22:48:14

>>44
くわしきゅ

0048デフォルトの名無しさん

2006/01/11(水) 08:48:49

スレ移動してください
http://pc8.2ch.net/test/read.cgi/tech/1136124255/l50

0049デフォルトの名無しさん

2006/01/11(水) 10:49:31

fact(0) :- !.
fact(N) :- N > 0,write(うわ),M is N * -1,fact(M).
fact(N) :- write(あ),M is N + 1,fact(M).

0050デフォルトの名無しさん

2006/01/11(水) 11:50:55

>36
それは再帰違う

0051デフォルトの名無しさん

2006/01/11(水) 13:07:39

>>49
fact(0) :- !.
fact(N) :- integer(N),N > 0,write(うわ),M is N * -1,fact(M).
fact(N) :- integer(N),N < 0,write(あ),M is N + 1,fact(M).

が、好ましいコード。

0052デフォルトの名無しさん

2006/01/15(日) 12:08:19

x=y
y=x

0053デフォルトの名無しさん

2006/01/15(日) 14:51:17

それは再帰違う

0054デフォルトの名無しさん

2006/01/21(土) 20:21:35

>>54
再帰かよ。

0055デフォルトの名無しさん

2006/01/21(土) 20:53:22

http://pc8.2ch.net/test/read.cgi/tech/1136124255/55

0056デフォルトの名無しさん

2006/01/26(木) 00:45:04

>>54がスタックあふれを起こしましたよ

0057デフォルトの名無しさん

2006/03/26(日) 17:30:15

a (x) = x(b)
b (x) = x(a)
a (b)

0058デフォルトの名無しさん

2006/03/27(月) 22:44:22

>>57
Cで書こうとしてちょっと悩んだ。

0059デフォルトの名無しさん

2006/05/14(日) 22:33:22

L(G):
G=(N,Σ,P,S)
N={S,A,B,C,D}
Σ={う,わ,あ,!,！}
P={
　S→うA,
　A→わB,
　B→あB|C,
　C→!D,
　D→！D|ε
}
S=S

0060デフォルトの名無しさん

2006/07/23(日) 23:33:34

おもすれ

0061デフォルトの名無しさん

2006/07/28(金) 19:17:27

ｔｓｔ

0062 ◆YY8ebcAR4s

2006/09/17(日) 21:35:57

tst tst

0063デフォルトの名無しさん

2006/09/23(土) 23:54:40

0064デフォルトの名無しさん

2006/10/31(火) 09:50:27

0065デフォルトの名無しさん

2006/11/02(木) 03:18:10

GNU's Not UNIX.

0066デフォルトの名無しさん

2006/11/04(土) 16:00:45

そして再び最下層から１へ帰る

0067デフォルトの名無しさん

2006/11/04(土) 16:25:26

おもしろそーなスレ発見。

でも、再帰させるときは迷う。
再帰しなくて済む方法がないか考える。

処理速度が下がりそうじゃない？

でも、個人的に再帰好き。巧く書けると気持ちいい。

0068デフォルトの名無しさん

2006/11/04(土) 22:44:14

俺は末尾再帰を信じるぜ。
だから再帰を除去しない。

末尾再帰以外でそこがボトルネックだと形式的にスタックを使う形に置き換えるのはするけどな。

0069デフォルトの名無しさん

2007/01/08(月) 15:53:42

コンポジットパターンを実装すると
大体イヤでも再帰になる

0070デフォルトの名無しさん

2007/04/30(月) 18:43:54

再起age

0071デフォルトの名無しさん

2007/04/30(月) 19:10:04

プログラムの再帰は必ずループに置き換えて
データ構造のみスタックにして対処しています

0072デフォルトの名無しさん

2007/05/01(火) 06:43:19

>>71
なぜ?

0073名無しさん@Vim%Chalice

2007/06/10(日) 21:38:51

再起なんて無いに越したことないだろ。
んでみんなに質問
再起でないとだめな場合ってどんな場合？

0074デフォルトの名無しさん

2007/06/10(日) 22:08:03

つーか逆になんでそんなに再起を危険視するのが意味わからん

0075デフォルトの名無しさん

2007/06/10(日) 22:11:17

>>73
コンポジットパターンの実装で、オブジェクトをトラバースするような処理では
スーパークラスのメソッドの再起になりやすいな

0076デフォルトの名無しさん

2007/06/10(日) 22:19:34

バベルの塔

0077デフォルトの名無しさん

2007/06/11(月) 11:59:39

ハノイじゃないか？つーか再起してどーする

0078デフォルトの名無しさん

2007/06/11(月) 13:18:03

バベルの塔は死なん。何度でも蘇るのじゃ。

0079デフォルトの名無しさん

2007/06/11(月) 20:48:53

つーかOOPL使えよいい加減

0080デフォルトの名無しさん

2007/06/11(月) 22:50:09

かんけーねーだろ。バカか？

0081デフォルトの名無しさん

2007/06/11(月) 23:04:51

うんこー

0082デフォルトの名無しさん

2007/06/11(月) 23:06:09

未だに構造化設計乙

0083デフォルトの名無しさん

2007/06/12(火) 00:38:30

OOだと再帰ができないと思っている人がいるみたいですね

0084デフォルトの名無しさん

2007/06/12(火) 00:43:04

あ、おばかさんのためにちょっと例をだしてあげます。

class node {
　node *left;
　node *right;
public:
　void execute() {
　　hogehoge...;
　　left->execute();
　　right->execute();
　}
};

void foo(node *root) {
　root->execute();
}

これが再帰ですよ。

0085デフォルトの名無しさん

2007/06/12(火) 20:24:30

>>73
append([],X,X).
append([A|X],Y,[A|Z]) :- append(X,Y,Z).
Prologの有名なappend/3の定義ですが、
?- append([1,2],[a,b],X).
X=[1,2,a,b]
はともかく、
?- append(X,Y,[1,2,a,b]).
X=[],Y=[1,2,a,b];
X=[1],Y=[2,a,b];
X=[1,2],Y=[a,b];
X=[1,2,a],Y=[b];
X=[1,2,a,b],Y=[];
を再帰でなく書くことは
可能だけど面倒。

0086デフォルトの名無しさん

2007/06/13(水) 05:38:04

>>85
Prologだと、どこかで再帰を使わないと
書けないのでは?

0087デフォルトの名無しさん

2007/06/13(水) 21:10:50

再帰を毛嫌いするような奴とは
一緒に仕事したくねー

0088デフォルトの名無しさん

2007/06/13(水) 21:30:51

木リストとかどうすんのよ

0089デフォルトの名無しさん

2007/06/14(木) 18:39:51

>>86
list_length/2 は
使って良いとして(これも再帰を使っているが)、
findall/3 の中でassert/1 retract/1 を
繰り返して何とかなりそうに思ったが
だめかな。

0090デフォルトの名無しさん

2007/06/14(木) 18:53:30

>>89 は結合の方でした。 ?- append([1,2],[a,b],X).
生成の方は全然だめ。 ?- append(X,Y,[1,2,a,b]).
repeat/1 か for/3 それと list_nth/2 が欲しいですね。
どれも再帰述語だな。

0091デフォルトの名無しさん

2007/06/14(木) 20:49:05

再帰って、再帰を使わない等価な書き方が、必ずあるんじゃないの？

0092デフォルトの名無しさん

2007/06/14(木) 23:57:42

おまえならできる

0093デフォルトの名無しさん

2007/06/15(金) 13:09:02

0094デフォルトの名無しさん

2007/06/15(金) 13:11:20

>>91
処理の繰り返しの中で使用する変数(コンテキスト)をスタックに置くのが再帰ですから
スタックを自力で用意するか、そのようなコンテキストがそもそも存在しないのなら
別にループでも構いませんよ。

0095デフォルトの名無しさん

2007/06/15(金) 14:03:52

再帰を使わないとループを書けない言語では別だがな。

0096デフォルトの名無しさん

2007/06/15(金) 21:00:01

シティーボーイズの大竹まことです

きたろうです

再帰しげるでｓ

0097デフォルトの名無しさん

2007/06/15(金) 23:00:27

再帰ｷﾀ━━━━（ﾟ∀ﾟ）━━━━━ｯ!!!

0098名無しさん@Vim%Chalice

2007/06/16(土) 14:20:01

馬鹿PGほど無理やり再帰みたいなん使いたがる

0099デフォルトの名無しさん

2007/06/16(土) 14:53:23

まともな大人は他人を馬鹿って言わない

0100デフォルトの名無しさん

2007/06/16(土) 16:50:48

何このレッテルの貼り合い

0101デフォルトの名無しさん

2007/06/16(土) 17:06:21

末尾再帰の最適化というのがあるのだが、
あえて再帰を使ってそれが末尾再帰になってる可能性というのはどのくらいあるんだ？

0102デフォルトの名無しさん

2007/06/16(土) 17:22:00

勝手に最適化されるわけじゃなくて、末尾再帰になるように書いた時に
コール→リターン命令じゃなくジャンプ命令になるってだけ
可能性というよりはもっと作為的な物であって、プログラムを書く人間の
意図に依存してる

0103デフォルトの名無しさん

2007/06/16(土) 18:09:10

意識して末尾再帰にするくらいならはじめから再帰なんて使わんよ。
C++のコンパイラには最適化をやってくれるのもが多いがJavaやC#はやらんみたいだ。

0104デフォルトの名無しさん

2007/06/16(土) 18:14:27

Java は HotSpot の機能でなかったっけ?

0105デフォルトの名無しさん

2007/06/16(土) 18:31:47

>>103
元々再帰的な処理を、リソースの無駄遣い無くそのまま書き下せるんだから
末尾再帰にするのは意味あるよ。>>103 は単にループ以外使いたくない
だけでしょ。

0106デフォルトの名無しさん

2007/06/16(土) 19:12:10

>>104
試してみたがC#とJavaの両方ともコンパイル時およびJIT(HotSpot, ngenなど)時に
末尾再帰の最適化はやってくれなかった。きっちりスタックオーバーフローが起きる。

>>105
ほしいと思ってるのが関数が末尾再帰であることを保障するキーワード。
末尾再帰の最適化がなされなかった場合にコンパイルエラーまたは実行時にAssertするような機能。

0107デフォルトの名無しさん

2007/06/16(土) 19:24:41

>>106
Web で見た感じだと IBM の JVM は末尾再帰の最適化してるみたいね。
HotSpot は RFE が上がってて in progress になってた。

どちらも古い情報だったんで、現状どうなってるかは分からないけど。

0108デフォルトの名無しさん

2007/07/24(火) 00:52:22

また地獄に再帰する・・・・

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

再 帰

　　　　　　　再　　　　　　　帰　　　　　　　