再帰をみっちり仕込んで下さい！

どうしても「再帰」っていう概念が理解できないんです！
何度もいろいろ質問しては教えてもらい、それ自体はできるんですが
再帰がどういう構造になってるのか、っていう大本の所を理解していないので
他になかなか応用できないでいます・・・。
こんな私にみっちり仕込んでください！

・参考になるページ
・読むといい本とか
・作ってみるといいサンプル
・論理的に再帰がどういう物か説く
等どんなことでもいいのでお願いします！
（一応VBで他のちょっとした事ならできる、ぐらいのレベルです）

>>2

>>3

>>4

>>1

てゆーかその前に
「再帰」の定義を教えて？　>>1ｻﾝなりにでいいからさ・・・

>>7

>>6

>>6

>>10

1000!

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

>>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)からやっちまった!?
しょうのないヤツだ。
そいつは答えあわせに使え。
ついでにかかった時間と労力を比較しとけ。

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

これって再帰?
--->
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;
}
<---
でもいいような気がするが。

便乗質問。

自分自身を呼びつづけて、結局帰ってこなくても再帰は再帰よね？
（戻り値といっしょに処理を返すのが普通だろうけど）

main() {main();}

>>20
終了条件が無く、無限ループであってもループと言うが如し。

（ＣＰＵ時間だけでなくスタック食い尽くす分無限ループより質がわるいがな。）

>20
それは暴走でわ

http://www.google.co.jp/search?q=VB%82%C5%8D%C4%8BA%81@%83T%83%93%83v%83%8B&hl=ja&lr=

>>19
うん。

>>20
うん。

再起

問題

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

>>33 どうして？

>>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) ね。

祭器はMLの得意技です。MLやりなさい

いいや、scheme をやるのです。

再帰不能

>>36 なるほど。惜しいです

func(2)の時は 1+func(1)+func(1)=3となります

ループでやるとめんどくさいけど再帰を使うと簡単(ﾟдﾟ)ｳﾏｰ
っていうのは quick sort 以外だと何がある？

>>41
　再帰でやると順番を逆転するとかが容易　例：2進で印刷するとか

お絵かき屋さんとしてはflood fillなんかを・・・

１０進数を２進数に変換、二進数を１０進数に変換
催奇だ！！

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の方が良いと思う。

とりあえずこのスレを１から読んでこい

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

>>45
最初の頃のレスはそういう意味だったのか。ﾜﾗﾀ

今頃、気がついたのか？
http://pc.2ch.net/test/read.cgi/tech/992241842/207-208

ついでにオマケ
向こうから、こっちを呼び出して相互再帰だー。
http://pc.2ch.net/test/read.cgi/tech/992241842/209

>>1
それは君自身に問え。
それが再帰だ。

>>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 なのかなと…。

やっぱ知らない言語はアレだ…。

>>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 という値を保持できると仮定して良いの?
それとも...

int func(int a)
{
　　if(a が一定条件を満たす) {
　　　　return a;
　　} else {
　　　　return func(a);
　　}
}

これだけの話。

>>52-53
なんでいまさらこのスレヲアゲルノカナ・・？
>>27の結論出すのに２ヶ月かかったってコトカナ？
ドウデモイイケドナ。

>>54
GC してたんだよ、きっと。

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

　　　　　　　　　＿＿＿＿＿＿＿
　　∧⊂ヽ,　／
　　ﾐﾟДﾟ,ﾐ,ﾉ＜　ハニャーン
　　ﾐ⊃ ,ﾐ　　＼＿＿＿＿＿＿＿＿＿＿＿＿
　　ﾐ,　 ,,ﾐ　
　　⊂,,,ノ
　　　 ∪
階乗計算をするのに再帰が便利なんじゃなくて
再帰を勉強するのに階乗計算がｲｲ。

って事でした。

リスト遊びでも読んどけ

スタック積み上げて氏んでくれ

ぷよぷよかファイアーエムブレムもどきでも作ってください

C,C++,JAVAで再帰をやるやつは逝ってよし

>>69
ＰＬ／ＳＱＬで使った漏れはＯＫですか？

>>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.
なんだって。

LIFOとFIFO
今の会社でこの言葉使ったら誰も知らなかった・・・
MSBとLSBこれも通じなかった・・・(-_-)ｳﾂﾀﾞ

馬鹿って言うやつが馬鹿

>78

ﾜﾗﾀ

（以下略

再帰と再入の違いが分かりません
あと再配置も

リカーシブ
リエントラント
リロケート

>84
リカージョン

挿入のやりかたが分りません

10　GOSUB　10

GOSUBはいやだよ。GOTOにしとこう。

>>83
再帰と、再入は ASCII 用語辞典 http://yougo.ascii24.com/gh/ に
あった。再配置は、おぼろげな記憶。

再帰: recursive call
　サブルーチンの中から、さらに自分自身を呼び出すような処理。この再
帰呼び出しを利用することで、複雑な処理を非常に単純なコードとして実
現できる場合がある。ただし再帰呼び出しを行なうプログラムの実行時に
は、消費されるスタック用メモリに注意する必要がある。

再入: reentrant
　「再入可能」という意味。マルチタスク環境では、あるプログラムコー
ドの実行中に、さらにそのプログラムコードの実行が要求されることが
ある。このような場合でも、そのプログラムコードがリエントラントに設
計されていれば、１つのプログラムコードで複数の処理を非同期に実行で
きる。

再配置: relocate
　コードやデータ等の位置を配置し直すこと。

>>86 はいはい。

きたろうじゃなくって大竹まことじゃなくって……