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

1 名前：名無しのプログラマ [2015/08/09(日) 17:46:33.69 ID:Icb40LOY.net] for,while使うの嫌いで基本的に再帰多用するんだが、だめなの？ 皆から敬遠されてる気がする 655 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 18:34:45.30 ID:FR19Rjgq.net] 再帰キティは、理由なんか無く難癖つけるだけのレスばかり 656 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 20:04:17.17 ID:RgFRqfXr.net] >>638 数学的に突き詰めれば自然数だって帰納的に定義されるものなんだから、 ループは必ず再帰に置き換えられるね(もちろん逆もまた真) したがって意味がないことはない あとはどっちが読みやすいかだけの話 モダン言語の流れは手続き的なループをなくして、再帰や高階関数を使う 方向のようだけどね 657 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 20:31:46.45 ID:K7Q0EkNO.net] 再帰とループの違いはなに？ 手順をスタックしてるかどうかでしょ まぁループと再帰を別に考えてる(と言うか感じてる)時点で三流くささがするのだけど 658 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 20:32:19.95 ID:FR19Rjgq.net] それモダン言語じゃなくて、性能の悪い非実用的な言語なだけ 659 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 20:55:16.54 ID:RgFRqfXr.net] >>643 最近はマシンスペックが上がってるからね 性能より抽象的な書き方ができるのを求めるようになってるんだよ 性能カリカリに求めたい場合だけCとか使っておけばいい世界 660 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 21:38:09.28 ID:vuZU5Hwi.net] >>642 > 再帰とループの違いはなに？ ループ・・・小学校で習う（1から10までの数字を足し算しょう等） 再帰・・・高校で習う。（1からnまでの自然数の和を計算式で表す） 661 名前：デフォルトの名無しさん [2015/09/04(金) 21:49:10.66 ID:q06Od88z.net] >>645 まったく理解できてない…… 662 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 21:49:46.26 ID:vuZU5Hwi.net] >>646 「間違ってる」とは言わないんだなｗ 663 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 21:54:59.88 ID:K7Q0EkNO.net] なんかどうでもいいや 664 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 21:59:29.06 ID:vuZU5Hwi.net] はい、反論も出なかったわけで、 つまりループと再帰ではループのほうがわかりやすいんだよね。 単純なループじゃない場合は、再帰のほうがいい場合もある。 だけどループでいいのならば、ループのほうがわかりやすい。 それは小学生でもループを理解していることからわかる。 （小学生にループというのは、nにn-1を足すのを0になるまで繰り返すとか言ってもわからない） 665 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 22:17:32.25 ID:6Rt4goII.net] 最新の実験的な言語で昔の関数型に回帰して再帰に走ってるの 単に言語開発のネタ切れしてるだけじゃねぇの 開発サイドの人間が必死こいて宣伝してるんだったら気持ちもわかるが ユーザーだったらもっとマシな言語あるでしょとしか言えない 666 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 22:24:44.42 ID:q06Od88z.net] >>647 根底から間違ってる、って言えばよかったの？ まず、(((((((((1+2)+3)+4)...+10) は典型的な再帰構造。ループでもなんでもない。 そして和の公式 n*(n+1)/2 は再帰でも何でもない閉じた式表現 （というか、再帰を使わない式にすることこそがその眼目だ）。 667 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:01:37.97 ID:vuZU5Hwi.net] 1から10まで足せって 小学生に言って、そんな式書く奴いないなｗ 普通は 1 + 1 = 2 2 + 2 = 4 4 + 3 = 7 7 + 4 = 11 って計算するんだぜ。 これを10まで繰り返す。 まさにループ 668 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:20:57.61 ID:q06Od88z.net] >>652 それ全然ループじゃないから。 669 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:24:17.87 ID:q06Od88z.net] n-1 までの和に n を足せば nまでの和が得られる、という原理に忠実な計算なんで 再帰以外のなにものでもないんだけど、基礎論触ったことないとわかんないかもね。 670 名前：デフォルトの名無しさん [2015/09/04(金) 23:26:41.39 ID:yf6WF608.net] >>654 わかったところでカスだけどな。 再帰っていうのは木偶の坊の代名詞。 671 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:28:22.98 ID:kQbi8Wuv.net] 一つの見方しかできないのは数学に向いてないよ 672 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:29:28.63 ID:vuZU5Hwi.net] >>653 ループじゃんｗ 書けば理解できるのか？ int sum = 0; for(int i = 1; i <= 10; i++) { 　sum = sum + i; } これをステップ実行したのが>>652 673 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:30:53.74 ID:K7Q0EkNO.net] おまえら夏休みは終わったんだぞ 674 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:33:40.85 ID:vuZU5Hwi.net] >>658 9月にそれを言うってことは お前大卒（もしくは在籍）じゃないのか？ 675 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 23:43:51.99 ID:RgFRqfXr.net] >>655 分かったなら再帰が役に立つことぐらい簡単に理解できそうなもんだけどなー 理解できないならわかってないんだよ 676 名前：デフォルトの名無しさん [2015/09/05(土) 00:20:19.44 ID:LWQiKMu8.net] >>660 ループの方が100億万倍やくに立つ。 再帰は数学に憧れてるだけで数学できない出来損ない野郎が使う。 677 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 00:45:04.95 ID:j+vMQGdO.net] いや、goto の方が1000億万倍役に立つだろ。 678 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 00:56:03.07 ID:dKM7sd/0.net] a. 再帰は不要 b. ループは不要 c. どっちも欲しい d. 言語に合わせる aとb(いるのか？)に精神病患者がいるせいで、 cの人の投げた話題を勝手にa(あるいはb)の人間の主張と見なして攻撃するのがおかしい。 aに反駁したらループ不要派だとレッテルを貼られ、 bに反論したら再帰理解できない馬鹿とレッテルを貼られるが、そもそもnot a != bだしnot b != aだからな。 再帰関数を作る時は、頭に保持しなきゃならない情報が少ないのがいいよ。 f(n)の定義を使ってf(n)を定義できるイメージ。場合分けだけで済む。 古典的なインデックスを使うforループより、要素を1つずつ取り出すっていうのが明確なforeachが好まれるのも似た理屈だと思う。 679 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 01:09:05.88 ID:dKM7sd/0.net] あと、再帰はパターンマッチがあると途端に利便性が上がる。 例えばリストの要素を2つ以上必要とする処理を書くとき、OCamlだと let rec foo acc xs = match xs with | x :: y :: rest -> foo (do_something x y acc) y::rest) | _ :: [] | [] -> finish_something みたいに書けて楽。ループだとインデックスの範囲とか終了条件とか色々考慮しなきゃならんので手間がかかる。 680 名前：デフォルトの名無しさん [2015/09/05(土) 01:13:53.21 ID:LWQiKMu8.net] >>664 パターンマッチは邪道 ナローイングなキャストを誤魔化してるだけ 681 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 01:22:40.76 ID:9u1zKCQd.net] 邪道でもなんでもないよ これを邪道とか言ってるのはCとかにどっぷり漬かった人間のただの負け惜しみ 682 名前：デフォルトの名無しさん mailto:sage [2015/09/05(土) 04:48:42.79 ID:Bq/cKCjD.net] どっちの書き方も使うからどっちが良いも悪いも邪道もどうもない ただし再帰のを話題にするなら、一回その楽な書き方で書いてから、正しい書き方に直すような前提の話になる CPUやメモリを隠してる状態でこの話は有り得 683 名前：ない 再帰かどうかと言うのは、CPUとメモリの使いかた (の人間的な概念) を指すものだから。 この手の話題を出す限りは、Pythonが仕様書兼動作テストで、それを手動最適化して直したのが Cの実装 なんてのも十分有り得る ま、さらに深くまで考慮するとまったく区別のしようがない同じ物なんだけどね。 ちょっと前に Rubyでしか使えないRuby用語の配列を、まるで本物の配列のように思い込んでた人がいたね。 再帰も再帰でそれと同じ。もちろんループも。 特定の言語内部だけの話ならそちらのスレにどうぞ。 [] [ここ壊れてます] 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までの等差数列の和だよ 漸化式の全ての項を使う →全てのノードを使う時は動的計画法で最適化できないんよ そのケースは、ある点からの周囲の経路を探索する場合 ディレクトリ探索だったり、塗りつぶしだったり、つまり全検索をかける場合 こういうのは再帰を使うだろうに

---

---

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

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