再帰をみっちり仕込んで下さい！
■ このスレッドは過去ログ倉庫に格納されています
00011@VB房
NGNG何度もいろいろ質問しては教えてもらい、それ自体はできるんですが
再帰がどういう構造になってるのか、っていう大本の所を理解していないので
他になかなか応用できないでいます・・・。
こんな私にみっちり仕込んでください！
・参考になるページ
・読むといい本とか
・作ってみるといいサンプル
・論理的に再帰がどういう物か説く
等どんなことでもいいのでお願いします！
（一応VBで他のちょっとした事ならできる、ぐらいのレベルです）
0002デフォルトの名無しさん
NGNG0003デフォルトの名無しさん
NGNG0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNGてゆーかその前に
「再帰」の定義を教えて？ >>1ｻﾝなりにでいいからさ・・・
0006デフォルトの名無しさん
NGNG0007デフォルトの名無しさん
NGNG0008デフォルトの名無しさん
NGNG0009デフォルトの名無しさん
NGNG0010デフォルトの名無しさん
NGNG00121@VB房
NGNG関数の中から自分自身（関数）を呼び出し、
それの処理が帰ってくること、と思ってるんですが。
全然見当違いだったらｽｲﾏｾﾝ。
0013デフォルトの名無しさん
NGNG0014デフォルトの名無しさん
NGNG・単発ネタでスレ立てないで下さい
・削除依頼出しておいて下さい
・再帰をするときってのは大体パターンが決まってる
・そもそもBASICで再帰というのが間違い
0015デフォルトの名無しさん
NGNG正解！！
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝終了＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
0016デフォルトの名無しさん
NGNG0017関係なくても知らん
NGNGよくわかってないヤツは計算機にやらせてはいかん。
例題はフィボナッチ数列だ。足し算くらいできるだろ。
フィボナッチ数列の定義はここでは以下のようにする。
f(x)={
1 where x=0 or 1,
f(x-1)+f(x-2) where x>=2
}
OK。そしたらf(10)でも求めてみろ。
ただしf(0)から順にやってはだめだ。
必ず定義にしたがってf()を展開しながらやれ。
なに、もうf(0)からやっちまった!?
しょうのないヤツだ。
そいつは答えあわせに使え。
ついでにかかった時間と労力を比較しとけ。
0019あぼーん
NGNG--->
long factorial( long x ) {
if( x>1 ) {
return ( x * factorial ( x-1 ) );
} else {
return ( x );
}
}
<---
n>1のとき
n! = n * (n-1)!
n=1のとき
n! = n ( = 1 )
が基本的な考え方になっています
もっとも
--->
long factorial( long x ) {
long i;
long ret=1;
for( i=1; i<=x; i++ ) {
ret *= i;
}
return ret;
}
<---
でもいいような気がするが。
0020通りすがりのもの
NGNG自分自身を呼びつづけて、結局帰ってこなくても再帰は再帰よね？
（戻り値といっしょに処理を返すのが普通だろうけど）
0021デフォルトの名無しさん
NGNG0022デフォルトの名無しさん
NGNG終了条件が無く、無限ループであってもループと言うが如し。
（ＣＰＵ時間だけでなくスタック食い尽くす分無限ループより質がわるいがな。）
0023デフォルトの名無しさん
NGNGそれは暴走でわ
0024優しすぎて損ばかりしている名無しさん
NGNG0025デフォルトの名無しさん
NGNGうん。
>>20
うん。
0026デフォルトの名無しさん
NGNG0027デフォルトの名無しさん
NGNGfunction func(a:Integer):Integer;
var i:integer;
begin
Result:=0; if a<1 then exit;
Result:=1; if a<2 then exit;
for i:=1 to a-1 do Result:=Result+func(a-i)+func(i);
end;
func(23) を求めよ
0028デフォルトの名無しさん
NGNG0029デフォルトの名無しさん
NGNG(define (hanoi n from to spare)
(if (= n 1) (list (list 'move-disk from 'to to))
(append
(hanoi (- n 1) from spare to)
(hanoi 1 from to spare)
(hanoi (- n 1) spare to from))))
003027
NGNGこれ実行させないで答え判るとエライ人かもしれない
0031デフォルトの名無しさん
NGNG0032デフォルトの名無しさん
NGNG0033デフォルトの名無しさん
NGNGそれ VB?
答えは多分 20920706406
0034デフォルトの名無しさん
NGNG0035デフォルトの名無しさん
NGNG再帰呼び出しの基本的な考え方は次のようになります。
ふすまを開ける
↓
ふすまを開ける
↓
ふすまを開ける
↓
ふすまを開ける
↓
殿発見！！
↓
ふすまを閉める
↓
ふすまを閉める
↓
ふすまを閉める
↓
ふすまを閉める
って感じ？
で、このふすまを開ける作業をモジュール化して、どのふすまを開ける作業でも
応用できれば便利だよね。
上の例では書いてないけど、ふすまを開ける作業ごとに、実は殿はいないかチェックしてるわけ。
だから、毎回同じことをやってると。
で、シリアルに呼び出すのはバカすぎるけど、ループ作って呼び出してもいいよね。
でも殿がいない場合は、もう一回モジュール自身を呼んでもいいわけよ。
このあたりはコールスタックの概念があったほうがいいね。
あまり無頓着なことしてるとスタックオーバーフローを起こすとか。
一回呼ぶごとに何らかの計算もできます。
qsortなんかを見てください。
わかったかなー。
003633
NGNGa_n = 2*(a_1 + a_2 + ... + a_(n-2) + a_(n-1))
ここで 2*(a_1 + a_2 + ... + a_(n-2)) = a_(n-1) なので
a_n = a_(n-1) + 2 * a_(n-1) = 3 * a_(n-1)
で a_2 = 2 なので a_n = 2*3^(n-2)
a_23 = 2 * 3^(23-2) = 20920706406
a_n は上のプログラムでは func(n) ね。
0037デフォルトの名無しさん
NGNG0038デフォルトの名無しさん
NGNG0039デフォルトの名無しさん
NGNG0040デフォルトの名無しさん
NGNGfunc(2)の時は 1+func(1)+func(1)=3となります
0041デフォルトの名無しさん
NGNGっていうのは quick sort 以外だと何がある？
0042デフォルトの名無しさん
NGNG再帰でやると順番を逆転するとかが容易 例：2進で印刷するとか
0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNG催奇だ！！
0045デフォルトの名無しさん
NGNGどうしても「再帰」っていう概念が理解できないんです！
何度もいろいろ質問しては教えてもらい、それ自体はできるんですが
再帰がどういう構造になってるのか、っていう大本の所を理解していないので
他になかなか応用できないでいます・・・。
こんな私にみっちり仕込んでください！
・参考になるページ
・読むといい本とか
・作ってみるといいサンプル
・論理的に再帰がどういう物か説く
等どんなことでもいいのでお願いします！
（一応VBで他のちょっとした事ならできる、ぐらいのレベルです）
2 名前：デフォルトの名無しさん 投稿日：02/04/23 00:30
>>2
3 名前：デフォルトの名無しさん 投稿日：02/04/23 00:31
>>3
4 名前：デフォルトの名無しさん 投稿日：02/04/23 00:31
>>4
5 名前：デフォルトの名無しさん 投稿日：02/04/23 00:32
>>1
0046デフォルトの名無しさん
NGNG>>37-38
情報がたくさんあるschemeの方が良いと思う。
0047再帰的スレ
NGNGhttp://pc.2ch.net/test/read.cgi/tech/1019489340/
0048デフォルトの名無しさん
NGNG最初の頃のレスはそういう意味だったのか。ﾜﾗﾀ
0049デフォルトの名無しさん
NGNGhttp://pc.2ch.net/test/read.cgi/tech/992241842/207-208
ついでにオマケ
向こうから、こっちを呼び出して相互再帰だー。
http://pc.2ch.net/test/read.cgi/tech/992241842/209
0050デフォルトの名無しさん
NGNGそれは君自身に問え。
それが再帰だ。
005136
NGNGResult:=0; if a<1 then exit;
Result:=1; if a<2 then exit;
を
if (a<1) return 0;
if (a<2) return 1;
だと思ってしまつた…。
Result は初期化されてないけど 0 なのかなと…。
やっぱ知らない言語はアレだ…。
0052デフォルトの名無しさん
NGNGa(n)
{
int i, r;
if (n<1) return 0;
if (n<2) return 1;
for (r=1, i=1; i<n; i++) {
r += a(i) + a(n-i);
}
return r;
}
と解釈. (a, n を func, a と読み換えて下さい.) あとは
>>36 と同じ方法で
a_0 = 0
a_1 = 1
漸化式
a_n = 1 + 2(a_1 + a_2 + ... + a_{n-2} + a_{n-1})
= 1 + 2(a_1 + a_2 + ... + a_{n-2}) + 2*a_{n-1}
= a_{n-1} + 2*a_{n-1}
= 3*a_{n-1}
一般項
a_n = 0 (n=0)
3^{n-1} (n>0)
よって
a_23 = 3^22 = 31381059609
最後の計算は計算機を使わないと間違えるかも.
ところで, 27 の使っている言語では Integer は
31381059609 という値を保持できると仮定して良いの?
それとも...
0053デフォルトの名無しさん
NGNG{
if(a が一定条件を満たす) {
return a;
} else {
return func(a);
}
}
これだけの話。
0054デフォルトの名無しさん
NGNGなんでいまさらこのスレヲアゲルノカナ・・？
>>27の結論出すのに２ヶ月かかったってコトカナ？
ドウデモイイケドナ。
0055デフォルトの名無しさん
NGNGGC してたんだよ、きっと。
0056デフォルトの名無しさん
NGNG帰りは無いのですか？
0057デフォルトの名無しさん
NGNG再起なんて、lispでしか使わないから、覚える必要無し。
0058デフォルトの名無しさん
NGNG0059Delフサギコ ◆zE1iiRdQ
NGNGA | 再帰はサブディレクトリ探索に
K |彡 使えるのに…
A ⊂ﾐ
R |ﾐ
A |J 階層構造を扱うには便利ですよ
簡単な所でいえば
階乗計算なんか、どうでしょ。
5! = 5*4*3*2*1
を計算するのに再帰関数は便利
//nの階乗 n! を求める関数
function Kaijyo(n: Integer): Integer;
begin
if n = 1 then
begin
Result := 1;
end else
begin
Result := Kaijyo(n-1) * n;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
begin
for i := 3 to 10 do
begin
Memo1.Lines.Add(
IntToStr(i)+'の階乗 '+
IntToStr(i)+'! = '+ IntToStr(Kaijyo(i))+' です');
end;
end;
出力結果
3の階乗 3! = 6 です
4の階乗 4! = 24 です
5の階乗 5! = 120 です
6の階乗 6! = 720 です
7の階乗 7! = 5040 です
8の階乗 8! = 40320 です
9の階乗 9! = 362880 です
10の階乗 10! = 3628800 です
0060デフォルトの名無しさん
NGNGそして、27の言語はpascal。
Integerが32bitだと収まらないです
0061デフォルトの名無しさん
NGNGInt64
0062いぢわるな質問
NGNGｾﾝｾｲ! なぜループじゃなくて再帰を使って階乗を求めるのですか？
ｽﾀｯｸの無駄遣いだと思います。
0063デフォルトの名無しさん
NGNGでは再帰を使って a^n を 書いてみて下さい
0064デフォルトの名無しさん
NGNG再帰的に定義されていることが多い。
つーことで、>>1さんはプログラミングというより
むしろフォーマルな定義というものに慣れていないのでは、
と思う。sage
0065Delフサギコ ◆zE1iiRdQ
NGNG∧⊂ヽ, ／
ﾐﾟДﾟ,ﾐ,ﾉ＜ ハニャーン
ﾐ⊃ ,ﾐ ＼＿＿＿＿＿＿＿＿＿＿＿＿
ﾐ, ,,ﾐ
⊂,,,ノ
∪
階乗計算をするのに再帰が便利なんじゃなくて
再帰を勉強するのに階乗計算がｲｲ。
って事でした。
0066デフォルトの名無しさん
NGNG0067デフォルトの名無しさん
NGNG0068デフォルトの名無しさん
NGNG0069デフォルトの名無しさん
NGNG0070デフォルトの名無しさん
NGNGＰＬ／ＳＱＬで使った漏れはＯＫですか？
0071デフォルトの名無しさん
NGNGResultは予約語？
0072デフォルトの名無しさん
NGNGyes.
関数は、result に代入した結果が戻り値になる。
007371
NGNG0074デフォルトの名無しさん
NGNGwhile(HTMLソース.最後じゃない()){
タグ=HTMLソース.次の行読む();
if(タグ.リンクです()){
リンクをクリック(タグ.HTMLソース化());
}
}
}
0075デフォルトの名無しさん
NGNGメイン(){
リンクをクリック("http://www.2ch.net/");
}
リンクをクリック(アドレス){
HTMLソース=アドレス.HTMLソース化();
while(HTMLソース.最後じゃない()){
タグ=HTMLソース.次の行読む();
if(タグ.リンクです()){
リンクをクリック(タグ.アドレス取り出し());
}
}
}
0076デフォルトの名無しさん
NGNGいまどきの言語は普通に再帰使うじゃん。
Javaで再帰なんて当たり前だしのぉ。Parent追っかけるのにさ。
クラスライブラリでも(以下略)
0077お約束
NGNGこれはもちろん
*いまどきの処理系は末尾再帰のgoto書き換えくらいは普通に行うじゃん*
て意味だよね？
0078デフォルトの名無しさん
NGNGFIFA Is the Football Association.
なんだって。
0079デフォルトの名無しさん
NGNG今の会社でこの言葉使ったら誰も知らなかった・・・
MSBとLSBこれも通じなかった・・・(-_-)ｳﾂﾀﾞ
0080デフォルトの名無しさん
NGNG0081デフォルトの名無しさん
NGNGﾜﾗﾀ
0082デフォルトの名無しさん
NGNG0083デフォルトの名無しさん
NGNGあと再配置も
0084デフォルトの名無しさん
NGNGリエントラント
リロケート
0085デフォルトの名無しさん
NGNGリカージョン
0086デフォルトの名無しさん
NGNG0087デフォルトの名無しさん
NGNG0088デフォルトの名無しさん
NGNG0089デフォルトの名無しさん
NGNG再帰と、再入は ASCII 用語辞典 http://yougo.ascii24.com/gh/ に
あった。再配置は、おぼろげな記憶。
再帰: recursive call
サブルーチンの中から、さらに自分自身を呼び出すような処理。この再
帰呼び出しを利用することで、複雑な処理を非常に単純なコードとして実
現できる場合がある。ただし再帰呼び出しを行なうプログラムの実行時に
は、消費されるスタック用メモリに注意する必要がある。
再入: reentrant
「再入可能」という意味。マルチタスク環境では、あるプログラムコー
ドの実行中に、さらにそのプログラムコードの実行が要求されることが
ある。このような場合でも、そのプログラムコードがリエントラントに設
計されていれば、１つのプログラムコードで複数の処理を非同期に実行で
きる。
再配置: relocate
コードやデータ等の位置を配置し直すこと。
0090デフォルトの名無しさん
NGNG0091デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています