なあ、再帰関数好きな人いる？

1 名前：名無しのプログラマ [2015/08/09(日) 17:46:33.69 ID:Icb40LOY.net] for,while使うの嫌いで基本的に再帰多用するんだが、だめなの？ 皆から敬遠されてる気がする 684 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 06:52:05.04 ID:BDvTAHGX.net] >>667 CTMCP(ガウディ本)読んで、計算モデル理解した方が良いよ。 685 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 06:56:36.26 ID:ReU+9sFg.net] >>668 理解したよ。それでいいたことは何かな？ 686 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 06:59:39.65 ID:Bq/cKCjD.net] わお。まるで俺が返信したみたい。 まぁ俺も同じことを聞こうか >>668 それで言いたいことはなにかな？ 687 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 07:33:00.36 ID:zGjt7Ia9.net] >>657 おま、戻り値を使いまわしたら基本的に再帰じゃないの？。。。 688 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 07:42:48.23 ID:Bq/cKCjD.net] うわー 馬鹿しかいねぇ 689 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 07:45:22.49 ID:Bq/cKCjD.net] 失礼。すまなんだ。よけいな発言だった 690 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 08:00:20.87 ID:zGjt7Ia9.net] //r:ret,s:diff,n:n int sigma(int r, int s, int n) { 　if (n < 1)return 0; 　if (n == 1) return r; 　return r + sigma(r + s, s, n - 1); } int sigma2(int s, int n) { 　if (n < 1)return 0; 　int r = 0, t = s; 　for (n--; 0 < n; n--, t += s) r = r + t; 　return r; } 戻り値の使いまわしは基本的に再帰 691 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 08:50:03.58 ID:Bq/cKCjD.net] そこで再帰かどうかは決まらないんだけど。 でもあえてそこで決めるのならば(その話に乗るのならば)、手順 (もしくはそれに相当するもの) を覚えている物が再帰。 sum = sum + i; これは現在の状態しか保持しない。 構造を検索するもの、…例えばディレクトリとファイル検索で whileだけを使ったとしても、 出てきたそれぞれのファイル対し、そのアドレスを記録したら、 それは処理における必要資源量の理論最低値は再帰と等価 692 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 08:53:27.64 ID:zGjt7Ia9.net] そそ、戻り値の使いまわしとスタック保存 693 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 08:59:50.82 ID:zGjt7Ia9.net] たとえば、シュミレーションゲームでユニットの移動範囲を調べる とかの全検索は、どうやっても再帰 もちろんＡ＊も再帰 694 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 09:02:33.33 ID:Bq/cKCjD.net] 会話が成り立ってねぇ 695 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:03:26.20 ID:zGjt7Ia9.net] スタック保存の必要がなければループ文でいい 696 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:05:10.34 ID:zGjt7Ia9.net] >手順 (もしくはそれに相当するもの) を覚えている物が再帰。 これがスコープのスタック保存だろ 697 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 09:06:13.64 ID:Bq/cKCjD.net] あんた for(int i = 1; i <= 10; i++) { 　sum = sum + i; } これを再帰って言ったでしょうに。 これはスタックの保存じゃなくて上書きっつーの 698 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:13:54.31 ID:SH0QgRhI.net] sum=sum+iで sum+iのsumはスタック保存 699 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:20:33.46 ID:SH0QgRhI.net] まあスタックを「戻す必要がないから」保存して上書きしてるんだろ 700 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 09:21:52.97 ID:Bq/cKCjD.net] それはスタックじゃねぇ a = 0; a = a + 1; a = a + 2; 以上の三行は再帰とは呼ばない 再帰と言うのは最終段階の55の瞬間に今までの経緯を覚えてて そこで初めて再帰と必要資源量の (理論最低値の) 釣り合いが取れます。 例えば配列に 1, 2, 4, 7, 11,… と記録したらそこで初めてある側面で再帰と同じ資源量 701 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 09:25:47.84 ID:Bq/cKCjD.net] いや再帰っつーのは終わるまで必ず自身がどの手順でそこの処理に居るのかが記録されてるから。 必要がないもくそもない 702 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:26:38.87 ID:zGjt7Ia9.net] sum=sum+iで sum+iのsumはスタック保存値 sum=のsumがスタック保存（＋上書き） こういうのはループでも全然いいけど スコープスタックを保存する必要があるなら、完全に再帰しかない 703 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 09:29:04.79 ID:Bq/cKCjD.net] さいならー 704 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:40:47.32 ID:zGjt7Ia9.net] いや再帰っつーのは終わるまで必ず自身がどの手順でそこの処理に居るのかが記録されてるから。 必要がないもくそもない だから、スコープスタックを保存する必要がある時に、再帰を使う必要があるんですってば 705 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 09:57:57.73 ID:zGjt7Ia9.net] >>651 は >>674 な感じなんだろ ループは、スコープスタックを保存しなくていい時 再帰は、スコープスタックを保存しなければいけない時 再帰の文字通り、手順の戻り道を、覚えている必要があるかどうかだよ 706 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:00:34.66 ID:ReU+9sFg.net] えー、バカ以外には言うまでもないことだが スタックというものは、 値のプッシュ（スタックに積む）と 値のポップ（スタックから取り出す）を 行うためのデータ構造です。 これをしていないものは、当然 スタックではありません。 707 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:01:42.56 ID:zGjt7Ia9.net] バカは知りませんが関数呼び出しはコールスタックです 708 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:01:59.54 ID:ReU+9sFg.net] https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF スタックはコンピュータで用いられる基本的なデータ構造の1つで、 データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で 保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。 709 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:02:49.88 ID:ReU+9sFg.net] >>691 > バカは知りませんが関数呼び出しはコールスタックです どこの話をしてるんですか？ 710 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:03:52.96 ID:ReU+9sFg.net] 再帰というのは、関数の中で 自分自身の関数を呼び出すもののことです。 これをやっていないものは 当然再帰ではありません 711 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:12:58.37 ID:zGjt7Ia9.net] //r:ret,s:diff,n:n int sigma(int r, int s, int n) { 　if (n < 1)return 0; 　if (n == 1) return r; 　return r + sigma(r + s, s, n - 1); } これは全部、スタックに保存されてるよ だから、 int sigma2(int s, int n) { 　if (n < 1)return 0; 　int r = 0, t = s; 　for (n--; 0 < n; n--, t += s) r = r + t; 　return r; } これに比べて、スタック保存分、オーバーロードしているけどね ユニットの移動範囲とか、画像のフィリングとか、 ある点の周囲探索は、スタック保存の再帰関数にするのが一番いいだろ 712 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:16:27.86 ID:zGjt7Ia9.net] たとえば白黒ドットの囲まれた場所のある点からの塗りつぶしで ループだけしか使わないバカがいるのか？ 713 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:19:30.35 ID:Bq/cKCjD.net] な、 会話するの難しいだろ 714 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:21:37.41 ID:ReU+9sFg.net] >>695 お前は知らないだろうけどね。 関数ないのローカル変数っていうのは 全部スタックに保存されるんだよ。 スタックにデータを保存すれば 再帰という理屈であれば、 ローカル変数がある関数はすべて 再帰ってことになってしまう。 もちろんそんなことはありえない。 715 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:21:49.47 ID:zGjt7Ia9.net] 白黒ドットの囲まれた場所のある点からの塗りつぶしで ループだけしか使わないで作れるなら作ってみろよ ニヤニヤしながら見ててやるから 716 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:26:03.39 ID:zGjt7Ia9.net] >>698 え？コールスタックが再帰じゃないの？ それじゃ、関数を呼び出した後、元の位置に戻れないぞ 717 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:26:17.15 ID:ReU+9sFg.net] >>699 閉空間の塗りつぶしだね？ 検索したあったよ。 もちろん再帰は使っていない > この改良版アルゴリズムはスキャンライン・シード・フィル アルゴリズム(Scanline Seed Fill Algorithm)と呼ばれています。 fussy.web.fc2.com/algo/algo3-1.htm 718 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:27:24.93 ID:ReU+9sFg.net] >>700 > え？コールスタックが再帰じゃないの？ ぷぷぷ。こいつマジでわかってなかったんだｗ お前理屈だと、すべての関数呼び出しが再帰ってことになってしまう。 再帰は、関数が自分自身の関数を呼び出している場合のみ。 お前が言ってるのは、単なる関数呼び出しだ。 719 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:34:15.27 ID:zGjt7Ia9.net] サブルーチンの呼び出しの後、 呼び出し元に復元（リターン）できなければ、 プログラムじゃねえよ 720 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:36:14.02 ID:ReU+9sFg.net] ほらほら、こいつ再帰って言わなくなりましたよｗ 自分が言っていたことが間違っていたことがわかったから 恥ずかしくなった 721 名前：んでしょうねｗ [] [ここ壊れてます] 722 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 10:46:29.34 ID:SH0QgRhI.net] コールスタックって再帰だよ 関数が元に戻れてスタック内容も変わらない コールスタックを実装したら、当然再帰関数呼び出しも実装したことになる 723 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 10:47:55.97 ID:ReU+9sFg.net] コールスタックがない関数はないから すべての関数は再帰である。 >>705はそう言っているのです。 生暖かい目で見てあげましょう。 お兄ちゃん！関数使えるようになった！ 私、再帰使いこなしてる！ 724 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 11:00:37.95 ID:zGjt7Ia9.net] ttp://nas6.main.jp/secret/ContainerPtr.htm の ttp://nas6.main.jp/NAS6_tree_clct.h //再帰構文例1 //再帰構文例2 は俺は両方再帰だと思って作ったけどな >>701 みたいのは //再帰構文例1 の構造だろ 725 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 11:05:54.33 ID:zGjt7Ia9.net] 関数の自分自身を呼ばないと再帰関数じゃないっていうのは 頭が固いんじゃないの？ 726 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 11:10:08.71 ID:zGjt7Ia9.net] 訂正 関数の自分自身を呼ばないと再帰処理じゃないっていうのは 頭が固いんじゃないの？ //再帰構文例1 は関数の自分自身を呼んでないけど、どう見ても再帰処理 727 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 11:23:13.73 ID:Bq/cKCjD.net] いっぱい突っ込みどころがあるけどそれは置いといて、 今ひとつピンと来たものがある。 よくよく思い出すと「再帰処理」と「再帰関数」と言う似てるけど別の概念がある。 それを失念していた。 なおスレタイは再帰関数である。 728 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 11:27:58.33 ID:SH0QgRhI.net] で コールスタックは再帰処理だよ 729 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 11:34:56.98 ID:Bq/cKCjD.net] だよ、じゃねぇよ 100のうち俺の失念であろう1だ 会話が成り立ってなさすぎるからどうでもいいんだが >コールスタックを実装したら、当然再帰関数呼び出しも実装したことになる 730 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 11:38:41.59 ID:IJjvRwCO.net] >>707 //再帰構文例2 > は俺は両方再帰だと思って作ったけどな お前が間違ってるんだからお前が書いたコードきて これが再帰なんだとか主張しても意味が無い。 731 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 11:42:04.89 ID:IJjvRwCO.net] https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0 再帰（さいき）とは、あるものについて記述する際に、記述しているもの それ自身への参照が、その記述中にあらわれることをいう。 定義において、再帰があらわれているものを再帰的定義という。 なるほどね。自分自身への参照が必須なんだ。 732 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 11:55:26.05 ID:zGjt7Ia9.net] >>714 だからクラスの関数呼び出しなんて、ほとんど this->が省略されているだけなんだが・・・ 733 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 11:57:10.38 ID:IJjvRwCO.net] >>715 関係ないよ。 734 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 12:03:39.85 ID:9u1zKCQd.net] >>708 頭が固いもなにも、それが再帰関数の定義なんだが… 735 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 12:09:24.27 ID:zGjt7Ia9.net] アセンブリレベルが分からないと説明しようがないな 基本的にスタックでしか動かないし ttp://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node65.html 再帰呼び出し、スタック 736 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 12:13:43.89 ID:zGjt7Ia9.net] >>718の大学教授にこれはループであって再帰ではないってかみついてこいよ def xn2(N) { 　XN = 0; 　for (I=0; I<N; I++) { 　　XN = 2*XN+1; 　} 　return(XN); } 737 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 12:25:42.76 ID:zGjt7Ia9.net] int sum = 0; 　for(int i = 1; i <= 10; i++) { 　　sum = sum + i; } な、これは再帰だろ、頭が悪いんだから、教授に迷惑をかけるなよ 738 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 12:44:51.30 ID:zGjt7Ia9.net] 戻り値を使いまわしたら基本的に再帰なんだよってはじめに書いておいた 739 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 12:56:18.37 ID:zGjt7Ia9.net] >>701 のも 新たなシードを決める際には、バッファ中のどのピクセルを選んでもよいのですが、 新しい順か、古い順かのどちらかに統一するのが普通でしょう。 バッファをスタック構造にすれば新しい順、キューにすれば古い順に自然に決まります。 これを読んでいないのか再帰じゃないと思ってるんだろ 740 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 13:11:58.86 ID:IJjvRwCO.net] > 戻り値を使いまわしたら基本的に再帰なんだよってはじめに書いておいた 違う 741 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 13:14:58.05 ID:zGjt7Ia9.net] >>723 だから、戻り値を使って再帰呼び出ししているのと同じ事だろ 742 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 13:16:02.36 ID:a9 ] [ここ壊れてます] 743 名前：CPEVg5.net mailto: >>721 戻り値を使い回すのはDP(動的計画法)という立派な名前が付いてるんだが [] [ここ壊れてます] 744 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 13:16:18.51 ID:IJjvRwCO.net] 例が良かったなｗ すぐに見つかった。 >>720をアセンブリレベルにすると 見ての通りスタックも関数呼び出しもない。 単なるループ mm.ahs.kitasato-u.ac.jp/~lm00000/sim/ueyama_ip/software/add10asm.html 次の例は １ から １０ まで （実は １０ から １ まで） の整数を加算するプログラムです。 ラベル　 命令コード　 オペランド　 コメント文 　　　　　LD　　　　　B, 10　　　　　; レジスタ B に 10 を代入する 　　　　　LD　　　　　A, 0　　　　　; レジスタ A に 0 を代入する LOOP:　ADD　　　　A, B　　　　　; A に B を加える。加算結果はレジスタ A に。 　　　　　DEC　　　　B　　　　　　　; B の値から 1 を引く 　　　　　JR　　　　　NZ, LOOP　　　; 引いた結果が 0 でなければ LOOP に分岐する STOP:　JR　　　　　STOP　　　　　;プログラム終了。 加算結果はレジスタ A に残る。 745 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 13:16:42.20 ID:IJjvRwCO.net] >>724 ぜんぜん違う 746 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 13:22:00.75 ID:zGjt7Ia9.net] >>726 >>718 のリンクで 正式には再帰で書くけど、 最適化してループで書くってようなことが書いてあるだろ 747 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 13:26:52.77 ID:zGjt7Ia9.net] >>718 のリンクでも >>695 でも ＞これに比べて、スタック保存分、オーバーロードしているけどね こういうわけで再帰をループに最適化するわけ 748 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 13:34:34.79 ID:a9CPEVg5.net] >>729 ねえ、そろそろ無知を晒すのやめない？恥ずかしくないか？ 749 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 13:41:26.99 ID:zGjt7Ia9.net] //等差数列 //定義に忠実に書いた場合 //r:ret,s:diff,n:n int sigma(int r, int s, int n) { 　if (n < 1)return 0; 　if (n == 1) return r; 　return r + sigma(r + s, s, n - 1); } //メモリ使用量を最適化した場合 int sigma2(int s, int n) { 　if (n < 1)return 0; 　int r = 0, t = s; 　for (n--; 0 < n; n--, t += s) r = r + t; 　return r; } で、最適化されたのしか、教わらないし、理解できないのかな？ 750 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 13:48:39.57 ID:zGjt7Ia9.net] 訂正 //等差数列 //定義に忠実に書いた場合 //r:ret,s:diff,n:n int sigma(int r, int s, int n) { 　if (n < 1)return 0; 　if (n == 1) return r; 　return r + sigma(r + s, s, n - 1); } //メモリ使用量を最適化した場合 int sigma2(int s, int n) { 　if (n < 1)return 0; 　int r = 0, t = s; 　for (; 1 < n; n--, t += s) r = r + t; 　return r; } 751 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 14:03:25.65 ID:SH0QgRhI.net] sigma2は最適化された動的計画法 sigmaは「漸化式」の定義に基づいた再帰法 752 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 14:09:21.37 ID:zGjt7Ia9.net] 漸化式で求めた全ての項を 参照する必要があるのならば 動的計画法を用いることはできない 753 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 14:18:04.33 ID:bMqKfWg+.net] >>733 codepad.org/pUWGRddj どこを見れば等差数列だと分かるようになるのでしょうか？ 754 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 14:20:40.72 ID:IJjvRwCO.net] >>728 > 正式には「再帰で書くけど 最適化して（再帰ではなく）ループで書く」 ですね！？ 最適化してループで書いたのだから それは再帰ではないということです。 755 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 14:42:48.35 ID:zGjt7Ia9.net] >>735 ああ、ごめんね sigmaだから1〜nまでの等差数列の和だよ 漸化式の全ての項を使う →全てのノードを使う時は動的計画法で最適化できないんよ そのケースは、ある点からの周囲の経路を探索する場合 ディレクトリ探索だったり、塗りつぶしだったり、つまり全検索をかける場合 こういうのは再帰を使うだろうに 756 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 14:44:53.85 ID:zGjt7Ia9.net] つまり経路の全検索をかける場合 こういうのは再帰を使うだろうに 757 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 14:56:44.42 ID:IJjvRwCO.net] あれ？ 根本的な前提わかってないの？ 誰も再帰を絶対に使わないで書けとか言ってなくて、 ループで簡単にかけるようなものを わざわざ再帰で書くなよ（笑）って 話なんだけど。 758 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 14:57:36.94 ID:zGjt7Ia9.net] >>735 sigmaだから1〜n-1までの等差s数列の和 s=3なら sigma=3+6+9+12+・・・ 759 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 15:08:23.80 ID:zGjt7Ia9.net] //1〜n-1までの等差s数列の和 //定義に忠実に書いた場合 //r:ret,s:diff,n:n int sigma(int r, int s, int n) { 　if (n < 1)return 0; 　if (n == 1) return r; 　return r + sigma(r + s, s, n - 1); } //メモリ使用量を最適化した場合 int sigma2(int s, int n) { 　if (n < 1)return 0; 　int r = 0, t = s; 　for (; 1 < n; n--, t += s) r = r + t; 　return r; } べつにどっちで書けって言われても 項をスタックするかしないだけの違いだけど？ 760 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:10:18.45 ID:IJjvRwCO.net] > 項をスタックするかしないだけの違いだけど？ それよりも重要な違いは、 自分の関数自身を呼ぶかどうかだよ。 自分自身を呼ぶのが再帰、 そうでないのは再帰じゃない。 761 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:16:46.56 ID:dKM7sd/0.net] その定義だと相互再帰は再帰じゃないのかと重箱の隅をつつかれるけど、間違いじゃない。 クソコ 762 名前：テは速やかにNG入れるといいよ。ラーメンが好きかどうかの話をしている中でお茶漬けもラーメンだと強弁するような、話題に入ることができない人だから。 [] [ここ壊れてます] 763 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:18:48.81 ID:ygimYbNM.net] 末尾再帰にあらずんば再帰にあらず 764 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 15:19:27.30 ID:zGjt7Ia9.net] 利点と欠点があって 再帰：書けない漸化式はない、項をスタックするからメモリを消費する ループ：項の参照が少ない漸化式のみ書ける、項をスタックしないからメモリ使用量は少ない そんだけ 765 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:23:23.93 ID:ygimYbNM.net] >>745 ループと再帰は厳密に完全互換ですよ 766 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 15:31:56.99 ID:zGjt7Ia9.net] >>746 ノード検索とか再帰のノード全てメモしてループするとか 素直に再帰を使っちゃいかんのかいな 767 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:35:58.97 ID:ygimYbNM.net] >>747 可否の話をしただけ >>745で可能性に対する言及が間違っているから、それを指摘したにすぎない forでかけるものは、再帰でもかけるし 再帰でかけるものは、forでもかける 768 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:38:08.67 ID:1TQgpEDy.net] うわーこいつ最悪だな 自分がほんまモンの馬鹿であるという自覚が全くないバカ ま、見てる分には面白いけど他人に迷惑掛けんなよ 他人に迷惑を掛けるとなんとかキューゼットとかいう奴みたいに嫌われ者になっぞ 769 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 15:42:58.31 ID:gAQxPGKS.net] NAS6って宗教板で「重力が神」みたいなことをホザいてた奴だな 770 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 18:40:37.54 ID:zGjt7Ia9.net] 利点と欠点があって 再帰：書けない漸化式はない 項をスタックするからメモリを消費する ループ：項の参照が少ない漸化式のみ書ける あるいは項をメモする必要がある 項をスタックしないからメモリ使用量は少ない そんだけ 771 名前：デフォルトの名無しさん [2015/09/05(土) 19:01:21.79 ID:tTlkULNN.net] >>751 スタックしない再帰があれば最強じゃん 772 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 19:32:52.27 ID:6bqI6s7I.net] 再帰処理と、再帰関数や再帰呼出とをきちんと区別しろ。 ループは再帰処理の一種だ。 773 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 19:37:09.10 ID:Bq/cKCjD.net] まず定義に逆らうのやめろよ。 再帰は自己よ呼び出す関数だ。当然実行中の処理手順は無条件にスタックされる。 そして都合よく「再帰」と「ループ」を分けて見たり、全部再帰と言って見たり挙動不審なことをするのもやめれよ。 もはや会話が成り立たん。 ちなみに俺の場合は、一番最初の冒頭のレスで「極論的には再帰もループも同じ」 とした上で、その後は一貫して再帰とループを区別してんだよ。 すなわちCの状態のように関数とスタックの抽象化が出来てる状態で初めてループと再帰があるんだ。 君がやってることは犬小屋も本棚もどっちも「木」で出来てるから同じと言って見たり、 犬小屋と本棚は別物のように書いて見たり、 木の状態を指してこれは「犬小屋」と言って見たり、 「本棚」を指して「犬小屋」と言って見たり、 そもそもなんの話をしてるか分からなくなって見たり。 774 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 19:40:47.01 ID:CMLBJgqr.net] schemeのnamed letは繰り返し? 再帰? 775 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 20:00:58.23 ID:zGjt7Ia9.net] double calcPI(double r, double s, double n) { 　double t = 1.0; 　if (s == 1) t = 2.0; 　if (n == 1) return r; 　return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1)); } double calcPI2() { 　double sse = 0.00000000000001;　double a = 0.125; 　double b = sqrt(a);　double c = 1.0 + 3.0 * b; 　double d = sqrt(c);　double e = 0.625; 　double f = d - e;　d = 2 * d; 　b = f - b;　c = c + f; 　double npow = 4; 　do { 　　npow = 2 * npow;　　f = (c + d) / 2; 　　d = sqrt(c * d);　　f = f - d; 　　d = 2 * d;　　b = b - f;　　c = f + d; 　} while (sse < f); 　f = f * f / 4;　c = c + d; 　return (c * c - f - f / 2) / (c * b - f) / npow; } どっちが簡単だと思う？ 776 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 20:25:21.94 ID:zGjt7Ia9.net] double calcPI(double r, double s, double n) { 　double t = 1.0; 　if (s == 1) t = 2.0; 　if (n == 1) return r; 　return t * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1)); } double calcPI3(double n) { 　double r = 1.0; 　double s = 1.0; 　double t = 1.0; 　while (1 < n) { 　　t = (t * s / (2.0 * s + 1.0)); 　　r = r + t; 　　s += 1; 　　n -= 1; 　} 　return 2.0 * r; } 意地悪が過ぎたが、今度はマジ どっちが可読性があるの？ 777 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 20:34:20.88 ID:zGjt7Ia9.net] ああ、ちなみにπの漸化式は 2(1+(1/3)+(1/3)(2/5)+(1/3)(2/5)(3/7)+...) だからね 778 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 20:49:22.97 ID:zGjt7Ia9.net] 変数名がごっちゃにならないように書き直し double calcPI(double r, double s, double n) { 　double u = 1.0; 　if (s == 1) u = 2.0; 　if (n == 1) return r; 　return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1)); } double calcPI3(double n) { 　double r = 1.0; 　double s = 1.0; 　double t = 1.0; 　double u = 2.0; 　while (1 < n) { 　　t = (t * s / (2.0 * s + 1.0)); 　　r = r + t; 　　s += 1; 　　n -= 1; 　} 　return u * r; } 779 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 21:09:08.26 ID:zGjt7Ia9.net] 完全に同じ処理にしたけど、どっちが楽なんだろうね？ double calcPI(double r, double s, double n) { 　double u = 1.0; 　if (s == 1) u = 2.0; 　if (n == 0) return r; 　return u * (r + calcPI(r * s / (2.0 * s + 1.0), s + 1, n - 1)); } double calcPI3(double n) { 　double r = 1.0; 　double s = 1.0; 　double t = 1.0; 　double u = 1.0; 　while (0 < n) { 　　t = t * s / (2.0 * s + 1.0); 　　r = u * (r + t); 　　s += 1; 　　n -= 1; 　} 　u = 2.0; 　return u * r; } 780 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 21:16:59.43 ID:zGjt7Ia9.net] 我々は「軍国主義者」を打倒したと、我らが「軍事パレード」で宣言 781 名前：デフォルトの名無しさん [2015/09/05(土) 21:27:52.93 ID:tTlkULNN.net] >>761 Javaできる？ Javaで2つのint型配列を結合する処理を再帰で書いてみて 782 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 21:55:59.06 ID:zGjt7Ia9.net] コンパイラ入れんのめんどくさいからパス #include <iostream> void init(int * p, int n) { 　for (; 0 < n; n--) p[n] = 0; } void disp(int * p, int n) { 　std::cout << std::endl; 　for (int i = 0; i < n; i++) std::cout << p[i] << " "; 　std::cout << std::endl; } int recUnit(int i, int j, int *a, int na, int *b, int nb) { 　if (i < na && j < nb) a[i] = b[j]; 　else return i; 　return recUnit(i + 1, j + 1, a, na, b, nb); } void unit(int *a, int na, int *b, int nb, int *c, int nc) { 　int i; 　i = recUnit(0, 0, a, na, b, nb); 　recUnit(i, 0, a, na, c, nc); } 783 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 21:56:37.35 ID:zGjt7Ia9.net] void unit2(int *a, int na, int *b, int nb, int *c, int nc) { 　int i, j; 　for (i = 0, j = 0; j < nb; i++, j++) if (i < na)a[i] = b[j]; 　for (j = 0; j < nc; i++, j++) if (i < na)a[i] = c[j]; } int main() { 　int a[10], b[5] = { 0, 1, 2, 3, 4 }, c[5] = { 5, 6, 7, 8, 9 }; 　init(a, 10);　unit(a, 10, b, 5, c, 5);　disp(a, 10); 　init(a, 10);　unit2(a, 10, b, 5, c, 5);　disp(a, 10); 　return 0; } 784 名前：NAS6 ◆n3AmnVhjwc [2015/09/05(土) 22:03:28.78 ID:zGjt7Ia9.net] ミスった #include <iostream> void init(int * p, int n) { 　for (; 0 < n; n--) p[n - 1] = 0; } void disp(int * p, int n) { 　std::cout << std::endl; 　for (int i = 0; i < n; i++) std::cout << p[i] << " "; 　std::cout << std::endl; } int recUnit(int i, int j, int *a, int na, int *b, int nb) { 　if (i < na && j < nb) a[i] = b[j]; 　else return i; 　return recUnit(i + 1, j + 1, a, na, b, nb); } void unit(int *a, int na, int *b, int nb, int *c, int nc) { 　int i; 　i = recUnit(0, 0, a, na, b, nb); 　recUnit(i, 0, a, na, c, nc); }

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef