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

1 名前：名無しのプログラマ [2015/08/09(日) 17:46:33.69 ID:Icb40LOY.net] for,while使うの嫌いで基本的に再帰多用するんだが、だめなの？ 皆から敬遠されてる気がする 604 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 03:40:53.92 ID:ucFEbRDO.net] >>587 C言語においては、配列は固定長データが連続で並んでる。 その他の言語ではそうとは限らない だから"配列"だけで断定することは出来ない。 これでいいですよ。 605 名前：デフォルトの名無しさん [2015/09/01(火) 03:44:11.25 ID:Uqk8gU8P.net] >>591 C言語はプログラム言語です つまり、プログラムにおいて配列とは固定長データが連続で並んでるものなんです 606 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 04:07:30.08 ID:ucFEbRDO.net] わかりやすく言うと プログラム言語 というカテゴリの中に 　・C言語 　・Perl 　・PHP 　・Ruby 　・その他 　などが含まれます。 その中で、C言語では配列とは固定長データが連続で並んでるものなんです 607 名前：デフォルトの名無しさん [2015/09/01(火) 04:14:14.53 ID:Uqk8gU8P.net] >>593 C言語以外では困るのでC言語でお願いしますと言いました。 いいですか、私はC言語以外では困るんです。 あなたは私を困らせたいのですか？困らせたくないでしょう。 私に同情してください。 配列=固定長データが連続で並んでる これでいいですね。 608 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 04:19:55.14 ID:C9NG6GGp.net] >>593 スクリプトだらけなんだが… 609 名前：デフォルトの名無しさん [2015/09/01(火) 04:24:44.91 ID:6K59ZHF3.net] つうか、C言語のもの以外それみんな名前が「配列」なだけのハッシュ… 610 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 04:33:56.34 ID:ucFEbRDO.net] 配列の実装がハッシュなだけ。 配列だからって、実装まで決まらない証拠。 611 名前：デフォルトの名無しさん [2015/09/01(火) 04:37:44.81 ID:Uqk8gU8P.net] >>597 ふうむ、たとえば二分探索木の実装に赤黒木やスプレーツリーがあるように データ構造にも抽象的なものとより具体的なものがあるわけっしょ。 つまり、抽象データ構造としての配列とより具体的なデータ構造としての配列があり、 抽象データ構造としての配列に連想配列が含まれ、より具体的な連想配列のデータ構造として ハッシュテーブルがあるってことでしょね。 612 名前：デフォルトの名無しさん [2015/09/01(火) 04:57:20.77 ID:6K59ZHF3.net] データ構造についての普通の教科書読めば そういう緩い意味で「配列 array」は使わないことがわかるよ。 613 名前：デフォルトの名無しさん [2015/09/01(火) 04:58:46.51 ID:6K59ZHF3.net] array data structureとarray data typeとの区別をつけようね。 614 名前：デフォルトの名無しさん [2015/09/01(火) 05:04:47.15 ID:6K59ZHF3.net] 細切れに書いちゃってアレだけど、 array data typeはその実装がリストでもいい。 だから、効率性を云々する時のarrayはarray data typeではなくて array data structureの話じゃなきゃいけない。そしてarray data structureは インデックスからアドレスへの容易な算術演算によって（典型例が データの連続配置）、O(1)アクセスを可能にするデータ構造。 615 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 06:38:20.62 ID:lctJDoUS.net] いや、そんな長々と説明しなくていい� 616 名前：諱B array data structureがO(1)でなければならないというのなら それを定義したのはどれかを言ってくれればいい。 おそらく無いからそれをごまかすために説明してるんだろうと思ってるけどねｗ [] [ここ壊れてます] 617 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 07:30:15.06 ID:CkpgYLyf.net] >>594 うわあ、これはマジモンでヤバい人だ… 618 名前：デフォルトの名無しさん [2015/09/01(火) 08:00:49.42 ID:/DoXUIG1.net] tet 619 名前：デフォルトの名無しさん [2015/09/01(火) 08:05:00.21 ID:/DoXUIG1.net] メモリの取得、解放なんかは OS自体にその手の機能が存在してるべきなんだよ 速度をそこまでガチで求めない場合の簡易版で良い 620 名前：デフォルトの名無しさん [2015/09/01(火) 08:11:25.32 ID:KtW8DmAo.net] ゲーム木探索とかの再帰じゃないとできないことぐらいしか再帰関数でやらない 逆に再帰関数はforやwhileに書き換えできる？　出来るならそっちにしたいレベル 621 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 08:25:26.84 ID:vcgHCiFQ.net] テンプレートメタプログラミングやC++11のconstexprだと、どうしても再帰使わないと書けないコードでてくる…… あれってなんか解決策あるんですかね…… 怠惰なインスタンス化のように無限再帰を回避する方法ならあるけど 622 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 12:55:10.42 ID:4i2DmfPV.net] ＞再帰じゃないとできない まず無い。 再帰でベンチマーク作るのでなければ。 623 名前：デフォルトの名無しさん [2015/09/01(火) 13:38:18.55 ID:DJMTd98b.net] >>581 君に理解できる話じゃないよ。 クイックソートのスタックオーバーフローを防ぐためと称して 非再帰化しろだのスタックサイズを増やせだのと、 君程度の人なら言うかもしれないが、大学の先生がそんなことじゃ困る。 空間計算量の最適化を教えなさいよという話だ。 それ無しに非再帰化だのスタックサイズだのと言われる学生さんが可哀想だ。 624 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 13:48:33.08 ID:4i2DmfPV.net] >>609 君ごときの無能にそんなことじゃ困るなんて言われる 先生がかわいそうだ。 625 名前：デフォルトの名無しさん [2015/09/01(火) 15:23:42.04 ID:6K59ZHF3.net] >>602 data typeじゃなくて data structureとしてのarrayなら下にあるけど？ 常識なんで、定数アクセスじゃないadsがあるというならむしろそっちが実例挙げてね https://en.wikipedia.org/wiki/Array_data_structure 626 名前：デフォルトの名無しさん mailto:sage [2015/09/01(火) 19:15:05.37 ID:jZfLWulg.net] 大学と共同研究とか外注受けたりとかやったことあるやつは 大学の先生の技術レベルがやばいのは経験してるでしょ いまさら騒ぐ事でもねーよ 627 名前：デフォルトの名無しさん mailto:sage [2015/09/02(水) 00:47:36.69 ID:kkVdXJxG.net] サイ基地外は現実を否定することしかできない 628 名前：デフォルトの名無しさん mailto:sage [2015/09/02(水) 17:48:58.50 ID:pfz+JPDH.net] メモリ上でスラッと並んでるのが配列であって そうじゃないけど並んでるように見えるのは あんまり配列とは呼びたくないでござる。 629 名前：デフォルトの名無しさん mailto:sage [2015/09/02(水) 19:19:55.89 ID:DAe+xWqL.net] 組み込みや専用機なら配列と言う概念はいらない 630 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 02:22:06.78 ID:APM+2rA2.net] 位置の並びは関係なく、演算だけで区別できるのが配列 Rubyの配列はRuby用語 631 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 11:36:04.16 ID:hDY8eKzg.net] こんなにも配列の話題で盛り上がるとは みんな配列が大好きだね 人気者の配列のループには繰り返し文を使うから 繰り返し文は不滅だね 632 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 11:44:10.96 ID:HOkCudGK.net] >>614 わかる。配列とコレクションは別だよな。 633 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 12:12:06.19 ID:dGS6eFW0.net] 配列の処理もforじゃなくて再帰で書くんだがやめたほうがいいのかね 634 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 12:26:06.74 ID:hDY8eKzg.net] >>619 具体的にどんな感じで？ 635 名前：デフォルトの名無しさん [2015/09/03(木) 14:27:45.88 ID:9nQXwra1.net] >>620 head, tail, 636 名前：append さえあれば普通のリストとほぼ変わらん [] [ここ壊れてます] 637 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 15:43:06.69 ID:dGS6eFW0.net] >>620 hoge(input, output){ 　　if (size(input) == 0) { 　　　　return; 　　} 　　return hoge(tail(input), output.append(dosomething(tail(input)))); } こんなかんじ 638 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 18:02:46.75 ID:IwEVB15/.net] わざわざ再帰を使うなんてやめた方がいい。 ちゃんとループで書く技術を身につけるべき。 639 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 18:37:19.10 ID:dGS6eFW0.net] forのほうが手軽なんだけど、しょーもないインデックスミスしちゃわない？ 最近はどの言語も範囲forがあるから、まだいいんだが 640 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 19:27:47.89 ID:FSKtVBgW.net] > forのほうが手軽なんだけど、しょーもないインデックスミスしちゃわない？ あんまりないな。いつも書き方一緒だし。 それ以外の書き方をしていれば「？」となる。 641 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 19:39:17.92 ID:6KaE3e8w.net] 単に慣れの問題 642 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 19:55:45.70 ID:Fz3Ka6Ix.net] >>624 しょーもないミスをしないためにも再帰は覚えておくべきだね 使いドコロはケース・バイ・ケースだけど 何が何でも再帰を避けるようなことさえしなければいいんじゃない？ 643 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 20:37:42.86 ID:FSKtVBgW.net] >>627 forは範囲forで対応できるけど、 再帰は、範囲再帰ってあるの？ｗ 再帰のほうがしょーもないミス多いよね。 終了条件ミスってスタックオーバーフローｗ 644 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 21:22:18.75 ID:qp+WFxZL.net] 範囲forに対応するものは高階関数になるんでね？ なんでもできてしまうforよりかは 畳み込み、map,foreach, filterなんかで使いわけたほうがいい 645 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 21:23:50.62 ID:qp+WFxZL.net] 後は　>>= ,　<*> 646 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 22:32:32.63 ID:FSKtVBgW.net] >>629 > 範囲forに対応するものは高階関数になるんでね？ そんなわけない。 範囲だろうが範囲じゃなかろうがforはfor。 647 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 22:52:40.78 ID:qp+WFxZL.net] 拡張for文はIteratorを実装しなけらばならなかったりforeachメソッドがなきゃいけなかったりbegin/endがなきゃいけなかったりするから ある程度抽象的だから whileと同じような単純な構文であるforと同じだって言われると微妙な気持ちになる オブジェクト指向ありきみたいな 648 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 22:55:55.75 ID:K5TdrWRE.net] 便利だけど本質的には普通のforと同じ。 便利だけど単なるシンタックスシュガー なにより副作用のために使うものだから 関数型的ではない。 649 名前：デフォルトの名無しさん mailto:sage [2015/09/03(木) 23:50:51.54 ID:LEFvEBee.net] 問題の解き方を探るときにwholemeal approachをやろうとすると、再帰は宣言的なんでスタート地点にしやすい。 dynamic programmingでやることにしても、最初の明快だけど遅い関数を書くときは再帰が多い。 そっからチューンしていったものが正しいかを検証したいとかよくある。 ので、再帰もループもどっちもある程度便利に使える言語は便利よ。 650 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 07:55:30.31 ID:iLm0cn85.net] >>633 0点。 651 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 09:21:42.12 ID:QpES+Y0P.net] 宣言的な書き方は、総じて手続き的な書き方よりコードが短くなるため可読性が高い。ただし抽象度も上がるため、読む人を選ぶ可能性がある。 例えば以下の関数定義、手続き的に素直に書こうとするともっと長くなるはずだが、こう書かれても理解できない人もいるかもしれない。 f(n) = | 0 (n = 0 のとき) | n + f(n - 1) (n > 0 のとき) | -f( |n| ) (n < 0 のとき) なお、n は整数。 俺は宣言的な書き方が好き。 652 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 10:16:03.02 ID:qqcvyIbf.net] 数学における関数の、定義域別の関数定義みたいな書き方っすね 653 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 13:15:00.48 ID:YC3FOSdx.net] 結局、元の定義が再帰的でないと、再帰を使う意味は無いんだよな プログラミングでもっとも良く使うデータ構造は配列ですし、 配列のループ処理を再帰とみなす必要は無いですし、 繰り返し文であふれるのは自然だね 654 名前：デフォルトの名無しさん mailto:sage [2015/09/04(金) 17:32:01.47 ID:45GRgS6i.net] >>635 理由書いてないので無視するｗ 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] いや再帰っつーのは終わるまで必ず自身がどの手順でそこの処理に居るのかが記録されてるから。 必要がないもくそもない だから、スコープスタックを保存する必要がある時に、再帰を使う必要があるんですってば

---

---

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

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