再帰

http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842

再帰の意味も理解できないｳﾞｧｶ発見！

>>2
お前は再帰の意味がわかってるのか？
そうなら、是非解説してください。

ちなみに結構広い意味で使われてるのよ。
http://dictionary.goo.ne.jp/cgi-bin/dict_search.cgi?MT=%BA%C6%B5%A2&sw=2

このスレどうやって立てたの??

…と思ったら、hidden の中に時刻入ってるじゃん。なーんだ。

>>2
自己参照も再帰の一種かと。

>>4-5
でもタイミングが難しいのよ。

>>2は基底がないと再帰じゃないと思っているとか。

このスレは糞スレリサイクル法にもとづき、ただいまより
「再帰について語るスレ」と致します。

>>4
どういうこと？未だにどうやって立てたのかわからん

>>1の投稿時間を考えると、なかなか評価できるな

って全然関係ねぇや＜タイミング
むっちゃ簡単じゃんよ

>>7の補足
>>5
hiddenの値がスレ番になるわけじゃないかと。
CGIがリクエストを受け付けた時刻っぽい。

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

俺には、適当にスクリプトでも組んで、
適当なリクエストでサーバータイムとの差をms単位で算出してから、
余裕があるタイミングでポストする(ping値も参考にする？)
これ位しか、やりかたを思いつかない。

１みたいな人が、ハッカーになるんでしょうね。

>>13
ああそうなのか。疑ってスマソ

再帰とゆーか、ループっちゃってGCできなくなっちゃった
リストとゆーか...

>>16
虐めないでくれ…

これも１だろ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241448
sageで立てたから気付かれなかったけど。

これでテストしたんだな。8秒ずれ。
http://mentai.2ch.net/test/read.cgi?bbs=prog&key=992241080

すごい

クソスレリサイクル法に従い再帰の話題をば

再帰を人に教えるのは難しい。
ハノイの塔とかグラフィックを使うのとかは相手のレベルが低いと辛いし。

>>23
８クイーンじゃだめ？陳腐すぎますか？

アッカーマソ関数は?

>>23
まずクイックソートでおしえれよ

>>24
いきなりバックトラックだとちょっといやかな、とは思ったんですが。
ディレクトリを奥まで探っていく感じのサンプルがいいんだけど、
伝えたい感覚わかるかな？

>>25
ネタだよね（藁

>>26
理解してもらえませんでした（涙）

再帰的定義: GNU = "GNU is Not Unix!"
再帰的動作: function qsort(0,n) = qsort(0,n/2); qsort(n/2+1, n);

CFGで教えるというのはどうか。

無難に階乗とフィボナッチ

ターミネーター２で最後、敵のロボが溶鉱炉に落ちて口から顔が出て
そのまた口から顔が出て来るのを見て再帰を理解しましたｗ

&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スクリプト

Ｃで教えるにはANSIにこだわると難しいらしいな。
グラフィックで雪印やドラゴンカーブを書かせれば
すぐに理解できるとは思うけれど

ファイル検索のアルゴリズムは再帰？

検索関数でサブディレクトリ（フォルダ）が見つかったら
そのフォルダ相手に検索関数を実行する再帰手法が一般的
というか他のやり方はすぐに思いつかないのだが。
そういえばANSIにファイル検索関数ってなかったっけ。

>>33
Cで再帰を教える代表的なものは、クイックソートだな。

>>35
それは深さ(縦)優先の再帰。逆の再帰もあるだろ。
深さ優先は使用メモリは最小限にできるが、
その深さに比例してハンドルをオープンしっぱなしにしなければならない。

>>36
逆の再帰って何ですか？

lispヤレヤ

逆というか一般的に探索戦略は、深さ優先と幅優先の二種類がある。

幅優先ってどんなの？具体例だけでもいいから希望

幅を優先いたしまーす。

>>23
K&R(第一版)にのってる数字を表示するやつは結構簡単でいいと思う。

23じゃないけど>>42
K&R、持ってない。どんなの？

aaa
　bbb
　　ccc
　ddd

という階層構造があった場合、
aaa->bbb->ccc->dddと上から(?)順番に探してくのが深さ優先
aaa->bbb->ddd->cccと浅い順から探してくのが幅優先。
無限に(あるいは十分に)深い階層を探索する場合はこっちが有効な場合が多い。
ただメモリを馬鹿食いする。

>>44
tnx.

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

再帰使わない例も載ってて、それと比べると再帰の良さがわかりやすい。

オセロや将棋などのゲームで考えると分かりやすいと思う。
次の手、その結果に対して次の手とどんどん先読みしていくのが深さ優先。
次の手には何があるのかを全て調べてから、その次の手を調べるのが幅優先。

なるほど、さすがK&R。わかりやすい。
情報ありがとう>>46

階乗とか最大公約数とか。

>>49
再帰の例として良く見かけますけど、
階乗は、あまりメリットが見えないので、
n個以上(n>1)の数の最大公約数が良いかと…。

全数探索を行うときに再帰を使った。
当然、全数探索にはO(2^n)かかるのを承知でだが。
指数オーダーはいかんよ。今さらだけど。

宣教師と人食い土人

バックトラック問題はみんな再帰

スゲェ。
ちと感動したよ。>>1
一発ネタだが、名スレだ。

再帰呼び出しを使わずに再帰を実装する方法も考えてみよう

って優香、クイックソートの実装に再帰を使うのはヤメレ

>>55
再帰を使うのはサンプルだけだろ

ワイルドカードプログラムはどうだろうか？

>>56
再帰をスタックに直すプログラム書いてくれ。

再帰のコードを１とすると、
再帰使わない方法（スタック）は２以上の工数がかかる。

Q.

>>1を再帰を使わずに表現しなさい。

>>55
　えっ！？なんで！？厨房なんでわからない。
教えて

Win2000で試したら、窓380個(推定)まで開けたよ>>1

>>61
ｻｲｷﾊｼｮﾘｶﾞｱﾏﾘﾊﾔｸﾅｲ

>>61
1. 速度が遅い

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

　 ヒープならメモリ確保する時に正否が分かるが、スタックだと失敗した
　 瞬間にシグナル (しかも環境によっては SIGKILL) 飛んできたりするし。

58 名前：デフォルトの名無しさん 投稿日：2001/06/20(水) 23:56
>>56
再帰をスタックに直すプログラム書いてくれ。

これ作れば再帰で書いても良いんじゃない？

>>64
POSIXならsigaltstack()が使えるが、
スタックが溢れたのかそうでないかを判別する手段がないんだよな。
なんかいい手知らない?

　ふーむ。そうだったのか。
一つ賢くなったよ。アリガトホ

>再帰をスタックに直すプログラム書いてくれ。
同じく

再帰をやめれば自分で管理できるかと。

59 名前：デフォルトの名無しさん 投稿日：2001/06/20(水) 23:59
再帰のコードを１とすると、
再帰使わない方法（スタック）は２以上の工数がかかる。

>>58
なぜ俺に言う。
しかも、ループに展開できるのは末尾再帰だけだ

>>64 qsortならスタックのサイズは高々 log n じゃない?
それから、再帰呼びだしのオーバーヘッドて
自分でスタック実装したときよりもそんなにデカいものなんですか?
アセンブラレベルで比べたことがないからわからない。

>>70
状況によって違う。
一般論では語れない。

>>74
おまえもなー。

>>74
ナイス！ワラタ

>>72
違うよ。
クイックソートは平均がO(logN)なだけで、最悪の場合はO(N)になる。

>>72　>>76
クイックソートはO(n log n)。
最悪はO(n^2)。（避けれるように出来るけど）

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

結構でっかいような気はするなぁ。

スタック
if (sp == stack_num) stack = realloc(stack, stack_num *= 2);
stack[sp++] = val;

再帰
f(val);

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

再帰は毎回
・関数呼出し（オーバーフローは判定不能）
が必要。

>>78
> ・インデクス参照代入
> ・spの増加

popは…。

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

これがでかいよね。
レジスタ退避させたり。

あ、ごめん。
O(log n)ってスタックのサイズの話ね……。

再帰→スタック変換を人間が行なうと、
プログラム意味論的(よく知らんけど)に、
「再帰構造である」という主張が薄れるって害は無い？
（forやwhileをgotoに直す様な事と同等）
C->ASMの様に、
機械的（暗黙的に）にやらせるのが理想だと思うんだけど。

>>77
計算量ではなくてスタックの深さの話だと思うが

>>76
末尾再帰を上手く使えば O(log N)で抑えられる。
小さいブロックを先に片づけるのだ

>>81
まあね。
でも意味重視で性能悪いのは・・・ね。

まあ、理解不能になるわけじゃないしいいんじゃない？

>>82
小さいブロックを先に…って話じゃ無理かと。

二つに分ける時に、片寄らないようにしないとイカン。

age

ニホンジンハウソツキ

＞再帰の例として良く見かけますけど、
＞階乗は、あまりメリットが見えないので、
＞n個以上(n>1)の数の最大公約数が良いかと…。

nが２個ならユーグリッドの互除法だよね。
３つ以上ならどのように再帰で表現する？
出来なくないですか？

GCD(n1, n2, ..., nm) <= GCD(n1, GCD(n2, ..., nm)).
じゃないの？

ネタスレがこんな良スレに育って・・・父さん嬉しいぞ

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

実際問題、
「（末尾再帰ではない）再帰→スタック＋ループ」
変換は機械的に可能でしょうか？

>>91
可能でしょ。
アセンブラレベルでは「スタック＋ループ」みたいなもんじゃん。
あれがcallとretでなくjmp+αだったらいいだけでしょ？
# これは可能っていう根拠について書いてるので
# 上記の方法でやれってのとは違うです。

age

>>92
アセンブラにした所で、再帰構造のコードはずっと再帰ですが。

じゃあ、「再帰」と「スタック+ループ」の違いは?
PCをスタックに積むかどうか?

>>96
オマエモナー（気に入ったらしい）

>>97
パクルなＹＯ！（ちょっとしつこいな・・・）

　順列の生成を再帰を使わずにやってみた事が有るけど、パフォーマンスは
確かに上がるね。ソースは汚くなるけど。

いまさらだけど、schemeというlisp系言語やMLなどの関数型言語は
言語規約として末尾再帰(単体/相互)をgoto相当に展開する。
普通の再帰は知らないけど。
表現能力は、
再帰＞スタック＋ループ

100!

101!

>>103

>>102

そういえばあの時順列のアルゴリズムを追求してすごいの作ったつもりに
なってたけど、ある本を読んだら最少順序変換法って名前が付いてた。
車輪を再発明してたのが判ってしばらく鬱だったよ。

>>102,103
入り口が複数なのね。

>>104
そうやって、人は一歩ずつ成長して行く

アルゴリズム言語Schemeに関する第五改訂報告書
http://www.sci.toyama-u.ac.jp/~iwao/Scheme/r5rsj/html/r5rsj.html#SEC2
>繰り返しを表現する場合に手続き呼び出しのみを使用することによって、
>終端再帰的手続き呼び出しが本質的に引数を渡すgotoであることが、Schemeでは強調されている。

>>99 単純にそうは言えないだろ。
暗黙の制御スタック一つしかない再帰に比べれば、明示的な
スタックは複数もつことができて、より細かい制御はできるし。
まあ、安直なものは再帰のほうが楽にかけて、
世の中安直で十分な場合も多いというのは真だけど。

なんだぁ、リカーシブって
再び呪いをかけられることかと思ってたよ

>>108
Bit悪魔の辞典ですか（笑）

そりゃ、リ・カース(re-curse)

難しいボケとツッコミだなぁ

うんち

>>112
1がコレだもんなぁ

>>113
ナイーブな対応。再帰にしてみよう

>>113
>>112は騙りです。

再帰することはオブジェクト指向的に見てどう？

人をバカって言うヤツがバカ。

人をバカって言うやつがバカって言うやつが…

Stack overflow

>>118
ほぉら、再帰に入る前に脱出の手段考えてないからこんなことに…

>>118-119
ワラタ。おもろい

なるほどそういうことか！
目から鱗だね！

良スレ

良スレ
>>16 >>19 他称ハッカーは尊称、ということにしとこうや。

末尾再帰ぐらい展開しろやボケェ！
って状況になるといいね。

>>121 は、どのカキコをみて >>116 の解を見つけたのか謎である。

ほんと、謎だね。

ｼﾞｻｸｼﾞｴﾝﾃﾞｼﾀ (o^ー')b

http://piza.2ch.net/test/read.cgi?bbs=tech&key=992241842

>>128
残念。

sage

age

>>131
そんな・・・
意味もなくageなくても・・・

上がってたので読んでみた。
再帰使うと深さ優先の探索になるんだよね? 広さ優先と再帰って組めない？

>>133
オブジェクトのメソッドを呼び出すような再帰(？)なら可能だろ。
処理のメソッドと子供を辿るメソッドを分けて、前者をすべての
子供に対して読んでから後者を呼べばいい。

makeの再帰呼び出しにはちょっと感動した

>>135
何のMakefileか教えてくれー。見てみたいー。

prologって言語ではループ＝再帰だよ！

wshでサブディレクトリのファイルを移動するコードを書きたいんだけれど、
どうやって「深さ優先」と「幅優先」を書き分けたらいいでしょうか？

良いアドバイスがあったらよろしくお願いします。

>>135
サブディレクトリに移動してmakeってやつ? ごく普通だろ。

>>136
linuxカーネルとかemacsのソースでも見てみ。
まぁライブラリを作ったりする場合は常識だな。

shr

>>139
たまに間違ってfork爆弾になってるMakefileもあるな。

>>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をコピー
}

>>142
さんきゅーです。さっそくやってきます￥

っていうか、俺は職業プログラマだが、
プロになってから一度も再帰なんて使ったこと無いぞ。
せいぜい、加減乗除とルートまで。

面倒な処理はライブラリがやってくれるから、再帰なんて勉強しないで
ＵＭＬとかやったほうが役に立つぞ。
再帰なんて研究者か学生専門だね。

再帰は基礎教養として必須に一票。

>>145
まぁ、学生のうちはアルゴリズムの勉強で大いにやるべき。
むしろ、やらなきゃダメ。アイディアの元になるからね。

だけど、現場では全然使わないよ。

済まん、名前間違えた。
>>146の名前欄は「144」ね。

>>144-145

もう煽り誘導レスは飽きた。

別に煽ってないよぉ・・・
意見を言っただけなのに・・・

>>149
確かに、スタック積んで降ろして積んで降ろして･･･という動作を想像して鬱になってしまうので、
再帰を採用する前に他のアルゴリズムが無いか検討はしてみることが多いな。
でも再帰は書いてて気持ちいいね。

すまん、仕事でバリバリに使ってる。
個人的に好きなんで。

>>144
あんまり複雑なデータ構造は使わないんだな。
いや悪いといってるんじゃないので。
できる限り単純なほうがいいのは当り前だから。

> 面倒な処理はライブラリがやってくれるから、再帰なんて勉強しないで
でも再帰ひとつ満足に使えないのは論外。

>>151
使うなよ。
見た目が直感的に成る以外のメリットは無いだろ

コードが短くなるメリットがあるよ。

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

　問題ってのはスタックサイズや処理コストの事ね

俺は、あまり苦労しないで再帰は理解できたよ。
ファイル検索なんか、再帰便利だし。

再帰の理解に苦労するやつなんていないだろ。
悩むのは、再帰をいかに展開するか、だろ。

>>156
お前みたいの限ってホントは理解してなかったりするんだ。
学習者だろ？
ナップザック問題に泣いてるんだろ（ｗ

リカーシブル・グラフィックはよく分からん・・・・

Tail recursionは、loopにoptimizeされるcompilerが結構あるよ。
例えば、gcc。

>>159
だから、なに？

>>160
だから遠慮せずに再帰をどんどん使えって事では。
直感的になって効率も落ちないなら、つかわん理由がない。

C99では末尾再帰展開＋内部定義デフォにして欲しかったyo...

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

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

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

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

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

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

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

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

再帰。

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

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

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

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

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

>>169
面白い

>>170
対数

再帰。

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

>>174
面白くない

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

「自分自身を起動せよ」


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

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

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

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

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

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

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


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がトラップしてくれる分
かえって発見し易いか？

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

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

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言語による最新アルゴリズム事典

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

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

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

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

>>189
ベンチマーク

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

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

>>192
ﾔﾊﾟｰﾘ、テイラー展開を使うべきか？

しかし、プログラムを書くにはそんなに
数学を勉強しないといけないの？
線形代数とかまで要求されるジャン・・・

>>193
expは（ハードがやってくれなきゃ）当然多項式で近似するんだよ。
テイラーじゃなくてチェビシェフが普通だろうけど。

>>194
expを書こうなんて思えばね。

線形代数って、一次関数のことじゃないの？

線形代数って普通はベクトルとか行列の話だよね。

ふつーもクソもあるか。

われわれ工学部の強力な武器です。

>>194
画像・音声など信号処理にはもちろん必要。
プログラミング一般においても数学的なセンスは必要だね。
演繹的・帰納的にアルゴリズムを組み立て解を出す様は
数学もプログラムもよく似ている。

良スレage

age

涼スレ？

http://pc.2ch.net/test/read.cgi/tech/992241842/1

情報工学生には一読の価値あり age

age

http://pc.2ch.net/test/read.cgi/tech/992241842/l1

http://pc.2ch.net/test/read.cgi/tech/992241842/

http://pc.2ch.net/test/read.cgi/tech/1019489340/l1

マトリョーシカ

蛇足だけど、staticな関数の自己末尾再帰はgcc(2.95.4で試した)で
最適化させた場合、goto相当に展開する。

どうやったらわかるの？
アセンブラがわからないとだめ？