なあ、再帰関数好きな人いる? パート3 [転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
ハノイの塔って最初誰が考えたんだろなw
まさに再帰のための問題だよなw >>737
エドゥアール・リュカ/1800年代後半 連分数展開って見た目的にも再帰的
あとは連平方根なんてのもあったっけ? 数学のように条件を書くだけで処理が書けるのは楽しい >>741
では
これの値を教えてください
lim[n->∞]sin(πen!)
わりとまじです void **hoge; のときに
void *fuga = hoge; でもイケてしまうときとダメな時があるんだが良く判らん。 昔カッコつけてクラスのコンストラクトの再帰だったかループが爆発するバグを作ったことがある
バックトレース大変だった思い出
フリーダムなC言語系は好きだ int main()
{
return main();
} 再帰は面白いと思ってた時期もあった気がする。
ただ引数や戻り値を順番付けて管理しておけば処理内容はループと同じなんだよね。もちろん実行資源の内訳も。
と言うより、「再帰はループの一つである」という表現のほうが正しいか ただのループでスタックオーバーフローの心配はないからなぁ x 再帰はループの一つ
x ループは再帰の一つ
o 再帰でやりたいことはループでも実現できる
o ループでやりたいことは再帰でも実現できる >>755
ただのループが何を指すかが微妙だけど、
再帰を展開したようなループだとカーソル的な物が行き場を無くすとかはあるがな。
そもそもループ自体まやかしみたいなもんだよ。
cmpとjzでしかない。 再帰関数は動作の見た目(想像)が楽しい
でも天才は漸化式求めて一発で計算する >>758
あー、ループあるな。そういう意味では。
すまんかった。 >>755
再帰と同じようにループを実装すればオーバーフローしますけど。
>>756
実現できるのは外部仕様の話。
内部仕様の話だとこうなる。
ループを使って再帰を作ることはできる。(そもそも内部的に関数はニーモニックの段階でそう作られている)。
関数や再帰にまで抽象化 (いろいろ処理) されたものから、内部仕様としてのループを再現することはできない。
まずこうゆうときは、E(電力)あたりの最小可能処理数を考えるとわかりやすい。
あとはその処理 (抽象概念) にあなたがどのような名前をつけるか。
再帰を再帰だと思うのは、誰かが再帰に再帰という名前をつけた上、あなたもそれを再帰と思い込んだから。
実際にはループで実装されている。 >>762
> 再帰と同じようにループを実装すればオーバーフローしますけど。
意味わからん
再帰は必ずスタックを使う
単なるループはそんなもん使わない
どうやってスタックオーバーフローするんだ? 分からんなら分からんければいいんじゃね
先に事前に書いてあることを偉そうに質問されてもね 再帰を展開したようなループ、だから
そんなもん使わない、が偽か、
再起だって必ずしもスタックを使い尽くさない、が真かなんだよな。 スタックが必要あるからスタックが採用されるんでしょう。
ループや再帰にかかわらず。そして最適化すれば同じ記述。 >>767
int main(){ return main(); } 簡単です C言語は関数内でローカル関数を定義できないから嫌い
ローカル関数でなら末尾呼び出し除去の保証とかやりやすいのに >>769
それオプティマイザ次第で、ただの無限ループになるよ。
そう言う意味じゃなくて。
せめて、cmpとjzに、いやdjnzあるじゃんみたいな話についてこようよ。 >>770
C++で、クラス内に関数を定義すりゃいいだけ >>774
メモリアクセス要るようなループ書かんだろう…。ましてや再帰の展開で。 >>770
なるほどね,コンパイル単位内だけで末尾再帰を保証するわけだね >>770
今時のコンパイラならファイルスコープでもインライン展開とか再帰の末尾最適化ぐらい余裕でしょ コンパイラが最適化を諦めるくらい難解な処理するんだろ
そのくらいのことじゃないと再帰関数する意味無いからな
それか楽をしたいか、趣味か 木構造をループで辿りたいときってスタック使わずにできる? 辿るだけ(構造を保持しなくていい)ならできるでしょ
たとえば全てのアドレスを出すだけとか スタックなんて "ヒト" の概念だからな。
自動で伸び縮みするような配列だって内部的にはスタックと同一なわけで一方的に増えていくかもしれない。
構造や順序をスタックせず、現在の状態だけを保持していたとしても、オーバーフローしない理由にはならない。 ツリーだってメモリがツリー状になってる訳じゃない罠 質問 スタックを使わずにできるか
回答 オーバーフローしない理由にはならない
意味不明 >>784
関数呼び出しどうやってするんだよ
それにそんな再帰関数は好きになれないな >>786
ニーハオ!
モドル サキ ハ ドコニ キヲク シマスカ? ヒープだろうが、スタックだろうが、メモリサイズが有限である以上、
オーバーフローは起こるわな。 馬鹿には永遠に判らんだろうけど。 情報を保存しながら、進むならば、ループだっていつかオーバーフローする。
保存せずに計算できるならば、再帰でもオーバーフローしないかもしれない。 誰かの口真似したのかもしれないけどそれは完全に間違ってますよ >>796
Prologですから再帰述語で関数ではありませんが、
repeat :- 割り込みあり,!.
repeat :- repeat.
の場合、スタックの一番上でpop,pushを繰り返すことが可能なのではないでしょうか。 すみません。まちがえました。これではrepeat内でのループになってしまって
Prologのrepeatになりませんでした。分かり難くなりますから割り込みを外します。
repeat.
repeat :- repeat. >>797 だと、
繰り返しを最終回にするための割り込みとしたかったのですが、
実行開始の遅延を終了するための割り込みになってしまっています。 >>797
どういう条件だとスタックが伸びず、伸びることが不可避なのはどんな場合か。 >>800
実行時、述語の最後の節で、最後の副目標(サブルーチン呼び出しにあたる)に差し掛かった時に
その節のそれまでの副目標が全て決定性(別解があり得ない)に終了しているという条件で、
この節の呼び出し時点までスタックを戻って、そこに新たな再帰呼出しの情報を積むことができる。 好きか嫌いかで言ったら好きだ
趣味以外では使わないけど 再帰がスタックを積むんじゃなくて関数がスタックを積むんちゃうの?
スタックがなければ実現不可能な処理なら、ループで実装してもスタック積むんちゃうの? >>806
ループで実現したときはスタックに積まれない。 >>808
実行系に頼らず自分でスタックを実装するってこどだろ
使用メモリ量が不定なのは一緒 抽象概念が実体であるかのような基準で話をする人が多すぎる
再帰でスタックが発生するならそれに対比するループも必ず同等のスタック量が発生する。
それでも 「ループで実現したらスタックは積まれない」と言うのなら、それは実現できていない。
抽象概念としての名称は便宜上再帰であるかループであるかの違いはあるが、実体としての処理は必ず同等。 >>811
再帰は、入れ子状の関数呼び出しで、呼び出す関数は全部同一だから、
コードは一つで良い。しかし、関数だから呼び出す度にスタックに情報を積むし、
戻ってくるまで、積んである情報をPOPできない。
ただし、関数が末尾に有る時、則ち、戻って来た情報に対して何らかの計算をしてから
情報を返すということがない関数に関しては、戻ってきた値を直接自分の戻す値に
できるわけだから、呼びだされた時の普通なら積む情報を積まずに済ませることが
できるかも知れない。こういうことを「実体」というのですないか? すみません。最後
こういうことを「実体」というのではないか?
です。 >>813
根本的には処理もデータも区別なく実体ってことでしょ。
ループ自体も関数自体も実体。 継続は再帰ほど市民権得てないからなぁ。
継続を深く理解しているプログラマは全体の1割に満たないんだろうな。 物自体の実在性を議論してんのかよ
やっぱ再帰って難しいわ 私は再帰の塊のようなプログラムを作ったことがある。
DirBaseだ。
起動後のウィンドウにエクスプローラからファイルやフォルダを
ドラグ&ドロップするだけで簡単にツリーができる。
DirBaseで検索すれば、ダウンロードできる。 競プラではforループが盛んらしいが、言語開発者としては再起の方が使って欲しい
ソースは俺が今朝見た夢 >>819
ん?setjmp/longjmp のことですか? (数値計算を主体とする)関数では使わないけど、
再帰ルーチンで使用頻度が激しいのは、外部記憶装置を含めた初期化ルーチン。
一つのルーチンで、内部記憶(主記憶装置)と外部記憶(HDD等)の出入りを管理している場合に、
初期化ルーチンで外部記憶が存在しない場合には、ルーチンで保存している定数を読みだして、外部記憶に保存する。
初期化ルーチンからの定数の読み出し・外部への保存が再起処理。
初期化ルーチン以外では使わない手法。
分割して作成すると、何年か後に見直した時に、どのように初期化しているのかわからない、という事態になることが多発したので、
初期化が必要な場合には、このような手法で同一ルーチン内に収めるようにした。
もっとも一番利用頻度の高いのは、Winでは、ダイアログボックスのプロシージャ。再起の塊で、何をしているのかわからなくなってくる。 再帰プログラムは関数の呼び出しで積みあがるスタックを配列とみなせば、ループアルゴリズムそのものだ。 ファイルやフォルダ、ダイアログやウインドウは階層構造で構成されるので、再帰プログラムを使うのが一般的だ。 再帰って何?って頃から普通に再帰使ってたからなあ。
自分自身を呼び出せば良いじゃんみたいな。
高校で数列とか演繹法が得意だったせいかも。
自然に使ってた。 再帰云々言ってるのは大昔のFORTRANとかCOBOLを使ってた人ぐらいじゃないのかな
あと組み込みとかでスタックサイズが厳しい環境で組んでるとか 再帰プログラムの基本はスタックにデータを入れ積み上げていく過程と、スタックからデータを取り出しスタックをクリアしていく過程の二つの動作しか基本的にない。
データを取り出したら、そのデータを使ってプログラミングされた処理を実行する。スタックはデータを貯めることと同時に処理の順番を決めている。再帰のプログラミングには二つの概念が必要だ。 javaで再起処理書いたらガーベッジコレクションが掃除してくれるもんだと思ってたけど違うの?
十年前の記憶だから曖昧ですまない
cpu使用率が100%になるけど影響ないから使ってます〜って顧客に言われたのを思い出したもんやで 僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
980U0 今時スタックオーバフローぐらいでOSは死なないから大丈夫 再帰アルゴリズムはなるべくライブラリで隠蔽して欲しいな。
自分で書くのはまだしも他人の再帰コードを読むのはかなり嫌。 再帰関数と言えばアッカーマン関数とかたらい回し関数などが
有名ですが他にも何かある? 174 その名前は774人います (バットンキン MM5a-fW3D) 2018/11/16(金) 07:04:12.40 ID:N77Q/1ZeM
>ドラゴンクエストの世界観が全く反映されていないような印象
ド ラ ゴ ン ク エ ス ト と は 何 か ?
ドラゴンクエストとは何かを問い続けるのが、終わらないドラゴンクエストだろう? 違うか?
2 その名前は774人います (バットンキン MM5a-fW3D) 2018/11/16(金) 07:42:40.97 ID:N77Q/1ZeM
再帰関数を理解するにあたり先輩社員に教えていただいたのですが、その時の再帰関数の例がとてもわかりやすかったので共有させていただきます。
この例のおかげもあり、はじめは再帰関数なにそれ状態から、最後はしっかりと実装できるようになりました。再帰関数はPythonで実装しています。
https://qiita.com/jumpyoshim/items/20e6b5e70efa466699b4 再帰関数『終わらないドラゴンクエスト』
ドラゴンクエストとは?(){
ドラゴンクエストとは?()
} def DQ(n)
puts "DQ #{n}"
DQ(n+1)
end >>1
好き嫌いの問題じゃないと思うが、理論上再起かそれと同等の内部処理履歴を残さないと実現できない処理なら、使うだろう
再起にならざるを得ない具体的な数学(科学)的な条件は忘れたが、けっこう複雑な処理じゃない限り再起じゃなくても実現できたように思う >>858
「再起」じゃなくて「再帰」ね
スタックを使えば、つまりメモリを余分に使用することを認めれば
再帰はループに書き換えることができるから
再帰でなければ出来ないことは原理的に存在しない
更に言えば関数を受け取りまた返す高階関数があれば
いわゆる不動点演算子に相当するものが書けるので
関数の再帰的定義は不要になる 論理的にはクイックソートよりマージソートが好き。
実用性はクイックソートが上なのかな? >>859
>再帰はループに書き換えることができるから
そのループ再帰だよ・・・
再帰の問題点もそのまま同等に引き継いでるよ・・・ ループも不動点演算子も再帰関数の実装の仕方でしかない リストに対してはクイックソートやマージソートより選択ソートや挿入ソートのが速かった。
ケースによって使い分けるために色んなソートがあるんだなと実感した。 >>861
ループと再帰とは違うよ
更に言えば高階関数があればループも再帰も必要ない
不動点演算子もループも再帰だと言うのはナンセンスだ
それは「再帰と同じだ」と君が思うものを再帰と呼ぶ、と主張しているに等しい
こんな君だけの主観による再帰の定義では議論にならない チューリング完全なんだからどの言語でも一緒、という暴論と同程度に「ループと再帰は同じ」も暴論
コンピュータからみた話じゃなくて、プログラムを書く人にとってループと再帰が同価値なのかが問題になる
自分は、複雑でも読み溶ける再帰の方が好き。ループが複雑になると、どの変数がいつのどの値を持っているのか追いきれなくなる
再帰で同程度に複雑な処理を書くと、引数の数やら名前からすぐにヤバイ臭いがするんでそんなに腐らない 末尾再帰にすると結局for文とやってることが一緒になる モナドな再帰(IOモナドやリスト->リストな再帰)は単純な再帰でもスタック消費しない。
繰り返しコードの単純さは再帰>末尾再帰>=ループ。 非同期処理の終了を待って、次の繰り返しを行う
再帰でなければ書けない >>871
非同期処理の終了はイベントやコールバックで通知されるものとする
終了を待つ同期プリミティブは存在しない
Javascriptだとこれが普通で、繰り返しでは書けない async/await が JavaScript の新しい仕様として入ったのも知らんのか await/asyncの仕組みを知らないと見える
それ使って、繰り返しで書いてみなよ やっぱ、await/asyncで出来そうな気がしてきた >>867
違うよ
柴犬にこっちは太郎でこっちは次郎だから別の犬だ、と言ってるのと同じ 再帰処理は
現在の関数が戻ってゆくアドレスをスタックに保存し、このアドレスを積極的に利用する。
プログラミングの実行アドレスをスタックから取り出して制御するので、
再帰プログラミングを利用するコツは、戻りアドレスを正しく理解することだ。
再帰は同じ関数を行ったり来たりするものだが、
日常の社会では、やらない方法だ。
普通は、配列を利用して、そこに保存してあるデータを使い、
同じ場所でプログラムを実行する >>881
そらまあ再起が辿るイメージ図は全てツリーって名称付けれますし ゲーム作るときになってようやく再帰の恩恵を得た
めっちゃ書きやすい >>883
ミニマックス法かアルファベータ法だろ? マイコンだとスタックが1桁とかだから再帰書いた瞬間に死ぬ ルネサスのRL78/G10はRAMが128Byteしかないらしいな λf . (λx . f (x x)) (λx . f (x x)) ループで書くと出現する余計な変数がなくなるのが再帰のメリット >>889
?
kwsk
ループ変数は再帰関数でも必要なのでは? どんどんスタックにつめば確かにループ変数はいらない
ただ、人間のためにループ変数はあった方かいいと思うけど 再帰関数を理解したとき、最初にこれ考えたやつは天才だと思ったね
実行速度やスタック問題はともかくコードは見ていて美しい以外の何者でもない。 CやUnix、オブジェクト指向なんかよりもはるかに古いんだよな
最初に実装されたのはlispかな
メモリを食いすぎるのでおもちゃしか動かなかったようだが 今の時代メモリ食いすぎても動くし遅くもならないよな
1億再帰とかやったら話は別だけど >>890
要らない
/* n の階乗を求める */
int fact(int n)
{
if(n==0){
return 1;
} else {
return fact(n-1);
}
}
実質ループする処理だけど、ループの回数数えるための
変数は一切出現しない。なおかつ n は不変。 おお、"n*" を忘れた。こんな短い関数にバグ突っ込む俺(泣) くだらん処理にスタックを使いたくないのでわしは使わん
ライブラリが殆ど無いマイナーCPUのマイナーCコンパイラでQuickSortを書いた時くらいじゃケケケ 最近じゃオプティマイザがなるべくスタック使わないように
最適化してくれるんじゃなかったっけ? >>898
末尾再帰ならそうだと思いますが、末尾再帰でなければ無理でしょう >>896-897 は末尾再帰じゃないから最適化されにくい、というか、されない >>8
ループと再帰の能力は同じです
かなり古い計算論の結果です >>899
結合法則を仮定していいドメインなら
CPS変換を用いて最適化する手法が随分前からあります
結合法則はGPU並列化でも使われてます
浮動小数点の場合は工夫しないと誤差が変わりますが
ちなみにC++ conceptの初期案でもaxiomで法則を記述出来ました >>902
scheme の継続渡しに関係しますか?
キーワードありがとうございます >>903
そう
Continuation-passing style, defunctionalization, and associativity
Categorical Structure of ContinuationPassing Style
この辺のサンプルプログラム読んで すき
しかし再帰絶対書かないマンが思いの外多くて草生えるわ
末尾最適化できない再起をループに展開したって結局キューだのスタックオブジェクトでヒープ使うわけで
メモリ大幅に節約できると勘違いしてる基地外とか話にならん
再帰深度がたかだか1000段とかでスタックフレームにデカいオブジェクトブチ込んだりしなきゃ
素直に再帰で組むのがいいに決まってるじゃないか
数学的演算でもしない限り業務用でスタック溢れるケースを探す方が大変 スタックとヒープは別物
共有してるアーキテクチャもあるが ループに展開できる処理をわざわざ再帰で書く奴も大概やけどな。 >>909
二方向に再帰するもの、は展開に苦労しますね
式の評価は、再帰じゃないと書けないですね 再帰的データ構造は再帰でたどるのが楽なんだけど
ループで処理したほうが途中で抜けたり処理を組み合わせやすい
そこで再帰的な処理を遅延リストと組み合わせてループで処理するやり方がいまでは一般的な気がする
こういうふうに C#
https://paiza.io/projects/WbmxzuNdJq95o9RYTKFY_A 何が一般的なのか知らんがかなり変態的なコードだな
ループでGetEnumerator呼び出したりMoveNextの戻り値を見ずCurrentを取り出したりは一般的じゃないぞ
つーかバグだろそれ レス数が900を超えています。1000を超えると表示できなくなるよ。