5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

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

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

6 :デフォルトの名無しさん:02/04/23 00:33
>>7

7 :デフォルトの名無しさん:02/04/23 00:33
>>6

8 :デフォルトの名無しさん:02/04/23 00:33
>>6

9 :デフォルトの名無しさん:02/04/23 00:33
>>10

10 :デフォルトの名無しさん:02/04/23 00:35
1000!

11 :デフォルトの名無しさん:02/04/23 00:36
http://pc.2ch.net/test/read.cgi/tech/1019489340/

12 :1@VB房:02/04/23 00:36
>>5
関数の中から自分自身(関数)を呼び出し、
それの処理が帰ってくること、と思ってるんですが。
全然見当違いだったらスイマセン。

13 :デフォルトの名無しさん:02/04/23 00:37
Delphi Personalをインストールしたら教えてあげよう

14 :デフォルトの名無しさん:02/04/23 00:41
マジレス
・単発ネタでスレ立てないで下さい
・削除依頼出しておいて下さい
・再帰をするときってのは大体パターンが決まってる
・そもそもBASICで再帰というのが間違い

15 :デフォルトの名無しさん:02/04/23 00:45
>>12

正解!!


===============終了===============

16 :デフォルトの名無しさん:02/04/23 00:48
Schemeインストールしたら教えてあげよう

17 :関係なくても知らん:02/04/23 00:59
紙とペンを用意しろ。
よくわかってないヤツは計算機にやらせてはいかん。
例題はフィボナッチ数列だ。足し算くらいできるだろ。
フィボナッチ数列の定義はここでは以下のようにする。
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)からやっちまった!?
しょうのないヤツだ。
そいつは答えあわせに使え。
ついでにかかった時間と労力を比較しとけ。

18 :デフォルトの名無しさん:02/04/23 01:35
再帰
http://pc.2ch.net/test/read.cgi/tech/992241842/l50

19 :あぼーん:02/04/23 07:36
これって再帰?
--->
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;
}
<---
でもいいような気がするが。

20 :通りすがりのもの:02/04/23 11:25
便乗質問。

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

21 :デフォルトの名無しさん:02/04/23 13:39
main() {main();}

22 :デフォルトの名無しさん:02/04/23 13:45
>>20
終了条件が無く、無限ループであってもループと言うが如し。

(CPU時間だけでなくスタック食い尽くす分無限ループより質がわるいがな。)

23 :デフォルトの名無しさん:02/04/23 13:46
>20
それは暴走でわ

24 :優しすぎて損ばかりしている名無しさん:02/04/23 13:47
http://www.google.co.jp/search?q=VB%82%C5%8D%C4%8BA%81@%83T%83%93%83v%83%8B&hl=ja&lr=

25 :デフォルトの名無しさん:02/04/23 14:00
>>19
うん。

>>20
うん。

26 :デフォルトの名無しさん:02/04/23 14:24
再起

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) を求めよ


28 :デフォルトの名無しさん:02/04/23 14:32
かってにハノイの塔でもやっててくれよ。

29 :デフォルトの名無しさん:02/04/23 14:44
ほれハノイ
(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))))


30 :27:02/04/23 14:45
func(19)程度まではすぐに答えが出るから 一覧表示すればすぐに答え判るだろうけど

これ実行させないで答え判るとエライ人かもしれない

31 :デフォルトの名無しさん:02/04/23 14:47
末尾再帰!!

32 :デフォルトの名無しさん:02/04/23 14:51
(define (x) (x))

33 :デフォルトの名無しさん:02/04/23 14:56
>>27
それ VB?
答えは多分 20920706406

34 :デフォルトの名無しさん:02/04/23 15:02
>>33 どうして?

35 :デフォルトの名無しさん:02/04/23 15:17
>>1
再帰呼び出しの基本的な考え方は次のようになります。

ふすまを開ける
  ↓
ふすまを開ける
  ↓
ふすまを開ける
  ↓
ふすまを開ける
  ↓
殿発見!!
  ↓
ふすまを閉める
  ↓
ふすまを閉める
  ↓
ふすまを閉める
  ↓
ふすまを閉める

って感じ?
で、このふすまを開ける作業をモジュール化して、どのふすまを開ける作業でも
応用できれば便利だよね。
上の例では書いてないけど、ふすまを開ける作業ごとに、実は殿はいないかチェックしてるわけ。
だから、毎回同じことをやってると。
で、シリアルに呼び出すのはバカすぎるけど、ループ作って呼び出してもいいよね。
でも殿がいない場合は、もう一回モジュール自身を呼んでもいいわけよ。
このあたりはコールスタックの概念があったほうがいいね。
あまり無頓着なことしてるとスタックオーバーフローを起こすとか。
一回呼ぶごとに何らかの計算もできます。
qsortなんかを見てください。
わかったかなー。

36 :33:02/04/23 15:20
>>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やりなさい

38 :デフォルトの名無しさん:02/04/23 15:47
いいや、scheme をやるのです。

39 :デフォルトの名無しさん:02/04/23 15:49
再帰不能

40 :デフォルトの名無しさん:02/04/23 15:55
>>36 なるほど。惜しいです

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

41 :デフォルトの名無しさん:02/04/23 15:57
ループでやるとめんどくさいけど再帰を使うと簡単(゚д゚)ウマー
っていうのは quick sort 以外だと何がある?

42 :デフォルトの名無しさん:02/04/23 16:07
>>41
 再帰でやると順番を逆転するとかが容易 例:2進で印刷するとか

43 :デフォルトの名無しさん:02/04/23 16:10
お絵かき屋さんとしてはflood fillなんかを・・・

44 :デフォルトの名無しさん:02/04/23 16:37
10進数を2進数に変換、二進数を10進数に変換
催奇だ!!

45 :デフォルトの名無しさん:02/04/23 16:40
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


46 :デフォルトの名無しさん:02/04/23 16:55
再帰は数学的帰納法を思い浮かべると楽、な人もいるかも。

>>37-38
情報がたくさんあるschemeの方が良いと思う。

47 :再帰的スレ:02/04/23 19:15
とりあえずこのスレを1から読んでこい

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

48 :デフォルトの名無しさん:02/04/23 21:10
>>45
最初の頃のレスはそういう意味だったのか。ワラタ

49 :デフォルトの名無しさん:02/04/23 22:33
今頃、気がついたのか?
http://pc.2ch.net/test/read.cgi/tech/992241842/207-208

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



50 :デフォルトの名無しさん:02/04/23 22:36
>>1
それは君自身に問え。
それが再帰だ。

51 :36:02/04/24 01:15
>>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);
  }
}

これだけの話。


54 :デフォルトの名無しさん:02/06/02 11:16
>>52-53
なんでいまさらこのスレヲアゲルノカナ・・?
>>27の結論出すのに2ヶ月かかったってコトカナ?
ドウデモイイケドナ。

55 :デフォルトの名無しさん:02/06/02 11:56
>>54
GC してたんだよ、きっと。


56 :デフォルトの名無しさん:02/06/03 13:53
void関数を再帰呼び出しにしたら、呼び出すだけで
帰りは無いのですか?

57 :デフォルトの名無しさん:02/06/03 14:02
>>1
再起なんて、lispでしか使わないから、覚える必要無し。

58 :デフォルトの名無しさん:02/06/03 14:02
returnできるよ


59 :Delフサギコ ◆zE1iiRdQ :02/06/03 14:44
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 です

60 :デフォルトの名無しさん:02/06/03 17:35
>>52 お疲れ様.。 正解です。

 そして、27の言語はpascal。
 Integerが32bitだと収まらないです

61 :デフォルトの名無しさん:02/06/03 20:39
>Integerが32bitだと収まらないです
Int64

62 :いぢわるな質問:02/06/05 09:08
>59
センセイ! なぜループじゃなくて再帰を使って階乗を求めるのですか?
スタックの無駄遣いだと思います。


63 :デフォルトの名無しさん:02/06/05 09:55
そうですね >>62

では再帰を使って a^n を 書いてみて下さい

64 :デフォルトの名無しさん:02/06/05 17:23
そもそもプログラミングの対象は
再帰的に定義されていることが多い。

つーことで、>>1さんはプログラミングというより
むしろフォーマルな定義というものに慣れていないのでは、
と思う。sage

65 :Delフサギコ ◆zE1iiRdQ :02/06/06 13:33
         _______
  ∧⊂ヽ, /
  ミ゚Д゚,ミ,ノ< ハニャーン
  ミ⊃ ,ミ  \____________
  ミ,  ,,ミ 
  ⊂,,,ノ
    ∪
階乗計算をするのに再帰が便利なんじゃなくて
再帰を勉強するのに階乗計算がイイ。

って事でした。

66 :デフォルトの名無しさん:02/06/06 16:15
リスト遊びでも読んどけ


67 :デフォルトの名無しさん:02/06/06 16:17
スタック積み上げて氏んでくれ

68 :デフォルトの名無しさん:02/06/06 16:21
ぷよぷよかファイアーエムブレムもどきでも作ってください


69 :デフォルトの名無しさん:02/06/06 16:27
C,C++,JAVAで再帰をやるやつは逝ってよし

70 :デフォルトの名無しさん:02/06/06 16:32
>>69
PL/SQLで使った漏れはOKですか?

71 :デフォルトの名無しさん:02/06/06 19:47
>>27はDelphiですか?
Resultは予約語?

72 :デフォルトの名無しさん:02/06/06 20:14
>>71
yes.
関数は、result に代入した結果が戻り値になる。

73 :71:02/06/06 20:18
さんくす

74 :デフォルトの名無しさん:02/06/06 23:21
リンクをクリック(HTMLソース){
  while(HTMLソース.最後じゃない()){
    タグ=HTMLソース.次の行読む();
    if(タグ.リンクです()){
      リンクをクリック(タグ.HTMLソース化());
    }
  }
}


75 :デフォルトの名無しさん:02/06/06 23:47
修正。

メイン(){
 リンクをクリック("http://www.2ch.net/");
}
リンクをクリック(アドレス){
  HTMLソース=アドレス.HTMLソース化();
  while(HTMLソース.最後じゃない()){
    タグ=HTMLソース.次の行読む();
    if(タグ.リンクです()){
      リンクをクリック(タグ.アドレス取り出し());
    }
  }
}


76 :デフォルトの名無しさん:02/06/06 23:59
>>69
いまどきの言語は普通に再帰使うじゃん。
Javaで再帰なんて当たり前だしのぉ。Parent追っかけるのにさ。
クラスライブラリでも(以下略)

77 :お約束:02/06/07 14:10
>いまどきの言語は普通に再帰使う
これはもちろん
*いまどきの処理系は末尾再帰のgoto書き換えくらいは普通に行うじゃん*
て意味だよね?

78 :デフォルトの名無しさん:02/06/07 21:43
ところでさ、FIFAって何の略か知ってるやついる?
FIFA Is the Football Association.
なんだって。

79 :デフォルトの名無しさん:02/06/24 16:53
LIFOとFIFO
今の会社でこの言葉使ったら誰も知らなかった・・・
MSBとLSBこれも通じなかった・・・(-_-)ウツダ

80 :デフォルトの名無しさん:02/06/24 16:57
馬鹿って言うやつが馬鹿

81 :デフォルトの名無しさん:02/06/24 16:58
>78

ワラタ

82 :デフォルトの名無しさん:02/06/24 17:13
(以下略

83 :デフォルトの名無しさん:02/06/24 21:52
再帰と再入の違いが分かりません
あと再配置も

84 :デフォルトの名無しさん:02/06/24 21:53
リカーシブ
リエントラント
リロケート

85 :デフォルトの名無しさん:02/06/24 21:54
>84
リカージョン

86 :デフォルトの名無しさん:02/06/24 21:57
挿入のやりかたが分りません

87 :デフォルトの名無しさん:02/06/24 22:10
10 GOSUB 10


88 :デフォルトの名無しさん:02/06/24 22:12
GOSUBはいやだよ。GOTOにしとこう。

89 :デフォルトの名無しさん:02/06/24 22:57
>>83
再帰と、再入は ASCII 用語辞典 http://yougo.ascii24.com/gh/
あった。再配置は、おぼろげな記憶。

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

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

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

90 :デフォルトの名無しさん:02/06/25 00:08
>>86 はいはい。

91 :デフォルトの名無しさん:02/07/11 07:37
きたろうじゃなくって大竹まことじゃなくって……

21 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)