どうしても「再帰」っていう概念が理解できないんです!
何度もいろいろ質問しては教えてもらい、それ自体はできるんですが
再帰がどういう構造になってるのか、っていう大本の所を理解していないので
他になかなか応用できないでいます・・・。
こんな私にみっちり仕込んでください!
・参考になるページ
・読むといい本とか
・作ってみるといいサンプル
・論理的に再帰がどういう物か説く
等どんなことでもいいのでお願いします!
(一応VBで他のちょっとした事ならできる、ぐらいのレベルです)
>>1 てゆーかその前に
「再帰」の定義を教えて?
>>1サンなりにでいいからさ・・・
10 :
デフォルトの名無しさん:02/04/23 00:35
1000!
>>5 関数の中から自分自身(関数)を呼び出し、
それの処理が帰ってくること、と思ってるんですが。
全然見当違いだったらスイマセン。
Delphi Personalをインストールしたら教えてあげよう
マジレス
・単発ネタでスレ立てないで下さい
・削除依頼出しておいて下さい
・再帰をするときってのは大体パターンが決まってる
・そもそもBASICで再帰というのが間違い
>>12 正解!!
===============終了===============
Schemeインストールしたら教えてあげよう
紙とペンを用意しろ。
よくわかってないヤツは計算機にやらせてはいかん。
例題はフィボナッチ数列だ。足し算くらいできるだろ。
フィボナッチ数列の定義はここでは以下のようにする。
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)からやっちまった!?
しょうのないヤツだ。
そいつは答えあわせに使え。
ついでにかかった時間と労力を比較しとけ。
これって再帰?
--->
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;
}
<---
でもいいような気がするが。
便乗質問。
自分自身を呼びつづけて、結局帰ってこなくても再帰は再帰よね?
(戻り値といっしょに処理を返すのが普通だろうけど)
21 :
デフォルトの名無しさん:02/04/23 13:39
main() {main();}
>>20 終了条件が無く、無限ループであってもループと言うが如し。
(CPU時間だけでなくスタック食い尽くす分無限ループより質がわるいがな。)
>20
それは暴走でわ
再起
27 :
デフォルトの名無しさん:02/04/23 14:29
問題
function 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) を求めよ
かってにハノイの塔でもやっててくれよ。
ほれハノイ
(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))))
func(19)程度まではすぐに答えが出るから 一覧表示すればすぐに答え判るだろうけど
これ実行させないで答え判るとエライ人かもしれない
末尾再帰!!
(define (x) (x))
>>27 それ VB?
答えは多分 20920706406
35 :
デフォルトの名無しさん:02/04/23 15:17
>>1 再帰呼び出しの基本的な考え方は次のようになります。
ふすまを開ける
↓
ふすまを開ける
↓
ふすまを開ける
↓
ふすまを開ける
↓
殿発見!!
↓
ふすまを閉める
↓
ふすまを閉める
↓
ふすまを閉める
↓
ふすまを閉める
って感じ?
で、このふすまを開ける作業をモジュール化して、どのふすまを開ける作業でも
応用できれば便利だよね。
上の例では書いてないけど、ふすまを開ける作業ごとに、実は殿はいないかチェックしてるわけ。
だから、毎回同じことをやってると。
で、シリアルに呼び出すのはバカすぎるけど、ループ作って呼び出してもいいよね。
でも殿がいない場合は、もう一回モジュール自身を呼んでもいいわけよ。
このあたりはコールスタックの概念があったほうがいいね。
あまり無頓着なことしてるとスタックオーバーフローを起こすとか。
一回呼ぶごとに何らかの計算もできます。
qsortなんかを見てください。
わかったかなー。
>>34 a_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) ね。
37 :
デフォルトの名無しさん:02/04/23 15:33
祭器はMLの得意技です。MLやりなさい
いいや、scheme をやるのです。
再帰不能
>>36 なるほど。惜しいです
func(2)の時は 1+func(1)+func(1)=3となります
ループでやるとめんどくさいけど再帰を使うと簡単(゚д゚)ウマー
っていうのは quick sort 以外だと何がある?
>>41 再帰でやると順番を逆転するとかが容易 例:2進で印刷するとか
お絵かき屋さんとしてはflood fillなんかを・・・
44 :
デフォルトの名無しさん:02/04/23 16:37
10進数を2進数に変換、二進数を10進数に変換
催奇だ!!
1 名前:1@VB房 投稿日:02/04/23 00:29
どうしても「再帰」っていう概念が理解できないんです!
何度もいろいろ質問しては教えてもらい、それ自体はできるんですが
再帰がどういう構造になってるのか、っていう大本の所を理解していないので
他になかなか応用できないでいます・・・。
こんな私にみっちり仕込んでください!
・参考になるページ
・読むといい本とか
・作ってみるといいサンプル
・論理的に再帰がどういう物か説く
等どんなことでもいいのでお願いします!
(一応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
再帰は数学的帰納法を思い浮かべると楽、な人もいるかも。
>>37-38 情報がたくさんあるschemeの方が良いと思う。
>>45 最初の頃のレスはそういう意味だったのか。ワラタ
49 :
デフォルトの名無しさん:02/04/23 22:33
>>40 Result:=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 なのかなと…。
やっぱ知らない言語はアレだ…。
52 :
デフォルトの名無しさん:02/06/02 07:02
>>27 の使っている言語を知らないので, 多少推測して...
a(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 という値を保持できると仮定して良いの?
それとも...
53 :
デフォルトの名無しさん:02/06/02 07:29
int func(int a)
{
if(a が一定条件を満たす) {
return a;
} else {
return func(a);
}
}
これだけの話。
>>52-53 なんでいまさらこのスレヲアゲルノカナ・・?
>>27の結論出すのに2ヶ月かかったってコトカナ?
ドウデモイイケドナ。
56 :
デフォルトの名無しさん:02/06/03 13:53
void関数を再帰呼び出しにしたら、呼び出すだけで
帰りは無いのですか?
>>1 再起なんて、lispでしか使わないから、覚える必要無し。
returnできるよ
T |
A | 再帰はサブディレクトリ探索に
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 です
>>52 お疲れ様.。 正解です。
そして、27の言語はpascal。
Integerが32bitだと収まらないです
>Integerが32bitだと収まらないです
Int64
>59
センセイ! なぜループじゃなくて再帰を使って階乗を求めるのですか?
スタックの無駄遣いだと思います。
そうですね
>>62 では再帰を使って a^n を 書いてみて下さい
そもそもプログラミングの対象は
再帰的に定義されていることが多い。
つーことで、
>>1さんはプログラミングというより
むしろフォーマルな定義というものに慣れていないのでは、
と思う。sage
_______
∧⊂ヽ, /
ミ゚Д゚,ミ,ノ< ハニャーン
ミ⊃ ,ミ \____________
ミ, ,,ミ
⊂,,,ノ
∪
階乗計算をするのに再帰が便利なんじゃなくて
再帰を勉強するのに階乗計算がイイ。
って事でした。
66 :
デフォルトの名無しさん:02/06/06 16:15
リスト遊びでも読んどけ
スタック積み上げて氏んでくれ
68 :
デフォルトの名無しさん:02/06/06 16:21
ぷよぷよかファイアーエムブレムもどきでも作ってください
69 :
デフォルトの名無しさん:02/06/06 16:27
C,C++,JAVAで再帰をやるやつは逝ってよし
70 :
デフォルトの名無しさん:02/06/06 16:32
71 :
デフォルトの名無しさん:02/06/06 19:47
>>27はDelphiですか?
Resultは予約語?
>>71 yes.
関数は、result に代入した結果が戻り値になる。
さんくす
リンクをクリック(HTMLソース){
while(HTMLソース.最後じゃない()){
タグ=HTMLソース.次の行読む();
if(タグ.リンクです()){
リンクをクリック(タグ.HTMLソース化());
}
}
}
修正。
メイン(){
リンクをクリック("
http://www.2ch.net/");
}
リンクをクリック(アドレス){
HTMLソース=アドレス.HTMLソース化();
while(HTMLソース.最後じゃない()){
タグ=HTMLソース.次の行読む();
if(タグ.リンクです()){
リンクをクリック(タグ.アドレス取り出し());
}
}
}
>>69 いまどきの言語は普通に再帰使うじゃん。
Javaで再帰なんて当たり前だしのぉ。Parent追っかけるのにさ。
クラスライブラリでも(以下略)
>いまどきの言語は普通に再帰使う
これはもちろん
*いまどきの処理系は末尾再帰のgoto書き換えくらいは普通に行うじゃん*
て意味だよね?
ところでさ、FIFAって何の略か知ってるやついる?
FIFA Is the Football Association.
なんだって。
79 :
デフォルトの名無しさん:02/06/24 16:53
LIFOとFIFO
今の会社でこの言葉使ったら誰も知らなかった・・・
MSBとLSBこれも通じなかった・・・(-_-)ウツダ
馬鹿って言うやつが馬鹿
>78
ワラタ
(以下略
83 :
デフォルトの名無しさん:02/06/24 21:52
再帰と再入の違いが分かりません
あと再配置も
リカーシブ
リエントラント
リロケート
>84
リカージョン
86 :
デフォルトの名無しさん:02/06/24 21:57
挿入のやりかたが分りません
87 :
デフォルトの名無しさん:02/06/24 22:10
10 GOSUB 10
GOSUBはいやだよ。GOTOにしとこう。
>>83 再帰と、再入は ASCII 用語辞典
http://yougo.ascii24.com/gh/ に
あった。再配置は、おぼろげな記憶。
再帰: recursive call
サブルーチンの中から、さらに自分自身を呼び出すような処理。この再
帰呼び出しを利用することで、複雑な処理を非常に単純なコードとして実
現できる場合がある。ただし再帰呼び出しを行なうプログラムの実行時に
は、消費されるスタック用メモリに注意する必要がある。
再入: reentrant
「再入可能」という意味。マルチタスク環境では、あるプログラムコー
ドの実行中に、さらにそのプログラムコードの実行が要求されることが
ある。このような場合でも、そのプログラムコードがリエントラントに設
計されていれば、1つのプログラムコードで複数の処理を非同期に実行で
きる。
再配置: relocate
コードやデータ等の位置を配置し直すこと。
きたろうじゃなくって大竹まことじゃなくって……