トップページ⇒tech
212コメント51KB

再帰

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842
0002デフォルトの名無しさんNGNG
再帰の意味も理解できないｳﾞｧｶ発見！
0003デフォルトの名無しさんNGNG
>>2
お前は再帰の意味がわかってるのか？
そうなら、是非解説してください。

ちなみに結構広い意味で使われてるのよ。
http://dictionary.goo.ne.jp/cgi-bin/dict_search.cgi?MT=%BA%C6%B5%A2&sw=2
0004デフォルトの名無しさんNGNG
このスレどうやって立てたの??
00054NGNG
…と思ったら、hidden の中に時刻入ってるじゃん。なーんだ。
0006デフォルトの名無しさんNGNG
>>2
自己参照も再帰の一種かと。
00071NGNG
>>4-5
でもタイミングが難しいのよ。
0008デフォルトの名無しさんNGNG
>>2は基底がないと再帰じゃないと思っているとか。
0009デフォルトの名無しさんNGNG
このスレは糞スレリサイクル法にもとづき、ただいまより
「再帰について語るスレ」と致します。
0010デフォルトの名無しさんNGNG
>>4
どういうこと？未だにどうやって立てたのかわからん
0011デフォルトの名無しさんNGNG
>>1の投稿時間を考えると、なかなか評価できるな
001211NGNG
って全然関係ねぇや＜タイミング
むっちゃ簡単じゃんよ
00131NGNG
>>7の補足
>>5
hiddenの値がスレ番になるわけじゃないかと。
CGIがリクエストを受け付けた時刻っぽい。
0014NanasshyNGNG
One day a student came to Moon and said: "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons."

Moon patiently told the student the following story:

"One day a student came to Moon and said: `I understand how tomake a better garbage collector...

[Ed. note: Pure reference-count garbage collectors have problems with circular structures that point to themselves.]
0015デフォルトの名無しさんNGNG
俺には、適当にスクリプトでも組んで、
適当なリクエストでサーバータイムとの差をms単位で算出してから、
余裕があるタイミングでポストする(ping値も参考にする？)
これ位しか、やりかたを思いつかない。
0016デフォルトの名無しさんNGNG
１みたいな人が、ハッカーになるんでしょうね。
001711NGNG
>>13
ああそうなのか。疑ってスマソ
0018デフォルトの名無しさんNGNG
再帰とゆーか、ループっちゃってGCできなくなっちゃった
リストとゆーか...
00191NGNG
>>16
虐めないでくれ…
0020デフォルトの名無しさんNGNG
これも１だろ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241448
sageで立てたから気付かれなかったけど。
0021デフォルトの名無しさんNGNG
これでテストしたんだな。8秒ずれ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241080
0022デフォルトの名無しさんNGNG
すごい
0023デフォルトの名無しさんNGNG
クソスレリサイクル法に従い再帰の話題をば

再帰を人に教えるのは難しい。
ハノイの塔とかグラフィックを使うのとかは相手のレベルが低いと辛いし。
0024デフォルトの名無しさんNGNG
>>23
８クイーンじゃだめ？陳腐すぎますか？
0025デフォルトの名無しさんNGNG
アッカーマソ関数は?
0026デフォルトの名無しさんNGNG
>>23
まずクイックソートでおしえれよ
002723NGNG
>>24
いきなりバックトラックだとちょっといやかな、とは思ったんですが。
ディレクトリを奥まで探っていく感じのサンプルがいいんだけど、
伝えたい感覚わかるかな？

>>25
ネタだよね（藁

>>26
理解してもらえませんでした（涙）
0028デフォルトの名無しさんNGNG
再帰的定義: GNU = "GNU is Not Unix!"
再帰的動作: function qsort(0,n) = qsort(0,n/2); qsort(n/2+1, n);
0029デフォルトの名無しさんNGNG
CFGで教えるというのはどうか。
0030デフォルトの名無しさんNGNG
無難に階乗とフィボナッチ
0031デフォルトの名無しさんNGNG
ターミネーター２で最後、敵のロボが溶鉱炉に落ちて口から顔が出て
そのまた口から顔が出て来るのを見て再帰を理解しましたｗ
0032デフォルトの名無しさんNGNG
&d('.');sub d{opendir D,$_[0];my@a=grep!/^\.\.?$/,readdir D;closedir D;
foreach(@a){printf"%".length($b="$_[0]\\$_")."s\n",$_;&d("$b")if(-d$b)}}

さぶでれくとり一覧を表示するperlスクリプト
0033デフォルトの名無しさんNGNG
Ｃで教えるにはANSIにこだわると難しいらしいな。
グラフィックで雪印やドラゴンカーブを書かせれば
すぐに理解できるとは思うけれど
0034デフォルトの名無しさんNGNG
ファイル検索のアルゴリズムは再帰？
0035>>34NGNG
検索関数でサブディレクトリ（フォルダ）が見つかったら
そのフォルダ相手に検索関数を実行する再帰手法が一般的
というか他のやり方はすぐに思いつかないのだが。
そういえばANSIにファイル検索関数ってなかったっけ。
0036デフォルトの名無しさんNGNG
>>33
Cで再帰を教える代表的なものは、クイックソートだな。

>>35
それは深さ(縦)優先の再帰。逆の再帰もあるだろ。
深さ優先は使用メモリは最小限にできるが、
その深さに比例してハンドルをオープンしっぱなしにしなければならない。
0037デフォルトの名無しさんNGNG
>>36
逆の再帰って何ですか？
0038デフォルトの名無しさんNGNG
lispヤレヤ
0039デフォルトの名無しさんNGNG
逆というか一般的に探索戦略は、深さ優先と幅優先の二種類がある。
0040デフォルトの名無しさんNGNG
幅優先ってどんなの？具体例だけでもいいから希望
0041デフォルトの名無しさんNGNG
幅を優先いたしまーす。
0042デフォルトの名無しさんNGNG
>>23
K&R(第一版)にのってる数字を表示するやつは結構簡単でいいと思う。
0043デフォルトの名無しさんNGNG
23じゃないけど>>42
K&R、持ってない。どんなの？
0044デフォルトの名無しさんNGNG
aaa
　bbb
　　ccc
　ddd

という階層構造があった場合、
aaa->bbb->ccc->dddと上から(?)順番に探してくのが深さ優先
aaa->bbb->ddd->cccと浅い順から探してくのが幅優先。
無限に(あるいは十分に)深い階層を探索する場合はこっちが有効な場合が多い。
ただメモリを馬鹿食いする。
004540NGNG
>>44
tnx.
0046デフォルトの名無しさんNGNG
>>43
printd(int n) /* nを10進数で表示 */
{
 int i;

 if (n < 0) {
  putchar('-');
  n = -n;
 }
 if ((i = n/10) != 0)
  printd(i);
 putchar(n % 10 + '0');
}

再帰使わない例も載ってて、それと比べると再帰の良さがわかりやすい。
004739NGNG
オセロや将棋などのゲームで考えると分かりやすいと思う。
次の手、その結果に対して次の手とどんどん先読みしていくのが深さ優先。
次の手には何があるのかを全て調べてから、その次の手を調べるのが幅優先。
0048デフォルトの名無しさんNGNG
なるほど、さすがK&R。わかりやすい。
情報ありがとう>>46
0049デフォルトの名無しさんNGNG
階乗とか最大公約数とか。
0050デフォルトの名無しさんNGNG
>>49
再帰の例として良く見かけますけど、
階乗は、あまりメリットが見えないので、
n個以上(n>1)の数の最大公約数が良いかと…。
0051デフォルトの名無しさんNGNG
全数探索を行うときに再帰を使った。
当然、全数探索にはO(2^n)かかるのを承知でだが。
指数オーダーはいかんよ。今さらだけど。
0052デフォルトの名無しさんNGNG
宣教師と人食い土人
0053デフォルトの名無しさんNGNG
バックトラック問題はみんな再帰
0054デフォルトの名無しさんNGNG
スゲェ。
ちと感動したよ。>>1
一発ネタだが、名スレだ。
0055デフォルトの名無しさんNGNG
再帰呼び出しを使わずに再帰を実装する方法も考えてみよう

って優香、クイックソートの実装に再帰を使うのはヤメレ
0056デフォルトの名無しさんNGNG
>>55
再帰を使うのはサンプルだけだろ
0057デフォルトの名無しさんNGNG
ワイルドカードプログラムはどうだろうか？
0058デフォルトの名無しさんNGNG
>>56
再帰をスタックに直すプログラム書いてくれ。
0059デフォルトの名無しさんNGNG
再帰のコードを１とすると、
再帰使わない方法（スタック）は２以上の工数がかかる。
0060デフォルトの名無しさんNGNG
Q.

>>1を再帰を使わずに表現しなさい。
0061デフォルトの名無しさんNGNG
>>55
　えっ！？なんで！？厨房なんでわからない。
教えて
0062デフォルトの名無しさんNGNG
Win2000で試したら、窓380個(推定)まで開けたよ>>1
0063デフォルトの名無しさんNGNG
>>61
ｻｲｷﾊｼｮﾘｶﾞｱﾏﾘﾊﾔｸﾅｲ
0064デフォルトの名無しさんNGNG
>>61
1. 速度が遅い

2. スタックサイズは制限がある環境が多く、エラーハンドリングが面倒

　 ヒープならメモリ確保する時に正否が分かるが、スタックだと失敗した
　 瞬間にシグナル (しかも環境によっては SIGKILL) 飛んできたりするし。
0065デフォルトの名無しさんNGNG
58 名前：デフォルトの名無しさん 投稿日：2001/06/20(水) 23:56
>>56
再帰をスタックに直すプログラム書いてくれ。

これ作れば再帰で書いても良いんじゃない？
0066デフォルトの名無しさんNGNG
>>64
POSIXならsigaltstack()が使えるが、
スタックが溢れたのかそうでないかを判別する手段がないんだよな。
なんかいい手知らない?
006761NGNG
　ふーむ。そうだったのか。
一つ賢くなったよ。アリガトホ
0068デフォルトの名無しさんNGNG
>再帰をスタックに直すプログラム書いてくれ。
同じく
0069デフォルトの名無しさんNGNG
再帰をやめれば自分で管理できるかと。
0070デフォルトの名無しさんNGNG
59 名前：デフォルトの名無しさん 投稿日：2001/06/20(水) 23:59
再帰のコードを１とすると、
再帰使わない方法（スタック）は２以上の工数がかかる。
0071デフォルトの名無しさんNGNG
>>58
なぜ俺に言う。
しかも、ループに展開できるのは末尾再帰だけだ
0072デフォルトの名無しさんNGNG
>>64 qsortならスタックのサイズは高々 log n じゃない?
それから、再帰呼びだしのオーバーヘッドて
自分でスタック実装したときよりもそんなにデカいものなんですか?
アセンブラレベルで比べたことがないからわからない。
0073デフォルトの名無しさんNGNG
>>70
状況によって違う。
一般論では語れない。
0074デフォルトの名無しさんNGNG
>>74
おまえもなー。
0075デフォルトの名無しさんNGNG
>>74
ナイス！ワラタ
0076デフォルトの名無しさんNGNG
>>72
違うよ。
クイックソートは平均がO(logN)なだけで、最悪の場合はO(N)になる。
0077デフォルトの名無しさんNGNG
>>72　>>76
クイックソートはO(n log n)。
最悪はO(n^2)。（避けれるように出来るけど）

>>72
> それから、再帰呼びだしのオーバーヘッドて
> 自分でスタック実装したときよりもそんなにデカいものなんですか?

結構でっかいような気はするなぁ。
0078デフォルトの名無しさんNGNG
スタック
if (sp == stack_num) stack = realloc(stack, stack_num *= 2);
stack[sp++] = val;

再帰
f(val);

スタックは毎回
・オーバーフロー判定（最初に見積もれれば不要）
・インデクス参照代入
・spの増加

再帰は毎回
・関数呼出し（オーバーフローは判定不能）
が必要。
0079デフォルトの名無しさんNGNG
>>78
> ・インデクス参照代入
> ・spの増加

popは…。

> ・関数呼出し（オーバーフローは判定不能）

これがでかいよね。
レジスタ退避させたり。
008077NGNG
あ、ごめん。
O(log n)ってスタックのサイズの話ね……。
0081デフォルトの名無しさんNGNG
再帰→スタック変換を人間が行なうと、
プログラム意味論的(よく知らんけど)に、
「再帰構造である」という主張が薄れるって害は無い？
（forやwhileをgotoに直す様な事と同等）
C->ASMの様に、
機械的（暗黙的に）にやらせるのが理想だと思うんだけど。
0082デフォルトの名無しさんNGNG
>>77
計算量ではなくてスタックの深さの話だと思うが

>>76
末尾再帰を上手く使えば O(log N)で抑えられる。
小さいブロックを先に片づけるのだ
0083デフォルトの名無しさんNGNG
>>81
まあね。
でも意味重視で性能悪いのは・・・ね。

まあ、理解不能になるわけじゃないしいいんじゃない？
0084デフォルトの名無しさんNGNG
>>82
小さいブロックを先に…って話じゃ無理かと。

二つに分ける時に、片寄らないようにしないとイカン。
0085ageNGNG
age
0086デフォルトの名無しさんNGNG
ニホンジンハウソツキ
0087>>50NGNG
＞再帰の例として良く見かけますけど、
＞階乗は、あまりメリットが見えないので、
＞n個以上(n>1)の数の最大公約数が良いかと…。

nが２個ならユーグリッドの互除法だよね。
３つ以上ならどのように再帰で表現する？
出来なくないですか？
0088デフォルトの名無しさんNGNG
GCD(n1, n2, ..., nm) <= GCD(n1, GCD(n2, ..., nm)).
じゃないの？
0089デフォルトの名無しさんNGNG
ネタスレがこんな良スレに育って・・・父さん嬉しいぞ
0090本ヲタNGNG
The Little Schemer
http://www.amazon.com/exec/obidos/ASIN/0262560992/002-6796989-4387263

The Seasoned Schemer
http://www.amazon.com/exec/obidos/ASIN/026256100X/002-6796989-4387263

A Little Java, a Few Patterns
http://www.amazon.com/exec/obidos/ASIN/0262561158/002-6796989-4387263

http://www.cs.rice.edu/~matthias/TLS/
http://www.cs.rice.edu/~matthias/TSS/
http://www.cs.rice.edu/~matthias/Javar/

リスト遊び
http://www.kame.net/~kazu/book/list.html
http://www.ascii.co.jp/books/detail/4-7561/4-7561-3442-4.html
http://www.amazon.co.jp/exec/obidos/ASIN/4756134424/249-7473945-9268357
0091デフォルトの名無しさんNGNG
実際問題、
「（末尾再帰ではない）再帰→スタック＋ループ」
変換は機械的に可能でしょうか？
0092デフォルトの名無しさんNGNG
>>91
可能でしょ。
アセンブラレベルでは「スタック＋ループ」みたいなもんじゃん。
あれがcallとretでなくjmp+αだったらいいだけでしょ？
# これは可能っていう根拠について書いてるので
# 上記の方法でやれってのとは違うです。
0093デフォルトの名無しさんNGNG
age
0094デフォルトの名無しさんNGNG
>>92
アセンブラにした所で、再帰構造のコードはずっと再帰ですが。
0095デフォルトの名無しさんNGNG
じゃあ、「再帰」と「スタック+ループ」の違いは?
PCをスタックに積むかどうか?
009696NGNG
>>96
オマエモナー（気に入ったらしい）
009774NGNG
>>97
パクルなＹＯ！（ちょっとしつこいな・・・）
0098デフォルトの名無しさんNGNG
　順列の生成を再帰を使わずにやってみた事が有るけど、パフォーマンスは
確かに上がるね。ソースは汚くなるけど。
0099デフォルトの名無しさんNGNG
いまさらだけど、schemeというlisp系言語やMLなどの関数型言語は
言語規約として末尾再帰(単体/相互)をgoto相当に展開する。
普通の再帰は知らないけど。
表現能力は、
再帰＞スタック＋ループ
0100デフォルトの名無しさんNGNG
100!
0101デフォルトの名無しさんNGNG
101!
0102デフォルトの名無しさんNGNG
>>103
0103デフォルトの名無しさんNGNG
>>102
010498NGNG
そういえばあの時順列のアルゴリズムを追求してすごいの作ったつもりに
なってたけど、ある本を読んだら最少順序変換法って名前が付いてた。
車輪を再発明してたのが判ってしばらく鬱だったよ。

>>102,103
入り口が複数なのね。
0105デフォルトの名無しさんNGNG
>>104
そうやって、人は一歩ずつ成長して行く
0106デフォルトの名無しさんNGNG
アルゴリズム言語Schemeに関する第五改訂報告書
http://www.sci.toyama-u.ac.jp/~iwao/Scheme/r5rsj/html/r5rsj.html#SEC2
>繰り返しを表現する場合に手続き呼び出しのみを使用することによって、
>終端再帰的手続き呼び出しが本質的に引数を渡すgotoであることが、Schemeでは強調されている。
0107デフォルトの名無しさんNGNG
>>99 単純にそうは言えないだろ。
暗黙の制御スタック一つしかない再帰に比べれば、明示的な
スタックは複数もつことができて、より細かい制御はできるし。
まあ、安直なものは再帰のほうが楽にかけて、
世の中安直で十分な場合も多いというのは真だけど。
0108デフォルトの名無しさんNGNG
なんだぁ、リカーシブって
再び呪いをかけられることかと思ってたよ
0109デフォルトの名無しさんNGNG
>>108
Bit悪魔の辞典ですか（笑）
0110>108NGNG
そりゃ、リ・カース(re-curse)
0111デフォルトの名無しさんNGNG
難しいボケとツッコミだなぁ
01121NGNG
うんち
0113デフォルトの名無しさんNGNG
>>112
1がコレだもんなぁ
0114デフォルトの名無しさんNGNG
>>113
ナイーブな対応。再帰にしてみよう
01151(本物)NGNG
>>113
>>112は騙りです。
0116デフォルトの名無しさんNGNG
再帰することはオブジェクト指向的に見てどう？
0117再帰NGNG
人をバカって言うヤツがバカ。
0118デフォルトの名無しさんNGNG
人をバカって言うやつがバカって言うやつが…

Stack overflow
0119デフォルトの名無しさんNGNG
>>118
ほぉら、再帰に入る前に脱出の手段考えてないからこんなことに…
0120デフォルトの名無しさんNGNG
>>118-119
ワラタ。おもろい
0121116NGNG
なるほどそういうことか！
目から鱗だね！
0122デフォルトの名無しさんNGNG
良スレ
0123＃6411NGNG
良スレ
>>16 >>19 他称ハッカーは尊称、ということにしとこうや。
0124デフォルトの名無しさんNGNG
末尾再帰ぐらい展開しろやボケェ！
って状況になるといいね。
0125デフォルトの名無しさんNGNG
>>121 は、どのカキコをみて >>116 の解を見つけたのか謎である。
0126デフォルトの名無しさんNGNG
ほんと、謎だね。
0127116=121=125NGNG
ｼﾞｻｸｼﾞｴﾝﾃﾞｼﾀ (o^ー')b
0128末尾再帰？NGNG
http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842
0129デフォルトの名無しさん01/08/28 16:05ID:4ABH04kY
>>128
残念。
0130デフォルトの名無しさん01/09/01 19:38ID:BF0ekyhU
sage
0131デフォルトの名無しさんNGNG
age
0132デフォルトの名無しさんNGNG
>>131
そんな・・・
意味もなくageなくても・・・
0133デフォルトの名無しさんNGNG
上がってたので読んでみた。
再帰使うと深さ優先の探索になるんだよね? 広さ優先と再帰って組めない？
0134デフォルトの名無しさんNGNG
>>133
オブジェクトのメソッドを呼び出すような再帰(？)なら可能だろ。
処理のメソッドと子供を辿るメソッドを分けて、前者をすべての
子供に対して読んでから後者を呼べばいい。
0135デフォルトの名無しさんNGNG
makeの再帰呼び出しにはちょっと感動した
0136デフォルトの名無しさんNGNG
>>135
何のMakefileか教えてくれー。見てみたいー。
0137佐伯NGNG
prologって言語ではループ＝再帰だよ！
0138デフォルトの名無しさんNGNG
wshでサブディレクトリのファイルを移動するコードを書きたいんだけれど、
どうやって「深さ優先」と「幅優先」を書き分けたらいいでしょうか？

良いアドバイスがあったらよろしくお願いします。
0139デフォルトの名無しさんNGNG
>>135
サブディレクトリに移動してmakeってやつ? ごく普通だろ。

>>136
linuxカーネルとかemacsのソースでも見てみ。
まぁライブラリを作ったりする場合は常識だな。
0140デフォルトの名無しさんNGNG
shr
0141デフォルトの名無しさんNGNG
>>139
たまに間違ってfork爆弾になってるMakefileもあるな。
0142デフォルトの名無しさんNGNG
>>138
再帰なんか要らないよ
切り替えも簡単

幅優先:
O = 空リスト
Oにコピー元を入れる
while (Oが空でない) {
　n = Oの先頭のファイル
　if (nがディレクトリ) {
　　コピー先にnを作る
　　nの子を全部Oの末尾に追加
　} else
　　nをコピー
}

深さ優先:
O = 空リスト
Oにコピー元を入れる
while (Oが空でない) {
　n = Oの先頭のファイル
　if (nがディレクトリ) {
　　コピー先にnを作る
　　nの子を全部Oの先頭に追加
　} else
　　nをコピー
}
0143138NGNG
>>142
さんきゅーです。さっそくやってきます￥
0144デフォルトの名無しさんNGNG
っていうか、俺は職業プログラマだが、
プロになってから一度も再帰なんて使ったこと無いぞ。
せいぜい、加減乗除とルートまで。

面倒な処理はライブラリがやってくれるから、再帰なんて勉強しないで
ＵＭＬとかやったほうが役に立つぞ。
再帰なんて研究者か学生専門だね。
0145デフォルトの名無しさんNGNG
再帰は基礎教養として必須に一票。
0146143NGNG
>>145
まぁ、学生のうちはアルゴリズムの勉強で大いにやるべき。
むしろ、やらなきゃダメ。アイディアの元になるからね。

だけど、現場では全然使わないよ。
0147146NGNG
済まん、名前間違えた。
>>146の名前欄は「144」ね。
0148デフォルトの名無しさんNGNG
>>144-145

もう煽り誘導レスは飽きた。
0149144NGNG
別に煽ってないよぉ・・・
意見を言っただけなのに・・・
0150デフォルトの名無しさんNGNG
>>149
確かに、スタック積んで降ろして積んで降ろして･･･という動作を想像して鬱になってしまうので、
再帰を採用する前に他のアルゴリズムが無いか検討はしてみることが多いな。
でも再帰は書いてて気持ちいいね。
0151デフォルトの名無しさんNGNG
すまん、仕事でバリバリに使ってる。
個人的に好きなんで。
0152デフォルトの名無しさんNGNG
>>144
あんまり複雑なデータ構造は使わないんだな。
いや悪いといってるんじゃないので。
できる限り単純なほうがいいのは当り前だから。

> 面倒な処理はライブラリがやってくれるから、再帰なんて勉強しないで
でも再帰ひとつ満足に使えないのは論外。
0153デフォルトの名無しさんNGNG
>>151
使うなよ。
見た目が直感的に成る以外のメリットは無いだろ
0154デフォルトの名無しさんNGNG
コードが短くなるメリットがあるよ。

　ネストが　log(N) の場合なら問題ないでしょ

　問題ってのはスタックサイズや処理コストの事ね
0155デフォルトの名無しさんNGNG
俺は、あまり苦労しないで再帰は理解できたよ。
ファイル検索なんか、再帰便利だし。
0156デフォルトの名無しさんNGNG
再帰の理解に苦労するやつなんていないだろ。
悩むのは、再帰をいかに展開するか、だろ。
0157デフォルトの名無しさんNGNG
>>156
お前みたいの限ってホントは理解してなかったりするんだ。
学習者だろ？
ナップザック問題に泣いてるんだろ（ｗ
0158デフォルトの名無しさんNGNG
リカーシブル・グラフィックはよく分からん・・・・
0159仕様書無しさんNGNG
Tail recursionは、loopにoptimizeされるcompilerが結構あるよ。
例えば、gcc。
0160デフォルトの名無しさんNGNG
>>159
だから、なに？
0161159ではないが…NGNG
>>160
だから遠慮せずに再帰をどんどん使えって事では。
直感的になって効率も落ちないなら、つかわん理由がない。
0162デフォルトの名無しさんNGNG
C99では末尾再帰展開＋内部定義デフォにして欲しかったyo...
0163デフォルトの名無しさんNGNG
数学では割と普通の概念なのに、
プログラミングではスタックが出てくるから分かりにくいのだろうか？
0164デフォルトの名無しさんNGNG
>>163
それは違うだろ…
C だろうとスタックは透過的なわけだし…

そもそもわかりにくいのか?
0165デフォルトの名無しさんNGNG
馬鹿がわからんだけだよ。(で、「非効率」だと騒ぐ)
「普通の概念」っつっても「数列」挫折したような奴には難しいだろ。
0166デフォルトの名無しさんNGNG
たしかVBだと再帰ができなかったような、、、
再帰が嫌いなやつってVBプログラマか？
0167名梨産NGNG
>>163
スタックって、CPUのSPの事指してる？
スタックの動作をしたいだけならSPにあたる添字をキチンと制御してやれば
ただの配列変数でできるでしょ？特に解りにくいとは思わないけど。

>>166
VBでもできますよん。前に数式解析のルーチン作ったとき使った。
0168デフォルトの名無しさんNGNG
ルート検索とか再帰使って関数を単純化できた。
便利なもん使ってなんか不都合あるんだろうか？
0169デフォルトの名無しさんNGNG
再帰。

どうして俺は再帰がきらいなんだろう。
悩んだ。
数日間それでなやんだ。
そしてとうとう結論を得た。
再帰するからだ。
0170デフォルトの名無しさんNGNG
>>168
ネストし過ぎるとタックオーバーフローで止まる（最悪、暴走する）プログラムになる。
クイックソートの様な指数オーダーの再帰ではそんなにネストする事は無い。
0171デフォルトの名無しさんNGNG
void bin2oct(unsigned n)
{
if (n != 0)
bin2oct(n / 8);
putchar(n % 8 + '0');
}
0172デフォルトの名無しさんNGNG
>>170
どこまでネタなんだか （藁

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

>>170
対数
0174≠１６９NGNG
再帰。

論点をまとめずに思考を進めてしまい、
再帰から抜けられないでいる。
0175173NGNG
>>174
面白くない
0176デフォルトの名無しさんNGNG
Lisp で たらい回し関数やアッカーマン関数を実行させて
処理系の実行速度を測ったりしたな
0177デフォルトの名無しさんNGNG
「自分自身を起動せよ」


この1行を書いたプログラムを実行するだけで、
あなたも再帰を体感できます。
0178デフォルトの名無しさんNGNG
>>177
ブラクラに実装されてることが多いな。
0179デフォルトの名無しさんNGNG
>>177
ロボット（腕だけのキット）をコントロールして自分自身のスイッチを切らせた人を知ってる…
0180デフォルトの名無しさんNGNG
いや再帰スレなんだから　ロボットにロボットを作らせなくちゃダメだろ
0181デフォルトの名無しさんNGNG
終了条件のない再帰ってありなの？

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

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


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;
}
0182デフォルトの名無しさんNGNG
>>181
>>終了条件のない再帰ってありなの？
スタック食いつぶす分無限ループよりタチが悪いな。
いや、スタックオーバーフローでOSがトラップしてくれる分
かえって発見し易いか？

>>カレントディレクトリ以下の構造を再帰的に出力する、
って事ならその「処理中のディレクトリにサブディレクトリがない」
ってのが終了条件になってるし。
0183デフォルトの名無しさんNGNG
再帰の、最も簡単な分類にはいる関数だと思われる。

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);}
0184デフォルトの名無しさんNGNG
その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);}
0185デフォルトの名無しさんNGNG
再帰の定番　アッカーマン

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));
}
0186あげNGNG
日本人の心 たらいまわし

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言語による最新アルゴリズム事典
0187デフォルトの名無しさんNGNG
unsigned get_int_value(unsigned value)
{
if(value==0)
return 0;
else
return get_int_value(value-1) + 1;
}
0188デフォルトの名無しさんNGNG
>>183
それは使いどころ間違ってるよ。

double power(double base, double ex)
{
return exp(ex * log(base));
}
だろ。
0189デフォルトの名無しさんNGNG
>>186は何に使うのですか？
0190デフォルトの名無しさんNGNG
>>189
ベンチマーク
0191デフォルトの名無しさんNGNG
>>188
183じゃないが、expとlogを使うより精度が高い。
0192デフォルトの名無しさんNGNG
>>191
でも遅い。整数乗しか扱えない。
0193デフォルトの名無しさんNGNG
>>192
ﾔﾊﾟｰﾘ、テイラー展開を使うべきか？
0194デフォルトの名無しさんNGNG
しかし、プログラムを書くにはそんなに
数学を勉強しないといけないの？
線形代数とかまで要求されるジャン・・・
0195デフォルトの名無しさんNGNG
>>193
expは（ハードがやってくれなきゃ）当然多項式で近似するんだよ。
テイラーじゃなくてチェビシェフが普通だろうけど。

>>194
expを書こうなんて思えばね。
0196デフォルトの名無しさんNGNG
線形代数って、一次関数のことじゃないの？
0197デフォルトの名無しさんNGNG
線形代数って普通はベクトルとか行列の話だよね。
0198デフォルトの名無しさんNGNG
ふつーもクソもあるか。
0199デフォルトの名無しさんNGNG
われわれ工学部の強力な武器です。
0200デフォルトの名無しさんNGNG
>>194
画像・音声など信号処理にはもちろん必要。
プログラミング一般においても数学的なセンスは必要だね。
演繹的・帰納的にアルゴリズムを組み立て解を出す様は
数学もプログラムもよく似ている。
0201デフォルトの名無しさんNGNG
良スレage
0202デフォルトの名無しさんNGNG
age
0203デフォルトの名無しさんNGNG
涼スレ？
0204デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/992241842/1
0205デフォルトの名無しさんNGNG
情報工学生には一読の価値あり age
0206デフォルトの名無しさんNGNG
age
0207デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/992241842/l1
0208デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/992241842/
0209デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/1019489340/l1
0210デフォルトの名無しさんNGNG
マトリョーシカ
0211デフォルトの名無しさんNGNG
蛇足だけど、staticな関数の自己末尾再帰はgcc(2.95.4で試した)で
最適化させた場合、goto相当に展開する。
0212デフォルトの名無しさんNGNG
どうやったらわかるの？
アセンブラがわからないとだめ？
■ このスレッドは過去ログ倉庫に格納されています