163 :
デフォルトの名無しさん:01/10/22 01:44
数学では割と普通の概念なのに、
プログラミングではスタックが出てくるから分かりにくいのだろうか?
>>163 それは違うだろ…
C だろうとスタックは透過的なわけだし…
そもそもわかりにくいのか?
165 :
デフォルトの名無しさん:01/10/22 07:56
馬鹿がわからんだけだよ。(で、「非効率」だと騒ぐ)
「普通の概念」っつっても「数列」挫折したような奴には難しいだろ。
たしかVBだと再帰ができなかったような、、、
再帰が嫌いなやつってVBプログラマか?
>>163 スタックって、CPUのSPの事指してる?
スタックの動作をしたいだけならSPにあたる添字をキチンと制御してやれば
ただの配列変数でできるでしょ?特に解りにくいとは思わないけど。
>>166 VBでもできますよん。前に数式解析のルーチン作ったとき使った。
ルート検索とか再帰使って関数を単純化できた。
便利なもん使ってなんか不都合あるんだろうか?
169 :
デフォルトの名無しさん:01/10/22 16:05
再帰。
どうして俺は再帰がきらいなんだろう。
悩んだ。
数日間それでなやんだ。
そしてとうとう結論を得た。
再帰するからだ。
>>168 ネストし過ぎるとタックオーバーフローで止まる(最悪、暴走する)プログラムになる。
クイックソートの様な指数オーダーの再帰ではそんなにネストする事は無い。
void bin2oct(unsigned n)
{
if (n != 0)
bin2oct(n / 8);
putchar(n % 8 + '0');
}
>>170 どこまでネタなんだか (藁
指数オーダーってO(k^n)のことだぞ。
チェックしないとダメなのは配列+ループでも同じだろう。
暴走する可能性は素直な再帰の方が低いと思うが。
(Winとかってスタックチェックやってくれないのかな?)
再帰。
論点をまとめずに思考を進めてしまい、
再帰から抜けられないでいる。
176 :
デフォルトの名無しさん:01/10/23 22:59
Lisp で たらい回し関数やアッカーマン関数を実行させて
処理系の実行速度を測ったりしたな
177 :
デフォルトの名無しさん:01/10/23 23:40
「自分自身を起動せよ」
この1行を書いたプログラムを実行するだけで、
あなたも再帰を体感できます。
179 :
デフォルトの名無しさん:01/10/24 00:46
>>177 ロボット(腕だけのキット)をコントロールして自分自身のスイッチを切らせた人を知ってる…
いや再帰スレなんだから ロボットにロボットを作らせなくちゃダメだろ
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;
}
>>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);}
その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);}
再帰の定番 アッカーマン
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));
}
日本人の心 たらいまわし
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
190 :
デフォルトの名無しさん:01/10/26 04:36
>>188 183じゃないが、expとlogを使うより精度が高い。
193 :
デフォルトの名無しさん:01/10/31 20:04
>>192 ヤパーリ、テイラー展開を使うべきか?
194 :
デフォルトの名無しさん:01/10/31 20:05
しかし、プログラムを書くにはそんなに
数学を勉強しないといけないの?
線形代数とかまで要求されるジャン・・・
>>193 expは(ハードがやってくれなきゃ)当然多項式で近似するんだよ。
テイラーじゃなくてチェビシェフが普通だろうけど。
>>194 expを書こうなんて思えばね。
196 :
デフォルトの名無しさん:01/10/31 20:16
線形代数って、一次関数のことじゃないの?
線形代数って普通はベクトルとか行列の話だよね。
ふつーもクソもあるか。
われわれ工学部の強力な武器です。
>>194 画像・音声など信号処理にはもちろん必要。
プログラミング一般においても数学的なセンスは必要だね。
演繹的・帰納的にアルゴリズムを組み立て解を出す様は
数学もプログラムもよく似ている。
良スレage
age
203 :
デフォルトの名無しさん:01/12/25 23:58
涼スレ?
205 :
デフォルトの名無しさん:02/02/02 18:33
情報工学生には一読の価値あり age
206 :
デフォルトの名無しさん:02/02/25 00:07
age
209 :
デフォルトの名無しさん:02/04/23 22:32
210 :
デフォルトの名無しさん:02/04/23 22:58
マトリョーシカ
蛇足だけど、staticな関数の自己末尾再帰はgcc(2.95.4で試した)で
最適化させた場合、goto相当に展開する。
どうやったらわかるの?
アセンブラがわからないとだめ?