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
おもすれ
tst
tst tst
1,Memechan
http://uniuni.dfz.jp/moeclc2/?0&0K1lp3K5ok820coasKtUyTzXBYDK 2,クロワッサン
http://uniuni.dfz.jp/moeclc3/?0&97&0K1lp2K3K5lfwUxJzn5CYEJPYWO 3,legal
http://uniuni.dfz.jp/moeclc2/?0&0q01603o04C5HbJtq0yJAqaLEMJPP 4,めだまおやぎ
5,クルサード
6,ケルディン
7,ささらん
http://uniuni.dfz.jp/moeclc3/?2&97&0K1lp3K5KoJvUyUzTEK 8,Rviz
9,Tyranno
10,ANOTHER
http://uniuni.dfz.jp/moeclc2/?2&0F1ek2K3K5KsJtUyn5BSDUQ15 11,ムラディン
http://uniuni.dfz.jp/moeclc4/?3&97&0K1mg3K5p0tpkuUzKEoQPnIWbM 12,ミルカッセ
http://uniuni.dfz.jp/moeclc2/?2&1ek2K3I4F54a6r57KHTIJJKNI 13,ディアス
14,キュー
http://uniuni.dfz.jp/moeclc3/?2&97&1602K3I4F5C6K7KIUJJKJOKPY 15,Ligy
http://uniuni.dfz.jp/moeclc4/?0&97&0K1ie3K4bW5I8JkVvKzTEKNKXN
a
GNU's Not UNIX.
66 :
デフォルトの名無しさん:2006/11/04(土) 16:00:45
そして再び最下層から1へ帰る
おもしろそーなスレ発見。
でも、再帰させるときは迷う。
再帰しなくて済む方法がないか考える。
処理速度が下がりそうじゃない?
でも、個人的に再帰好き。巧く書けると気持ちいい。
俺は末尾再帰を信じるぜ。
だから再帰を除去しない。
末尾再帰以外でそこがボトルネックだと形式的にスタックを使う形に置き換えるのはするけどな。
コンポジットパターンを実装すると
大体イヤでも再帰になる
70 :
デフォルトの名無しさん:2007/04/30(月) 18:43:54
再起age
プログラムの再帰は必ずループに置き換えて
データ構造のみスタックにして対処しています
再起なんて無いに越したことないだろ。
んでみんなに質問
再起でないとだめな場合ってどんな場合?
74 :
デフォルトの名無しさん:2007/06/10(日) 22:08:03
つーか逆になんでそんなに再起を危険視するのが意味わからん
>>73 コンポジットパターンの実装で、オブジェクトをトラバースするような処理では
スーパークラスのメソッドの再起になりやすいな
バベルの塔
ハノイじゃないか?つーか再起してどーする
バベルの塔は死なん。何度でも蘇るのじゃ。
つーかOOPL使えよいい加減
かんけーねーだろ。バカか?
うんこー
未だに構造化設計乙
OOだと再帰ができないと思っている人がいるみたいですね
あ、おばかさんのためにちょっと例をだしてあげます。
class node {
node *left;
node *right;
public:
void execute() {
hogehoge...;
left->execute();
right->execute();
}
};
void foo(node *root) {
root->execute();
}
これが再帰ですよ。
>>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=[];
を再帰でなく書くことは
可能だけど面倒。
>>85 Prologだと、どこかで再帰を使わないと
書けないのでは?
再帰を毛嫌いするような奴とは
一緒に仕事したくねー
木リストとかどうすんのよ
>>86 list_length/2 は
使って良いとして(これも再帰を使っているが)、
findall/3 の中でassert/1 retract/1 を
繰り返して何とかなりそうに思ったが
だめかな。
>>89 は結合の方でした。 ?- append([1,2],[a,b],X).
生成の方は全然だめ。 ?- append(X,Y,[1,2,a,b]).
repeat/1 か for/3 それと list_nth/2 が欲しいですね。
どれも再帰述語だな。
再帰って、再帰を使わない等価な書き方が、必ずあるんじゃないの?
おまえならできる
>>91 処理の繰り返しの中で使用する変数(コンテキスト)をスタックに置くのが再帰ですから
スタックを自力で用意するか、そのようなコンテキストがそもそも存在しないのなら
別にループでも構いませんよ。
再帰を使わないとループを書けない言語では別だがな。
シティーボーイズの大竹まことです
きたろうです
再帰しげるでs
再帰キタ━━━━(゚∀゚)━━━━━ッ!!!
98 :
名無しさん@Vim%Chalice:2007/06/16(土) 14:20:01
馬鹿PGほど無理やり再帰みたいなん使いたがる
まともな大人は他人を馬鹿って言わない
何このレッテルの貼り合い
101 :
デフォルトの名無しさん:2007/06/16(土) 17:06:21
末尾再帰の最適化というのがあるのだが、
あえて再帰を使ってそれが末尾再帰になってる可能性というのはどのくらいあるんだ?
勝手に最適化されるわけじゃなくて、末尾再帰になるように書いた時に
コール→リターン命令じゃなくジャンプ命令になるってだけ
可能性というよりはもっと作為的な物であって、プログラムを書く人間の
意図に依存してる
意識して末尾再帰にするくらいならはじめから再帰なんて使わんよ。
C++のコンパイラには最適化をやってくれるのもが多いがJavaやC#はやらんみたいだ。
Java は HotSpot の機能でなかったっけ?
>>103 元々再帰的な処理を、リソースの無駄遣い無くそのまま書き下せるんだから
末尾再帰にするのは意味あるよ。
>>103 は単にループ以外使いたくない
だけでしょ。
>>104 試してみたがC#とJavaの両方ともコンパイル時およびJIT(HotSpot, ngenなど)時に
末尾再帰の最適化はやってくれなかった。きっちりスタックオーバーフローが起きる。
>>105 ほしいと思ってるのが関数が末尾再帰であることを保障するキーワード。
末尾再帰の最適化がなされなかった場合にコンパイルエラーまたは実行時にAssertするような機能。
>>106 Web で見た感じだと IBM の JVM は末尾再帰の最適化してるみたいね。
HotSpot は RFE が上がってて in progress になってた。
どちらも古い情報だったんで、現状どうなってるかは分からないけど。
また地獄に再帰する・・・・