再帰

163 ：デフォルトの名無しさん：01/10/22 01:44

数学では割と普通の概念なのに、
プログラミングではスタックが出てくるから分かりにくいのだろうか？

164 ：デフォルトの名無しさん：01/10/22 02:36

>>163
それは違うだろ…
C だろうとスタックは透過的なわけだし…

そもそもわかりにくいのか?

165 ：デフォルトの名無しさん：01/10/22 07:56

馬鹿がわからんだけだよ。(で、「非効率」だと騒ぐ)
「普通の概念」っつっても「数列」挫折したような奴には難しいだろ。

166 ：デフォルトの名無しさん：01/10/22 11:38

たしかVBだと再帰ができなかったような、、、
再帰が嫌いなやつってVBプログラマか？

167 ：名梨産：01/10/22 15:08

>>163
スタックって、CPUのSPの事指してる？
スタックの動作をしたいだけならSPにあたる添字をキチンと制御してやれば
ただの配列変数でできるでしょ？特に解りにくいとは思わないけど。

>>166
VBでもできますよん。前に数式解析のルーチン作ったとき使った。

168 ：デフォルトの名無しさん：01/10/22 15:16

ルート検索とか再帰使って関数を単純化できた。
便利なもん使ってなんか不都合あるんだろうか？

169 ：デフォルトの名無しさん：01/10/22 16:05

再帰。

どうして俺は再帰がきらいなんだろう。
悩んだ。
数日間それでなやんだ。
そしてとうとう結論を得た。
再帰するからだ。

170 ：デフォルトの名無しさん：01/10/22 16:05

>>168
ネストし過ぎるとタックオーバーフローで止まる（最悪、暴走する）プログラムになる。
クイックソートの様な指数オーダーの再帰ではそんなにネストする事は無い。

171 ：デフォルトの名無しさん：01/10/22 16:06

void bin2oct(unsigned n)
{
if (n != 0)
bin2oct(n / 8);
putchar(n % 8 + '0');
}

172 ：デフォルトの名無しさん：01/10/22 16:11

>>170
どこまでネタなんだか（藁

指数オーダーってO(k^n)のことだぞ。
チェックしないとダメなのは配列＋ループでも同じだろう。
暴走する可能性は素直な再帰の方が低いと思うが。
（Winとかってスタックチェックやってくれないのかな？）

173 ：デフォルトの名無しさん：01/10/22 18:31

>>169
面白い

>>170
対数

174 ：≠１６９：01/10/22 18:55

再帰。

論点をまとめずに思考を進めてしまい、
再帰から抜けられないでいる。

175 ：173：01/10/22 21:40

>>174
面白くない

176 ：デフォルトの名無しさん：01/10/23 22:59

Lisp でたらい回し関数やアッカーマン関数を実行させて
処理系の実行速度を測ったりしたな

177 ：デフォルトの名無しさん：01/10/23 23:40

「自分自身を起動せよ」

この1行を書いたプログラムを実行するだけで、
あなたも再帰を体感できます。

178 ：デフォルトの名無しさん：01/10/24 00:00

>>177
ブラクラに実装されてることが多いな。

179 ：デフォルトの名無しさん：01/10/24 00:46

>>177
ロボット（腕だけのキット）をコントロールして自分自身のスイッチを切らせた人を知ってる…

180 ：デフォルトの名無しさん：01/10/24 10:00

いや再帰スレなんだから　ロボットにロボットを作らせなくちゃダメだろ

181 ：デフォルトの名無しさん：01/10/24 10:43

終了条件のない再帰ってありなの？

よくありがちな
カレントディレクトリ以下の構造を再帰的に出力する、
というのを作りました。

いま手元にコードがないので擬似で。

void ls( char *name)
{
　dp = opendir(name);

　/* opendirで読んだディレクトリの中の　ファイル/ディレクトリをすべて得る */
　while( (dirp = readdir(dp)) != null )
　{
　　print "%s\n",dirp -> name;

　　/* .（カレントディレクトリ、 .. (一個上のディレクトリは無視) */
　　if( dirp -> name == "." ||
　　　　dirp -> name == ".." )
　　{
　　　continue;
　　}

　　/* そいつがディレクトリだったら、再帰的に */
　　if( dirp -> kind == directori )
　　{
　　　ls( dirp -> name ):
　　}
　}
}

int main(void)
{
　ls(".");
　return 0;
}

182 ：デフォルトの名無しさん：01/10/24 12:01

>>181
>>終了条件のない再帰ってありなの？
スタック食いつぶす分無限ループよりタチが悪いな。
いや、スタックオーバーフローでOSがトラップしてくれる分
かえって発見し易いか？

>>カレントディレクトリ以下の構造を再帰的に出力する、
って事ならその「処理中のディレクトリにサブディレクトリがない」
ってのが終了条件になってるし。

183 ：デフォルトの名無しさん：01/10/24 18:13

再帰の、最も簡単な分類にはいる関数だと思われる。

double power(double base, int ex){
　if (ex == 0) return 1;
　if (ex >= 1)
　　return base * power(base, ex-1);
　else
　　return 1/power(base, -ex);}

184 ：デフォルトの名無しさん：01/10/24 22:07

そのtail recursion板。

inline double power(double base, int ex){
if (ex >= 0)
return power1(base, ex, 1);
else
return 1/power1(base, -ex, 1);}
double power1(double base, int ex, int acc){
　if (ex == 0) return acc;
　if (ex >= 1)
　　return power1(base, ex-1, base * acc);}

185 ：デフォルトの名無しさん：01/10/25 09:34

再帰の定番　アッカーマン

int ack(int x, int y)
{
　if (x == 0) return y + 1;
　if (y == 0) return ack(x - 1, 1);
　　　　　　　　return ack(x - 1, ack(x, y - 1));
}

186 ：あげ：01/10/26 02:03

日本人の心たらいまわし

int tarai(int x, int y, int z)
{
　if (x <= y) return y;
　return tarai( tarai(x - 1, y, z),
　　　　　　　　tarai(y - 1, z, x),
　　　　　　　　tarai(z - 1, x, y));
}

from 奥村晴彦、C言語による最新アルゴリズム事典

187 ：デフォルトの名無しさん：01/10/26 02:05

unsigned get_int_value(unsigned value)
{
if(value==0)
return 0;
else
return get_int_value(value-1) + 1;
}

188 ：デフォルトの名無しさん：01/10/26 02:09

>>183
それは使いどころ間違ってるよ。

double power(double base, double ex)
{
return exp(ex * log(base));
}
だろ。

189 ：デフォルトの名無しさん：01/10/26 04:08

>>186は何に使うのですか？

190 ：デフォルトの名無しさん：01/10/26 04:36

>>189
ベンチマーク

191 ：デフォルトの名無しさん：01/10/27 00:42

>>188
183じゃないが、expとlogを使うより精度が高い。

192 ：デフォルトの名無しさん：01/10/27 03:37

>>191
でも遅い。整数乗しか扱えない。