- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
670 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 07:33:00.36 ID:zGjt7Ia9 - >>656
おま、戻り値を使いまわしたら基本的に再帰じゃないの？。。。
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
673 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 08:00:20.87 ID:zGjt7Ia9 - //r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
戻り値の使いまわしは基本的に再帰
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
675 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 08:53:27.64 ID:zGjt7Ia9 - そそ、戻り値の使いまわしとスタック保存
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
676 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 08:59:50.82 ID:zGjt7Ia9 - たとえば、シュミレーションゲームでユニットの移動範囲を調べる
とかの全検索は、どうやっても再帰
もちろんＡ＊も再帰
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
678 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 09:03:26.20 ID:zGjt7Ia9 - スタック保存の必要がなければループ文でいい
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
679 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 09:05:10.34 ID:zGjt7Ia9 - >手順 (もしくはそれに相当するもの) を覚えている物が再帰。
これがスコープのスタック保存だろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
685 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 09:26:38.87 ID:zGjt7Ia9 - sum=sum+iで
sum+iのsumはスタック保存値
sum=のsumがスタック保存（＋上書き）
こういうのはループでも全然いいけど
スコープスタックを保存する必要があるなら、完全に再帰しかない
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
687 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 09:40:47.32 ID:zGjt7Ia9 - いや再帰っつーのは終わるまで必ず自身がどの手順でそこの処理に居るのかが記録されてるから。
必要がないもくそもない
だから、スコープスタックを保存する必要がある時に、再帰を使う必要があるんですってば
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
688 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 09:57:57.73 ID:zGjt7Ia9 - >>650
は
>>673
な感じなんだろ
ループは、スコープスタックを保存しなくていい時
再帰は、スコープスタックを保存しなければいけない時
再帰の文字通り、手順の戻り道を、覚えている必要があるかどうかだよ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
690 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:01:42.56 ID:zGjt7Ia9 - バカは知りませんが関数呼び出しはコールスタックです
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
694 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:12:58.37 ID:zGjt7Ia9 - //r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
これは全部、スタックに保存されてるよ
だから、
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
これに比べて、スタック保存分、オーバーロードしているけどね
ユニットの移動範囲とか、画像のフィリングとか、
ある点の周囲探索は、スタック保存の再帰関数にするのが一番いいだろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
695 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:16:27.86 ID:zGjt7Ia9 - たとえば白黒ドットの囲まれた場所のある点からの塗りつぶしで
ループだけしか使わないバカがいるのか？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
698 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:21:49.47 ID:zGjt7Ia9 - 白黒ドットの囲まれた場所のある点からの塗りつぶしで
ループだけしか使わないで作れるなら作ってみろよ
ニヤニヤしながら見ててやるから
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
699 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:26:03.39 ID:zGjt7Ia9 - >>697
え？コールスタックが再帰じゃないの？
それじゃ、関数を呼び出した後、元の位置に戻れないぞ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
702 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 10:34:15.27 ID:zGjt7Ia9 - サブルーチンの呼び出しの後、
呼び出し元に復元（リターン）できなければ、
プログラムじゃねえよ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
706 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 11:00:37.95 ID:zGjt7Ia9 - ttp://nas6.main.jp/secret/ContainerPtr.htm
の
ttp://nas6.main.jp/NAS6_tree_clct.h
//再帰構文例1
//再帰構文例2
は俺は両方再帰だと思って作ったけどな
>>700
みたいのは
//再帰構文例1
の構造だろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
707 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 11:05:54.33 ID:zGjt7Ia9 - 関数の自分自身を呼ばないと再帰関数じゃないっていうのは
頭が固いんじゃないの？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
708 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 11:10:08.71 ID:zGjt7Ia9 - 訂正
関数の自分自身を呼ばないと再帰処理じゃないっていうのは
頭が固いんじゃないの？
//再帰構文例1
は関数の自分自身を呼んでないけど、どう見ても再帰処理
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
714 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 11:55:26.05 ID:zGjt7Ia9 - >>713
だからクラスの関数呼び出しなんて、ほとんど
this->が省略されているだけなんだが・・・
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
717 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 12:09:24.27 ID:zGjt7Ia9 - アセンブリレベルが分からないと説明しようがないな
基本的にスタックでしか動かないし
ttp://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node65.html
再帰呼び出し、スタック
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
718 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 12:13:43.89 ID:zGjt7Ia9 - >>717の大学教授にこれはループであって再帰ではないってかみついてこいよ
def xn2(N) {
XN = 0;
for (I=0; I<N; I++) {
XN = 2*XN+1;
}
return(XN);
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
719 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 12:25:42.76 ID:zGjt7Ia9 - int sum = 0;
for(int i = 1; i <= 10; i++) {
sum = sum + i;
}
な、これは再帰だろ、頭が悪いんだから、教授に迷惑をかけるなよ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
720 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 12:44:51.30 ID:zGjt7Ia9 - 戻り値を使いまわしたら基本的に再帰なんだよってはじめに書いておいた
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
721 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 12:56:18.37 ID:zGjt7Ia9 - >>700
のも
新たなシードを決める際には、バッファ中のどのピクセルを選んでもよいのですが、
新しい順か、古い順かのどちらかに統一するのが普通でしょう。
バッファをスタック構造にすれば新しい順、キューにすれば古い順に自然に決まります。
これを読んでいないのか再帰じゃないと思ってるんだろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
723 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 13:14:58.05 ID:zGjt7Ia9 - >>722
だから、戻り値を使って再帰呼び出ししているのと同じ事だろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
727 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 13:22:00.75 ID:zGjt7Ia9 - >>725
>>717
のリンクで
正式には再帰で書くけど、
最適化してループで書くってようなことが書いてあるだろ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
728 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 13:26:52.77 ID:zGjt7Ia9 - >>717
のリンクでも
>>694
でも
＞これに比べて、スタック保存分、オーバーロードしているけどね
こういうわけで再帰をループに最適化するわけ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
730 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 13:41:26.99 ID:zGjt7Ia9 - //等差数列
//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (n--; 0 < n; n--, t += s) r = r + t;
return r;
}
で、最適化されたのしか、教わらないし、理解できないのかな？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
731 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 13:48:39.57 ID:zGjt7Ia9 - 訂正
//等差数列
//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (; 1 < n; n--, t += s) r = r + t;
return r;
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
733 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 14:09:21.37 ID:zGjt7Ia9 - 漸化式で求めた全ての項を
参照する必要があるのならば
動的計画法を用いることはできない
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
736 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 14:42:48.35 ID:zGjt7Ia9 - >>734
ああ、ごめんね
sigmaだから1〜nまでの等差数列の和だよ
漸化式の全ての項を使う
→全てのノードを使う時は動的計画法で最適化できないんよ
そのケースは、ある点からの周囲の経路を探索する場合
ディレクトリ探索だったり、塗りつぶしだったり、つまり全検索をかける場合
こういうのは再帰を使うだろうに
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
737 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 14:44:53.85 ID:zGjt7Ia9 - つまり経路の全検索をかける場合
こういうのは再帰を使うだろうに
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
739 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 14:57:36.94 ID:zGjt7Ia9 - >>734
sigmaだから1〜n-1までの等差s数列の和
s=3なら
sigma=3+6+9+12+・・・
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
740 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 15:08:23.80 ID:zGjt7Ia9 - //1〜n-1までの等差s数列の和
//定義に忠実に書いた場合
//r:ret,s:diff,n:n
int sigma(int r, int s, int n) {
if (n < 1)return 0;
if (n == 1) return r;
return r + sigma(r + s, s, n - 1);
}
//メモリ使用量を最適化した場合
int sigma2(int s, int n) {
if (n < 1)return 0;
int r = 0, t = s;
for (; 1 < n; n--, t += s) r = r + t;
return r;
}
べつにどっちで書けって言われても
項をスタックするかしないだけの違いだけど？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
744 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 15:19:27.30 ID:zGjt7Ia9 - 利点と欠点があって
再帰：書けない漸化式はない、項をスタックするからメモリを消費する
ループ：項の参照が少ない漸化式のみ書ける、項をスタックしないからメモリ使用量は少ない
そんだけ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
746 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 15:31:56.99 ID:zGjt7Ia9 - >>745
ノード検索とか再帰のノード全てメモしてループするとか
素直に再帰を使っちゃいかんのかいな
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
750 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 18:40:37.54 ID:zGjt7Ia9 - 利点と欠点があって
再帰：書けない漸化式はない
項をスタックするからメモリを消費する
ループ：項の参照が少ない漸化式のみ書ける
あるいは項をメモする必要がある
項をスタックしないからメモリ使用量は少ない
そんだけ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
755 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 20:00:58.23 ID:zGjt7Ia9 - double calcPI(double r, double s, double n) {
double t = 1.0;
if (s == 1) t = 2.0;
if (n == 1) return r;
return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI2() {
double sse = 0.00000000000001; double a = 0.125;
double b = sqrt(a); double c = 1.0 + 3.0 * b;
double d = sqrt(c); double e = 0.625;
double f = d - e; d = 2 * d;
b = f - b; c = c + f;
double npow = 4;
do {
npow = 2 * npow; f = (c + d) / 2;
d = sqrt(c * d); f = f - d;
d = 2 * d; b = b - f; c = f + d;
} while (sse < f);
f = f * f / 4; c = c + d;
return (c * c - f - f / 2) / (c * b - f) / npow;
}
どっちが簡単だと思う？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
756 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 20:25:21.94 ID:zGjt7Ia9 - double calcPI(double r, double s, double n) {
double t = 1.0;
if (s == 1) t = 2.0;
if (n == 1) return r;
return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
while (1 < n) {
t = (t * s / (2.0 * s + 1.0));
r = r + t;
s += 1;
n -= 1;
}
return 2.0 * r;
}
意地悪が過ぎたが、今度はマジ
どっちが可読性があるの？
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
757 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 20:34:20.88 ID:zGjt7Ia9 - ああ、ちなみにπの漸化式は
2(1+(1/3)+(1/3)(2/5)+(1/3)(2/5)(3/7)+...)
だからね
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
758 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 20:49:22.97 ID:zGjt7Ia9 - 変数名がごっちゃにならないように書き直し
double calcPI(double r, double s, double n) {
double u = 1.0;
if (s == 1) u = 2.0;
if (n == 1) return r;
return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
double u = 2.0;
while (1 < n) {
t = (t * s / (2.0 * s + 1.0));
r = r + t;
s += 1;
n -= 1;
}
return u * r;
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
759 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 21:09:08.26 ID:zGjt7Ia9 - 完全に同じ処理にしたけど、どっちが楽なんだろうね？
double calcPI(double r, double s, double n) {
double u = 1.0;
if (s == 1) u = 2.0;
if (n == 0) return r;
return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1));
}
double calcPI3(double n) {
double r = 1.0;
double s = 1.0;
double t = 1.0;
double u = 1.0;
while (0 < n) {
t = t * s / (2.0 * s + 1.0);
r = u * (r + t);
s += 1;
n -= 1;
}
u = 2.0;
return u * r;
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
760 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 21:16:59.43 ID:zGjt7Ia9 - 我々は「軍国主義者」を打倒したと、我らが「軍事パレード」で宣言
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
762 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 21:55:59.06 ID:zGjt7Ia9 - コンパイラ入れんのめんどくさいからパス
#include <iostream>
void init(int * p, int n) {
for (; 0 < n; n--) p[n] = 0;
}
void disp(int * p, int n) {
std::cout << std::endl;
for (int i = 0; i < n; i++) std::cout << p[i] << " ";
std::cout << std::endl;
}
int recUnit(int i, int j, int *a, int na, int *b, int nb) {
if (i < na && j < nb) a[i] = b[j];
else return i;
return recUnit(i + 1, j + 1, a, na, b, nb);
}
void unit(int *a, int na, int *b, int nb, int *c, int nc) {
int i;
i = recUnit(0, 0, a, na, b, nb);
recUnit(i, 0, a, na, c, nc);
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
763 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 21:56:37.35 ID:zGjt7Ia9 - void unit2(int *a, int na, int *b, int nb, int *c, int nc) {
int i, j;
for (i = 0, j = 0; j < nb; i++, j++) if (i < na)a[i] = b[j];
for (j = 0; j < nc; i++, j++) if (i < na)a[i] = c[j];
}
int main()
{
int a[10], b[5] = { 0, 1, 2, 3, 4 }, c[5] = { 5, 6, 7, 8, 9 };
init(a, 10); unit(a, 10, b, 5, c, 5); disp(a, 10);
init(a, 10); unit2(a, 10, b, 5, c, 5); disp(a, 10);
return 0;
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
764 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 22:03:28.78 ID:zGjt7Ia9 - ミスった
#include <iostream>
void init(int * p, int n) {
for (; 0 < n; n--) p[n - 1] = 0;
}
void disp(int * p, int n) {
std::cout << std::endl;
for (int i = 0; i < n; i++) std::cout << p[i] << " ";
std::cout << std::endl;
}
int recUnit(int i, int j, int *a, int na, int *b, int nb) {
if (i < na && j < nb) a[i] = b[j];
else return i;
return recUnit(i + 1, j + 1, a, na, b, nb);
}
void unit(int *a, int na, int *b, int nb, int *c, int nc) {
int i;
i = recUnit(0, 0, a, na, b, nb);
recUnit(i, 0, a, na, c, nc);
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
766 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 22:24:32.63 ID:zGjt7Ia9 - ちゃんと出来てるかこっちのほうがいいか
void unit2(int *a, int na, int *b, int nb, int *c, int nc) {
int i, j;
for (i = 0, j = 0; j < nb; i++, j++) if (i < na) a[i] = b[j];
for (j = 0; j < nc; i++, j++) if (i < na) a[i] = c[j];
}
int main()
{
int a[10], b[4] = { 0, 1, 2, 3 }, c[6] = { 4, 5, 6, 7, 8, 9 };
init(a, 10); unit(a, 10, b, 4, c, 6); disp(a, 10);
init(a, 10); unit2(a, 10, b, 4, c, 6); disp(a, 10);
return 0;
}
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
767 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 22:31:18.83 ID:zGjt7Ia9 - 最適化されているのはループで
漸化式定義に忠実で書きやすいのが再帰だよ
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
768 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 22:33:05.45 ID:zGjt7Ia9 - >>757
>>759
>>767
|
- なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
769 ：NAS6 ◆n3AmnVhjwc []：2015/09/05(土) 22:47:45.27 ID:zGjt7Ia9 - void recForFunc() { ; }
int recFor(int i, int n, int a) {
if (n <= i) return i;
recForFunc();
return recFor(i + a, n, a);
}
std::cout << recFor(0, 10, 2) << std::endl;
for (i = 0; i < 10; i += 2) recForFunc();
std::cout << i << std::endl;
ループと再帰の違いは
スコープスタックを保存しているかしていないかだけ
|