再　　　　　　　帰　 　　　　　　

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

>>2
どうした？

>>3
何やってんだよ

>>4
４様ですか？

>>4
４様です。

>>6
４様でしたね。

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);
}

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

末尾再帰という

>>7
これだと

[出力結果]
あ*999
わう

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

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

ああ、こういうことか

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);
}

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

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

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

>>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個ほどあると仮定して。

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

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

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

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);
}

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

main = putStrLn $ take 1000 fact

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);
}

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

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

再帰不能

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

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

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

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

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

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

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

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

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

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

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)

次のお題をどうぞ

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

>>35

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

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);
}

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

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

100%?

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

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

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

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

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

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

>>44
くわしきゅ

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

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

>36
それは再帰違う

>>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).

が、好ましいコード。

x=y
y=x

それは再帰違う

>>54
再帰かよ。

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

再起age

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

>>71
なぜ?

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

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

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

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

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

きたろうです


再帰しげるでｓ

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

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

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

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

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

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

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

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

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

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

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

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

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

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